Expression Evaluation

Difficulty Level Medium
Frequently asked in Amazon Oracle
Math StackViews 6736

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.

Expression Evaluation

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.

  1. Initialize a string s of length n consisting of expression.
  2. Create one stack to store values and other to store operators.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.

References

Translate »