In expression evaluation problem, we have given a string s of length n representing an expression that may consist of integers, balanced parentheses, and binary operations ( +, -, *, / ). Evaluate the expression. An expression can be in any one of prefix, infix, or postfix notation.
Table of Contents
Example
See few examples for expression evaluation:
Input : s = “100 * ( 2 + 12 )”
Output : 1400
Input : s = “10 + 2 * 6”
Output : 22
Algorithm for Expression Evaluation
Now we know the problem statement for expression evaluation. So, without wasting our time we move towards algorithm uses for the solution of expression evaluation.
- Initialize a string s of length n consisting of expression.
- Create one stack to store values and other to store operators.
- Traverse through the string and check if the current character is a white space continue the loop. Else if it is an opening parenthesis push it in a stack of operators.
- Else if the current character is a digit. Initialize a integer val as 0. Traverse from the current position + 1 till the end of the string while the current character is a digit and update the val as val * 10 + current digit. Push it in the stack of values.
- Else if it is a closing parenthesis, traverse while the stack of operators is not empty and current character in it is not an opening parenthesis.
- Pop the top 2 digits from the stack of values and an operator from operator stack. Perform the arithmetic operation and push the result in a stack of values.
- While the operator’s stack is not empty, pop the top 2 digits from the stack of values and an operator from operator stack. Perform the arithmetic operation and push the result in a stack of values.
- Return the top of the stack of values.
C++ Program for Expression Evaluation
#include <bits/stdc++.h>
using namespace std;
int precedence(char op){
if(op == '+'||op == '-')
return 1;
if(op == '*'||op == '/')
return 2;
return 0;
}
int applyOp(int a, int b, char op){
switch(op){
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
}
}
int evaluate(string tokens){
int i;
stack <int> values;
stack <char> ops;
for(i = 0; i < tokens.length(); i++){
if(tokens[i] == ' ')
continue;
else if(tokens[i] == '('){
ops.push(tokens[i]);
}
else if(isdigit(tokens[i])){
int val = 0;
while(i < tokens.length() && isdigit(tokens[i])){
val = (val*10) + (tokens[i]-'0');
i++;
}
values.push(val);
}
else if(tokens[i] == ')'){
while(!ops.empty() && ops.top() != '('){
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
if(!ops.empty())
ops.pop();
}
else{
while(!ops.empty() && precedence(ops.top()) >= precedence(tokens[i])){
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
ops.push(tokens[i]);
}
}
while(!ops.empty()){
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
return values.top();
}
int main(){
cout << evaluate("100 * ( 2 + 12 )") << endl;
return 0;
}1400
Java Program for Expression Evaluation
import java.util.Stack;
class EvaluateString{
public static int evaluate(String expression){
char[] tokens = expression.toCharArray();
Stack<Integer> values = new Stack<Integer>();
Stack<Character> ops = new Stack<Character>();
for (int i = 0; i < tokens.length; i++){
if(tokens[i] == ' ')
continue;
if(tokens[i] >= '0' && tokens[i] <= '9'){
StringBuffer sbuf = new StringBuffer();
while(i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9'){
sbuf.append(tokens[i++]);
}
values.push(Integer.parseInt(sbuf.toString()));
}
else if(tokens[i] == '(')
ops.push(tokens[i]);
else if(tokens[i] == ')'){
while (ops.peek() != '('){
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
}
ops.pop();
}
else if(tokens[i] == '+' || tokens[i] == '-' || tokens[i] == '*' || tokens[i] == '/'){
while (!ops.empty() && hasPrecedence(tokens[i], ops.peek())){
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
}
ops.push(tokens[i]);
}
}
while(!ops.empty()){
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
}
return values.pop();
}
public static boolean hasPrecedence(char op1, char op2){
if (op2 == '(' || op2 == ')')
return false;
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
return false;
else
return true;
}
public static int applyOp(char op, int b, int a){
switch (op){
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
if (b == 0)
throw new
UnsupportedOperationException("Cannot divide by zero");
return a / b;
}
return 0;
}
public static void main(String[] args){
System.out.println(EvaluateString.evaluate("100 * ( 2 + 12 )"));
}
}1400
Complexity Analysis
Time Complexity: O(n) where n is the length of the expression which we going for evaluation.
Space Complexity: O(n) as it is the space required to store the n characters.