# 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 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
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) :

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)) {

} 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') ) {

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

}

void InfixToPostfix () {

Stack<String> stk = new Stack<String>();

stk.push("(");

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("(" )) {
}
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) ) {
}
stk.push(token);

} else {
// Positions of the operands do not change in the postfix expression so append
// an operand as it is.
}
}

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
``````