PDA

View Full Version : تبدیل Infix به Prefix



Behrouz_Rad
سه شنبه 20 بهمن 1383, 18:20 عصر
برای تبدیل عبارت infix به prefix به صورت زیر عمل کنید:
1) ابتدا عبارت را به صورت کامل پرانتز گذاری می کنیم (با توجه به اولویت عملگرها)
2) هر عملگر را به سمت چپ پرانتز بسته خودش منتقل می کنیم.
3) تمام پرانتزها را حذف می کنیم.

مثال) عبارت a/b-c+d*e-a*e را به prefix تبدیل می کنیم:
ابتدا عبارت را با توجه به اولویت عملگرها پرانتز گذاری می کنیم:


((((a/b)-c)+(d*e))-(a*e))

و سپس به طریقه گفته شده به prefix تبدیل می کنیم:


-+-/abc*de*ae


در روش postfix نیز همانند prefix است با این تفوت که در مرحله ی دوم، هر عملگر را به سمت راست پرانتز باز خودش منتقل می کنیم:
به عنوان مثال نتیجه postfix عبارت فوق به شکل زیر است:
ab/c-de*+ae*-

موفق باشید.
:wise1:

fakhradin ganjali
یک شنبه 06 خرداد 1386, 00:03 صبح
http://portal.acm.org/citation.cfm?id=954312.954319
فکر کنم اینجا یه چیزایی باشه.

Saeid1578
دوشنبه 11 تیر 1386, 15:43 عصر
#include <iostream>
#include <string>
#include <stack>
using namespace std;
//i love macros
#define isOp(x) (x=='-'||x=='+'||x=='/'||x=='*')
#define isHigh(x) (x=='*'||x=='/')
#define isLow(x) (x=='-'||x=='+')
#define isSame(x, y) ((isHigh(x) && isHigh(y)) ||(isLow(x) && isLow(y)))
#define isClose(x) ((x==']')||(x==')')||(x=='}'))
#define isOpen(x) ((x=='[')||(x=='(')||(x=='{'))
string reverse(string s)
{
string tar;

for(int i = s.size(); i >= 0; i--)
{
tar += s[i];
}
return tar;
}

string infix2prefix(string source)
{
stack<char> output;
stack<char> ops;
string eq(reverse(source)); //reverse equation
char c;
//for each element in equation
for(int i = 0; i < eq.size(); i++)
{
c = eq[i]; //prevent repeated dereferencing
//if not /-+*[]{}()
if((!isOp(c))&&(!isClose(c))&&(!isOpen(c)))
output.push(c);
//if is )}]
if(isClose(c))
ops.push(c);
//if is /+-*^
if(isOp(c))
{
//if stack is empty put operator on stack
if(ops.empty())
{
ops.push(c);
}else{
//else if top of stack is )]or} push operator on stack
if(isClose(ops.top()))
{
ops.push(c);
}
//is precedence is the same or higher push it onto
//operator stack...else, push it straight to output
//stack
if(isSame(c, ops.top())||isHigh(c))
{
ops.push(c);
}else{
output.push(c);
}
}
}

//if ([or{
if(isOpen(c))
{
//move operator stack to output stack
while(!ops.empty())
{
output.push(ops.top());
ops.pop();
}
}


}
//put remaining operators on output stack
while(!ops.empty())
{
output.push(ops.top());
ops.pop();
}

//turn output stack into a string
eq = "";
while(!output.empty())
{
eq += output.top();
output.pop();
}
return eq;
}

int main()
{

string eq;

char c;
cin >> eq;
while(eq != "exit")
{
cout << infix2prefix(eq) << endl;
cin >> eq;
}

return 0;
}

لطفا" در صورت اشکال برام مشکل رو بفرستید.من دارم میام ایران.ممکنه که ی خورده دیرتر جواب بدم.

sahasoft
دوشنبه 27 آبان 1387, 17:16 عصر
#include <iostream>
#include <string>
#include <stack>
using namespace std;
//i love macros
#define isOp(x) (x=='-'||x=='+'||x=='/'||x=='*')
#define isHigh(x) (x=='*'||x=='/')
#define isLow(x) (x=='-'||x=='+')
#define isSame(x, y) ((isHigh(x) && isHigh(y)) ||(isLow(x) && isLow(y)))
#define isClose(x) ((x==']')||(x==')')||(x=='}'))
#define isOpen(x) ((x=='[')||(x=='(')||(x=='{'))
string reverse(string s)
{
string tar;

for(int i = s.size(); i >= 0; i--)
{
tar += s[i];
}
return tar;
}

string infix2prefix(string source)
{
stack<char> output;
stack<char> ops;
string eq(reverse(source)); //reverse equation
char c;
//for each element in equation
for(int i = 0; i < eq.size(); i++)
{
c = eq[i]; //prevent repeated dereferencing
//if not /-+*[]{}()
if((!isOp(c))&&(!isClose(c))&&(!isOpen(c)))
output.push(c);
//if is )}]
if(isClose(c))
ops.push(c);
//if is /+-*^
if(isOp(c))
{
//if stack is empty put operator on stack
if(ops.empty())
{
ops.push(c);
}else{
//else if top of stack is )]or} push operator on stack
if(isClose(ops.top()))
{
ops.push(c);
}
//is precedence is the same or higher push it onto
//operator stack...else, push it straight to output
//stack
if(isSame(c, ops.top())||isHigh(c))
{
ops.push(c);
}else{
output.push(c);
}
}
}

//if ([or{
if(isOpen(c))
{
//move operator stack to output stack
while(!ops.empty())
{
output.push(ops.top());
ops.pop();
}
}


}
//put remaining operators on output stack
while(!ops.empty())
{
output.push(ops.top());
ops.pop();
}

//turn output stack into a string
eq = "";
while(!output.empty())
{
eq += output.top();
output.pop();
}
return eq;
}

int main()
{

string eq;

char c;
cin >> eq;
while(eq != "exit")
{
cout << infix2prefix(eq) << endl;
cin >> eq;
}

return 0;
}
لطفا" در صورت اشکال برام مشکل رو بفرستید.من دارم میام ایران.ممکنه که ی خورده دیرتر جواب بدم.



این که اشتباهه اصلا کار نمی کنه

sevil sevda
سه شنبه 26 آذر 1392, 13:50 عصر
سلام وقتتون بخیر
آقا من کد تبدیل infix به prefix و postfix رو میخوام که به زبان c# در محیط کنسول نوشته شده باشه:ناراحت:

abtin021
دوشنبه 07 تیر 1395, 21:59 عصر
برنامه C++‎‎ تبدیل infix به postfix تست شده روی مک اگه خواستین روی win اجرا کنید include "stdafx.h" بهش اضافه کنید



#include <iostream>
#include <stack>
#include <string>
using namespace std;




// Simply determine if character is one of the four standard operators.
bool isOperator(char character) {
if (character == '+' || character == '-' || character == '*' || character == '/') {
return true;
}
return false;
}




// If the character is not an operator or a parenthesis, then it is assumed to be an operand.
bool isOperand(char character) {
if (!isOperator(character) && character != '(' && character != ')') {
return true;
}
return false;
}




// Compare operator precedence of main operators.
// Return 0 if equal, -1 if op2 is less than op1, and 1 if op2 is greater than op1.
int compareOperators(char op1, char op2) {
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) { return -1; }
else if ((op1 == '+' || op1 == '-') && (op2 == '*' || op2 == '/')) { return 1; }
return 0;
}


string postfix()
{
// Empty character stack and blank postfix string.
stack<char> opStack;
string postFixString = "";


char input[100];


// Collect input
cout << "Enter an expression: ";
cin >> input;


// Get a pointer to our character array.
char *cPtr = input;


// Loop through the array (one character at a time) until we reach the end of the string.
while (*cPtr != '\0') {
// If operand, simply add it to our postfix string.
// If it is an operator, pop operators off our stack until it is empty, an open parenthesis or an operator with less than or equal precedence.
if (isOperand(*cPtr)) { postFixString += *cPtr; }
else if (isOperator(*cPtr)) {
while (!opStack.empty() && opStack.top() != '(' && compareOperators(opStack.top(),*cPtr) <= 0) {
postFixString += opStack.top();
opStack.pop();
}
opStack.push(*cPtr);
}
// Simply push all open parenthesis onto our stack
// When we reach a closing one, start popping off operators until we run into the opening parenthesis.
else if (*cPtr == '(') { opStack.push(*cPtr); }
else if (*cPtr == ')') {
while (!opStack.empty()) {
if (opStack.top() == '(') { opStack.pop(); break; }
postFixString += opStack.top();
opStack.pop();
}
}


// Advance our pointer to next character in string.
cPtr++;
}


// After the input expression has been ran through, if there is any remaining operators left on the stack
// pop them off and put them onto the postfix string.
while (!opStack.empty()) {
postFixString += opStack.top();
opStack.pop();
}






return "Postfix is: "+postFixString;
}




int main()
{
int select;


while (true)
{
cout<<"1:convert infix to postfix"<<endl;
cout<<"Please Enter your Number:"<<endl;
cin>>select;
string result;


switch (select)
{
case 1:
result=postfix();
cout<<result<<endl;


}
}
return 0;
}