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 332 |
| 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. | -132 |
| 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
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