In this article, we have explained how an Arithmetic Expression (like 2 * 3 + 4) is evaluated using Stack. We have presented the algorithms and time/ space complexity.

Table of content:

1. Introduction to Arithmetic expressions
2. Algorithm to evaluate Arithmetic expression
3. Step by Step Example
4. Implementation
5. Time & Space complexity

We will dive directly into the problem now.

Introduction to Arithmetic expressions

Arithmetic expressions can be represented in 3 forms:

1. Infix notation
2. Postfix notation (Reverse Polish Notation)
3. Prefix notation (Polish Notation)

Infix Notation is of the form operand1 operator operator2.
Eg: 5 + 3
Postfix Notation can be represented as operand1 operand2 operator.
Eg: 5 3 +
Prefix notation can be represented as operator operand1 operand2.
Eg: + 5 3
We use the infix notation most frequently in our day to day tasks. However, machines find infix notations tougher to process than prefic/postfix notations. Hence, compilers convert infix notations to prefix/postfix before the expression is evaluated.

The precedence of operators needs to be taken case of:

Exponentiation(^) > 
        Multiplication( * ) or Division(/) > 
        Addition(+) or Subtraction(-)

Brackets have the highest priority and their presence can override the precedence order.

To evaluate an infix expression, We need to perform 2 main tasks:

1. Convert infix to postfix
2. Evaluate postfix
   Let's discuss both the steps one by one.
   For step 1, Refer this article on converting infix to postfix expression using Stack.
   Once the expression is converted to postfix notation, step 2 can be performed:

Algorithm to evaluate Arithmetic expression

Steps:

1. Traverse the expression:
   1.1 If the character is an operand, push it into the stack.
   1.2 If the character is an operator, pop the 2 top most elements from the stack and perform the operation. Push the result back to the stack.
2. Once the expression is fully traversed, the element in the stack is the result.

Step by Step Example

Given expression is: 5 + 3 * 7.
Step 1 is to change this infix expression to postfix: 5 3 7 * +
Step 2: Stack S = [], traverse the string:
5 : Operand, push into the stack, S = [5], top = 5
3 : Operand, push into the stack, S = [5, 3], top = 3
7 : Operand, push into the stack, S = [5, 3, 7], top = 7
* : Operator, pop top two elements, op1 = 7, op2 = 3. Stack after pop operations S = [5], top = 5. Now, we push the result of op1 * op2, i.e 7 * 3 = 21 into the stack. S = [5, 21], top = 21
+ : Operator, pop top two elements, op1 = 21, op2 = 5. Stack after pop operations S = []. Push the result of op1 + op2 into the stack, i.e 21 + 5 = 26, S = [26]

The string has been completely traversed, the stack contains only 1 element which is the result of the expression = 26.

Implementation

Implementation in Java:

    public static int postfixEval(String str)
    {
        Stack<Integer> st = new Stack<>();
        for(int i=0;i<str.length();i++)
        {
            char x = str.charAt(i);
            if(x >= '0' && x <= '9')
            {
                st.push(Character.getNumericValue(str.charAt(i)));
            }
            else
            {
                int op1 = st.pop();
                int op2 = st.pop();
                switch(x)
                {
                    case '+' : st.push(op2 + op1);
                                break;
                    case '-' : st.push(op2 - op1);
                                break;
                    case '*' : st.push(op2 *  op1);
                                break;
                    case '/' : st.push(op2 / op1);
                                break;
                }
            }
        }
        return st.pop();
    }

Implementation in C++:

    int postfix_eval(string str)
    {
        stack<int> st;
        for(int i=0;i<str.length();i++)
        {
            char x = str[i];
            if(isdigit(x))
            {
                st.push(x - '0');
            }
            else
            {
                int op1 = st.pop();
                int op2 = st.pop();
                switch(x)
                {
                    case '+' : st.push(op2 + op1);
                                break;
                    case '-' : st.push(op2 - op1);
                                break;
                    case '*' : st.push(op2 *  op1);
                                break;
                    case '/' : st.push(op2 / op1);
                                break;
                }
             }
          }
          return st.pop();
      }

Time & Space complexity

Time complexity: O(N)

We traverse the entire string exactly once. Also, we perform a maximum of 2n push/pop operations, which means that an element goes into the stack and comes out of the stack(2n operations for n elements). This results in a time complexity of O(n).

Space complexity: O(N)

We use an auxiliary stack which can contain a maximum of N/2 elements. Hence, the space complexity of the algorithm is O(N).

With this article at OpenGenus, you must have the complete idea of Arithmetic Expression Evaluation using Stack.