Infix To Postfix

Converting an infix expression to a postfix expression

We refer standard or the conventional notation as the infix notation. In an infix notation an operator is present between the operands, also the parentheses specify the sequence of operations.
Example: 2 ^ 5 * ( 3 - 4 )

A postfix notation/reverse polish notation does not have precedence rules or the parentheses and the operator is positioned after the operands it needs to apply to.
Example: 2, 5, ^, 3, 4, -, *


Algorithm : Converting infix expression to postfix expression
Step 0. Tokenize the infix expression. i.e Store each element of an infix expression into a list / queue.
Step 1. Push “(” onto a stack and append “)” to the tokenized infix expression list / queue.
Step 2. For each element ( operator / operand / parentheses ) of the tokenized infix expression stored in the list/queue repeat steps 3 upto 6.
Step 3. If the token equals “(”, push it onto the top of stack.
Step 4. If the token equals “)”, pop out all the operators from the stack and append them to the postfix expression till an opening bracket i.e “(” is found.
Step 5. If the token equals “*” or “/” or “+” or “-” or “^”, pop out operators with higher precedence at the top of the stack and append them to the postfix expression. Push current token onto the stack.
Step 6. If the token is an operand, append it to the postfix expression. (Positions of the operands do not change in the postfix expression so append an operand as it is.)


Example of infix to postfix conversion :
Infix Expression: 2 ^ 5 * ( 3 - 4 ) + ”)”

Steps Infix Token Stack Content Postfix Expression
1. 2
Append 2 to postfix.
( 2
2. ^
Push ‘^’ on the stack.
^
(
2
3. 5
Append 5 to postfix.
^
(
2, 5
4. *
1. Pop out ‘^’ having higher precedence than * and append to postfix expression.
2. Push ‘*’ at the top.
*
(
2, 5, ^
5. (
Push ‘(’ on the stack.
(
*
(
2, 5, ^
6. 3
Append 3 to postfix.
(
*
(
2, 5, ^, 3
7. -
Push ‘-’ on the stack.
-
(
*
(
2, 5, ^, 3
8. 4
Append 4 to postfix.
-
(
*
(
2, 5, ^, 3, 4
9. )
1. Pop out all the operators from the stack and append them to the postfix expression
till an opening bracket is found. i.e Pop out ‘-’ and append it to the postfix expression.
2. Pop out “(” from the stack.
*
(
2, 5, ^, 3, 4, -
10. )
1. Pop out all the operators from the stack and append them to the postfix expression
till an opening bracket is found. i.e Pop out ‘*’ and append it to the postfix expression.
2. Pop out “(” from the stack.
Empty 2, 5, ^, 3, 4, -, *

Postfix Expression: 2, 5, ^, 3, 4, -, *

Data structure needed for infix to postfix conversion: Stack and List/Queue
Time Complexity of infix to postfix conversion : O(N), where N is the number of tokens in the infix expression.


Python

Python : Infix to Postfix converison implemented in Python 3


C++ : Infix to Postfix converison implemented in C++14

#include<iostream>
#include<stack>
#include<string>
#include<list>
#include<map>

using namespace std;

class Expression {

    private:
        map<string, int> precedence;
        list<string> infix_tokens;
        list<string> postfix_tokens;
        string exp;
    public:
        Expression() {
            precedence.insert( pair<string, int> ("^", 4) );
            precedence.insert( pair<string, int> ("/", 3) );
            precedence.insert( pair<string, int> ("*", 3) );
            precedence.insert( pair<string, int> ("+", 2) );
            precedence.insert( pair<string, int> ("-", 2) );
            precedence.insert( pair<string, int> ("(", 1) );
        }
        void Evaluate(string strexp);
        void Tokenize();
        void InfixToPostfix();
};

void Expression :: Evaluate (string strexp) {
    exp = strexp;
    cout << "Expression : " << exp << endl;
    Tokenize();
    InfixToPostfix();
}

// Tokenize individual characters into operators and operands
void Expression :: Tokenize () {

    int sz = exp.size();
    string token("");
     
    int i;
    for (i=0; i<sz-1; i++) {
  
        char p = exp.at(i);
  
        if (p == '+' or p == '-' or p == '/' or p == '*' or p == '^' or p == '(' or p == ')') {
            token = p;
            infix_tokens.push_back(token);
            token = "";
        } else {
            token += p;
            if (!(exp.at(i+1) >= '0' and exp.at(i+1) <= '9')) { 
                infix_tokens.push_back(token);
                token = "";
            }
        }
    }

    if (exp.at(i) >= '0' and exp.at(i) <= '9') {
        token += exp.at(sz-1);
    } else {
        token = exp.at(sz-1);
    }
    infix_tokens.push_back(token);
}

void Expression :: InfixToPostfix () {

    stack<string> stk;
    stk.push("(");
    infix_tokens.push_back(")");

    while (!infix_tokens.empty()) {

        string token = infix_tokens.front();
        infix_tokens.pop_front();

        if (token == "(") {
            stk.push(token);
        } else if (token == ")") {

            // Pop out all the operators and append them to postfix expression till an opening bracket is found
            while (stk.top() != "(") {
                postfix_tokens.push_back(stk.top());
                stk.pop();
            }
            stk.pop();

        } else if (token == "*" or token == "/" or token == "+" or token == "-" or token == "^") {

            // Pop out operators with higher precedence at the top of the stack and append them to 
            // the postfix expression, before pushing the current operator to the stack.
            while (!stk.empty() and precedence[stk.top()] >= precedence[token]) {
                postfix_tokens.push_back(stk.top());
                stk.pop();
            }
            stk.push(token);

        } else { 
            // Positions of the operands do not change in the postfix expression so append
            // an operand as it is.
            postfix_tokens.push_back(token);
        }
    }
   
    cout << "Postfix Expression :";
    for (auto &i  : postfix_tokens)
        cout << i << ",";
    cout << endl << endl;
 
    postfix_tokens.clear();
}

int main() {

    string strexp1 ("110+50"); // => 160
    string strexp2 ("110+50+(4-2*5)-10+40"); // => 184
    string strexp3 ("(110+50)*(2-4)"); //=> -320
    string strexp4 ("2^5*(3-4)"); // => -32
    string strexp5 ("2^5"); // => 32
    string strexp6 ("0-8-0-5^3"); // => -133

    Expression e;
    e.Evaluate (strexp1);
    e.Evaluate (strexp2);
    e.Evaluate (strexp3);
    e.Evaluate (strexp4);
    e.Evaluate (strexp5);
    e.Evaluate (strexp6);

    return 0;
}

Output showing an infix expression converted to a postfix expression

Expression : 110+50
Postfix Expression :110,50,+,

Expression : 110+50+(4-2*5)-10+40
Postfix Expression :110,50,+,4,2,5,*,-,+,10,-,40,+,

Expression : (110+50)*(2-4)
Postfix Expression :110,50,+,2,4,-,*,

Expression : 2^5*(3-4)
Postfix Expression :2,5,^,3,4,-,*,

Expression : 2^5
Postfix Expression :2,5,^,

Expression : 0-8-0-5^3
Postfix Expression :0,8,-,0,-,5,3,^,-,

Copyright © 2019-2020, Algotree.org.
All rights reserved.