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 between ( 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 operation ( y operator x ) into the stack.
Step 4. Element at the top of the stack is the result of the evaluation.
Example : Consider the 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. | -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