To evaluate an infix expression, we 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
© 2019-2026 Algotree.org | All rights reserved.
This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org
"Most good programmers do programming not because they expect to get paid or get adulation by the public, but because it is fun to program. - Linus Torvalds"