Algorithm : Infix To Postfix Conversion

Infix_To_Postfix

We refer to the standard or the conventional notation of writing an expression as the infix notation. In an infix notation an operator is present between the operands, also the expression within parentheses take priority while executing the sequence of operations.
Example: 2 ^ 5 * ( 3 - 4 )

A postfix notation a.k.a 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 for converting an Infix expression to a Postfix expression. Check below example.

Step 0. Tokenize the infix expression. i.e Store each element i.e ( operator / operand / parentheses ) 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 up to 6.
Step 3. If the token equals “(”, push it onto the top of the 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 : Consider the Infix expression : 2 ^ 5 * ( 3 - 4 ) + ")". Here we are appending a “)” to the given infix expression as mentioned in the above algorithm.

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 : O ( N ), where N is the number of tokens in the infix expression.

Infix to Postfix implementation 

import tokenize
from io import StringIO
from collections import deque

class Expression :

    # Set the precedence level of the operators
    precedence = {"^" : 4,
                  "/" : 3,
                  "*" : 3,
                  "+" : 2,
                  "-" : 2,
                  "(" : 1 }

    def __init__(self, exp_str) :
        self.exp_str = exp_str
        self.infix_tokens = []
        self.postfix_tokens = []

    def Evaluate (self) :
        self.Tokenize()
        self.InfixToPostfix()

    def Tokenize (self) :

        tuplelist = tokenize.generate_tokens(StringIO(self.exp_str).readline)

        for x in tuplelist :
            if x.string :
                self.infix_tokens.append(x.string)

        print("\n\nExpression : " + self.exp_str)

    def InfixToPostfix (self) :

        stack = deque()
        stack.appendleft("(")
        self.infix_tokens.append(")")

        while self.infix_tokens :

             token = self.infix_tokens.pop(0)

             if token == "(" :
                 stack.appendleft(token)

             elif token == ")" :
                 # Pop out all the operators from the stack and append them to 
                 # postfix expression till an opening bracket "(" is found

                 while stack[0] != "(" : # peek at topmost item in the stack
                     self.postfix_tokens.append(stack.popleft())
                 stack.popleft()

             elif token == "*" or token == "/" or token == "+"\
                 or token == "-" or token == "^" :

                 # Pop out the operators with higher precedence from the top of the
                 # stack and append them to the postfix expression before
                 # pushing the current operator onto the stack.
                 while ( stack and self.precedence[stack[0]] >= self.precedence[token] ) :
                     self.postfix_tokens.append(stack.popleft())
                 stack.appendleft(token)

             else :
                 # Positions of the operands do not change in the postfix
                 # expression so append an operand as it is to the postfix expression
                 self.postfix_tokens.append(token)

        print("Postfix expression : ", end=' ')
        for token in self.postfix_tokens :
            print(token, end=', ')

def main() :
    e = Expression("110+50+(4-2*5)-10+40")
    e.Evaluate()
    e1 = Expression("0-8-0-5^3")
    e1.Evaluate()
    e2 = Expression("(110+50)*(2-4)")
    e2.Evaluate()
    e3 = Expression("110+50")
    e3.Evaluate()
    e4 = Expression("2^5")
    e4.Evaluate()

if __name__ == "__main__" :
    main()

Output

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

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

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

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

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

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

using namespace std;

class Expression {

    private:
        map<string, int> precedence; // Map for storing the precedence of operators.
        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 the current character is an operator or a bracket we store it in the 
        // token list and flush the token.
        if (p == '+' || p == '-' || p == '/' || p == '*' || p == '^' || p == '(' or p == ')') {
            token = p;
            infix_tokens.push_back(token);
            token = "";
        } else {
            token += p;
            // If the next character is not a digit, it means the number is done
            // so we push it to the token list and flush the token.
            if (!(exp.at(i+1) >= '0' && exp.at(i+1) <= '9')) { 
                infix_tokens.push_back(token);
                token = "";
            }
        }
    }

    // If the last character is a number, it means the token still contains a part of the number.
    // So we append the last character to the previously stored number in the token and thus
    // we have the complete number.
    if (exp.at(i) >= '0' && 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("("); // The extra "(" is necessary so that the popping operation doesn't go on forever.
    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 == "*" || token == "/" || token == "+" || token == "-" || 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() && 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"); // => => 110,50,+,
    string strexp2 ("110+50+(4-2*5)-10+40"); // => 110,50,+,4,2,5,*,-,+,10,-,40,+,
    string strexp3 ("(110+50)*(2-4)"); //=> 110,50,+,2,4,-,*,
    string strexp4 ("2^5*(3-4)"); // => 2,5,^,3,4,-,*,
    string strexp5 ("2^5"); // => 2,5,^,
    string strexp6 ("0-8-0-5^3"); // => 0,8,-,0,-,5,3,^,-,

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

    return 0;
}

Output

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,^,-,

import java.util.*;

class Expression {

    Map<String, Integer> precedence; // For storing the operator precedence
    List<String> infix_tokens;
    List<String> postfix_tokens;
    String exp; // For storing the infix expression

    Expression() {

            precedence = new HashMap<String, Integer>();
            precedence.put("^", 4);
            precedence.put("/", 3);
            precedence.put("*", 3);
            precedence.put("+", 2);
            precedence.put("-", 2);
            precedence.put("(", 1);

            infix_tokens = new ArrayList<String>();
            postfix_tokens = new ArrayList<String>();
    }

    void Evaluate (String strexp) {
        exp = strexp;
        System.out.println("Expression : " + exp);
        Tokenize();
        InfixToPostfix();
    }

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

        StringBuilder token = new StringBuilder("");
        int sz = exp.length();
         
        int i; 
        for (i = 0; i < sz-1; i++) {
            String p = String.valueOf(exp.charAt(i));

            if ( List.of("+", "-", "/", "*", "^", "(", ")" ).contains(p)) {
                infix_tokens.add(p);
            } else { // Character is a number

                token.append(p);
                // If the next character is not a digit, it means the number is done
                // so we push it to the token list and flush the token.
                if ( ! (exp.charAt(i+1) >= '0' && exp.charAt(i+1) <= '9') ) {
                    infix_tokens.add(token.toString());
                    token.setLength(0); // reset token
                }
            }
        }

        // If the last character is a number, it means the token still contains a part of the number.
        // So we append the last character to the previously stored number in the token and thus
        // we have the complete number.

        if ( exp.charAt(i) >= '0' && exp.charAt(i) <= '9' ) {
            token.append(exp.charAt(sz-1));
        } else {
            token.setLength(0); // reset token
            token.append(exp.charAt(sz-1));
        }
        infix_tokens.add(token.toString());
    }

    void InfixToPostfix () {

        Stack<String> stk = new Stack<String>();

        stk.push("(");
        infix_tokens.add(")");

        while ( !infix_tokens.isEmpty() ) {
            String token = infix_tokens.remove(0);
            if (token.equals("(")) {
                stk.push(token);
            } else if ( token.equals(")") ) {

                // Pop out all the operators and append them to postfix expression till an opening bracket is found
                while (!stk.peek().equals("(" )) {
                    postfix_tokens.add(stk.pop());
                }
                stk.pop();
            } else if (List.of("*", "/", "+", "-", "^").contains(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() && precedence.get(stk.peek()) >= precedence.get(token) ) {
                    postfix_tokens.add(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.add(token);
            }
        }
        System.out.print("Postfix Expression :");
        for (String tok : postfix_tokens)
            System.out.print(tok + ", ");
        System.out.println("\n");
        postfix_tokens.clear();
    }

    public static void main (String args[]) {

        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 = new Expression();
        e.Evaluate (strexp1);
        e.Evaluate (strexp2);
        e.Evaluate (strexp3);
        e.Evaluate (strexp4);
        e.Evaluate (strexp5);
        e.Evaluate (strexp6);
    }

Output

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 (c) 2019-2024, Algotree.org.
All rights reserved.