Evaluating an infix expression

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


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 of evaluating an infix expression after getting it converted to a postfix expression
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 of evaluating an infix expression : O(N), where N is the number of tokens in the infix expression.


Python

Python : Implementation of evaluation of an infix expression in Python 3


C++ : Implementation of evaluation of an infix expression in C++14

#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

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