Algorithm : Evaluating an infix expression

To evaluate an infix expression, the idea is to do the following.
Step 1. Tokenize the infix expression and store the tokens inside a list / queue.
Step 2. Convert the infix expression into a postfix expression.
Step 3. Evaluate the postfix expression.

For Step 1 and Step 2 refer: Infix to Postfix conversion


Step 3
Algorithm : Evaluating the postfix expression

Step 1. For each element ( operator or operand ) of tokenized postfix expression stored in the list/queue do
            Step 2 and Step 3.
Step 2. If the token is an operand i.e a number (0..9) push it into the stack.
Step 3. Else i.e if the token is an operator ( ‘+’, ‘-’, ‘^’, ‘*’, ‘/’ ) pop the top two elements from the stack
            x = element at top and y = element below the top element.
            push result of y operator x into the stack.
Step 4. Element at the top of the stack is the result of the evaluation.


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

Steps Postfix Token Stack Content
1. [ 2 ]
Push 2 on the stack.
2
2. [ 5 ]
Push 5 on the stack.
5
2
3. [ ^ ]
1. Pop out 5 from the stack.
2. Pop out 2 from the stack.
3. Evaluate 2^5 and push the result i.e 32 on the stack.
32
4. [ 3 ]
Push 3 on the stack.
3
32
5. [ 4 ]
Push 4 on the stack.
4
3
32
6. [ - ]
1. Pop out 4 from the stack.
2. Pop out 3 from the stack.
3. Evaluate 3-4 and push the result i.e -1 on the stack.
-1
32
7. [ * ]
1. Pop out -1 from the stack.
2. Pop out 32 from the stack.
3. Evaluate 32 * ( -1 ) and push the result on the stack.
-32

Infix Result: -32

Time complexity : O ( N ), where N is the number of tokens in the infix expression.



Program to evaluate an infix expression

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()
        self.EvaluatePostfix()

    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("\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 EvaluatePostfix(self) :

        stack_result = deque()
    
        while self.postfix_tokens :
            token = self.postfix_tokens.pop(0)

            if token.isdigit() :
               stack_result.appendleft(float(token))
            else :
               x = float(stack_result.popleft())
               y = float(stack_result.popleft())

               # Note the order of operands(x, y), result equals [y(operator)x]
               if (token == "+") :
                   stack_result.appendleft(float(y+x))
               elif (token == "-") :
                   stack_result.appendleft(float(y-x))
               elif (token == "*") :
                   stack_result.appendleft(float(y*x))
               elif (token == "/") :
                   stack_result.appendleft(float(y/x))
               elif (token == "^") :
                   stack_result.appendleft(float(pow(y,x)))
    
        print("\n"+self.exp_str + " = " + str(stack_result.popleft()))

def main() :
    e = Expression("110+50") # 160
    e.Evaluate()
    e0 = Expression("110+50+(4-2*5)-10+40") # 184
    e0.Evaluate()
    e1 = Expression("0-8-0-5^3") # -133
    e1.Evaluate()
    e2 = Expression("(110+50)*(2-4)") # -320
    e2.Evaluate()
    e3 = Expression("2^5") #132
    e3.Evaluate()
   
if __name__ == "__main__" :
    main()

Output

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

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

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

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

Expression : 2^5
Postfix expression :  2,5,^,
2^5 = 32.0
#include<iostream>
#include<stack>
#include<string>
#include<list>
#include<cmath>
#include<sstream>
#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 EvaluatePostfix();
};

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

// 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 the 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;
}

void Expression :: EvaluatePostfix () {

    stack<int> stk_result;

    while (!postfix_tokens.empty()) {

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

        if (token.at(0) >= '0' and token.at(0) <= '9') {  
            stringstream ss(token);
            int n;
            ss >> n;
            stk_result.push(n);
        } else {
            int x = stk_result.top();
            stk_result.pop();
            int y = stk_result.top();
            stk_result.pop();
             
            // Note the order of operands(x, y), result equals [y(operator)x]
            if (token == "+") {
               stk_result.push( y + x );
            } else if (token == "-") {
               stk_result.push( y - x );
            } else if (token == "*") {
               stk_result.push( y * x );
            } else if (token == "/") {
               stk_result.push( y / x );
            } else if (token == "^") {
               stk_result.push(pow(y, x));
            }
        }
    } 
    cout << exp << " = " << stk_result.top() << endl << endl;
    stk_result.pop();
}

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

Expression : 110+50
Postfix Expression :110,50,+,
110+50 = 160

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

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

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

Expression : 2^5
Postfix Expression :2,5,^,
2^5 = 32

Expression : 0-8-0-5^3
Postfix Expression :0,8,-,0,-,5,3,^,-,
0-8-0-5^3 = -133
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("\n\nExpression : " + exp);
        Tokenize();
        InfixToPostfix();
        EvaluatePostfix();
    }

    // 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 another number, then we have got our token
                if ( ! (exp.charAt(i+1) >= '0' && exp.charAt(i+1) <= '9') ) {

                    infix_tokens.add(token.toString());
                    token.setLength(0); // reset token
                }
            }
        }

        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");
     
    }

    void EvaluatePostfix () {

        Stack<Integer> stk_result = new Stack<Integer>();

        while (!postfix_tokens.isEmpty()) {

            String token = postfix_tokens.remove(0);

            if (token.charAt(0) >= '0' && token.charAt(0) <= '9') {
                stk_result.push(Integer.parseInt(token));
            } else {
                int x = stk_result.pop();
                int y = stk_result.pop();
                 
                // Note the order of operands(x, y), result equals [y(operator)x]
                if (token.equals("+")) {
                   stk_result.push( y + x );
                } else if (token.equals("-")) {
                   stk_result.push( y - x );
                } else if (token.equals("*")) {
                   stk_result.push( y * x );
                } else if (token.equals("/")) {
                   stk_result.push( y / x );
                } else if (token.equals("^")) {
                   stk_result.push((int)Math.pow(y, x));
                }
            }
        } 
        System.out.print("\n" + exp + " = " + stk_result.pop());
    }

    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, +, 
110+50 = 160

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

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

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

Expression : 2^5
Postfix Expression :2, 5, ^, 
2^5 = 32

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



Copyright (c) 2019-2021, Algotree.org.
All rights reserved.