# مهندسی نرم افزار > مباحث مرتبط با مهندسی نرم‌افزار > الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها >  تبدیل Infix به Prefix

## Behrouz_Rad

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

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

&#40;&#40;&#40;&#40;a/b&#41;-c&#41;+&#40;d*e&#41;&#41;-&#40;a*e&#41;&#41;

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

-+-/abc*de*ae


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

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

----------


## fakhradin ganjali

http://portal.acm.org/citation.cfm?id=954312.954319
فکر کنم اینجا یه چیزایی باشه.

----------


## Saeid1578

#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

> #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)))
> ...


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

----------


## sevil sevda

سلام وقتتون بخیر
آقا من کد تبدیل infix به prefix و  postfix رو میخوام که به زبان C#‎ در محیط کنسول نوشته شده باشه :ناراحت:

----------


## abtin021

برنامه 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;
}

----------

