Expression Evaluation Using Stack

Precedence of Operators

In our school days, we read about BODMAS or PEMDAS. What exactly were those?

They were acronyms to remember the precedence of operators while solving an expression, but what is precedence?

The precedence of operators gives us an order in which operators are evaluated in any expression.

Computers have a similar idea of precedence, too, when it comes to operators. It is as follows:

1. Exponential (^)
2. Multiplication and division (* /)
3. Addition and subtraction (+ –)
    

Now we are well acquainted with all knowledge required for expression evaluation using stack. So what are we waiting for?
 

Source: giphy

Infix Expression Evaluation Using Stack

To begin with, let us see how infix expression evaluation using stack. 

Algorithm

Step 1: Create two stacks - the operand stack and the character stack.
Step 2: Push the character to the operand stack if it is an operand.
Step 3: If it is an operator, check if the operator stack is empty. 
Step 4: If the operator stack is empty, push it to the operator stack.
Step 5: If the operator stack is not empty, compare the precedence of the operator and the top character in the stack. 
If the character’s precedence is greater than or equal to the precedence of the stack top of the operator stack, then push the character to the operator stack.
Otherwise, pop the elements from the stack until the character’s precedence is less or the stack is empty.
Step 6: If the character is “(“, push it into the operator stack.
Step 7: If the character is “)”, then pop until “(” is encountered in the operator stack. 

Example

Infix expression : 2 * (5 * (3 + 6)) / 5 - 2

The final answer (here 16) is stored in the stack and is popped at the end. Now, let’s see the implementation of the above approach in JAVA. 

Code

import java.util.Stack;
public class Main
{
public int evaluate(String exp)
{
         Stack<Integer> operands = new Stack<>();  //Operand stack
         Stack<Character> operations = new Stack<>();  //Operator stack
         for(int i=0; i<exp.length();i++)
         {
             char c = exp.charAt(i);
             if(Character.isDigit(c))   //check if it is number
             {
                 //Entry is Digit, and it could be greater than a one-digit number
                 int num = 0;
                 while (Character.isDigit(c))
                 {
                           num = num*10 + (c-'0');
                           i++;
                         if(i < exp.length())
                         {
                             c = exp.charAt(i);
                         }
                         else
                         {
                             break;
                         }
                 }
                 i--;
             operands.push(num);
         }
         else if(c=='(')
         {
             operations.push(c);   //push character to operators stack
         }
         //Closed brace, evaluate the entire brace
         else if(c==')')
         {
             while(operations.peek()!='(')
             {
                     int output = performOperation(operands, operations);
                     operands.push(output);   //push result back to stack
             }
             operations.pop();
         }
        
         // current character is operator
         else if(isOperator(c))
         {
             while(!operations.isEmpty() && precedence(c)<=precedence(operations.peek()))
             {
                     int output = performOperation(operands, operations);
                     operands.push(output);   //push result back to stack
             }
               operations.push(c);   //push the current operator to stack
         }
     }
    
     while(!operations.isEmpty())
     {
         int output = performOperation(operands, operations);
         operands.push(output);   //push final result back to stack
     }
     return operands.pop();
}

static int precedence(char c)
{
         switch (c)
         {
             case '+':
             case '-':
                 return 1;
             case '*':
             case '/':
                 return 2;
             case '^':
                 return 3;
         }
         return -1;
}

public int performOperation(Stack<Integer> operands, Stack<Character> operations)
{
         int a = operands.pop();
         int b = operands.pop();
         char operation = operations.pop();
         switch (operation)
         {
             case '+':
                 return a + b;
             case '-':
                 return b - a;
             case '*':
                 return a * b;
             case '/':
                 if (a == 0)
                 {
                         System.out.println("Cannot divide by zero");
                         return 0;
                 }
                 return b / a;
         }
         return 0;
}

public boolean isOperator(char c)
{
         return (c=='+'||c=='-'||c=='/'||c=='*'||c=='^');
}

public static void main(String[] args)
{
         String infixExpression = "2 * (5 *(3+6))/5-2";
         Main obj = new Main();
         System.out.println(obj.evaluate(infixExpression));
}
}

You can also try this code with Online Java Compiler

Run Code

Output:

16

You can also visit Introduction to C# here.

Postfix Expression Evaluation Using Stack

Now that we know how to evaluate an infix expression let us move on to the next type - postfix evaluation. 

Algorithm

Here we will use only one operand stack instead of two. 

Step 1: Create an operand stack.
Step 2: If the character is an operand, push it to the operand stack.
Step 3: If the character is an operator, pop two operands from the stack, operate and push the result back to the stack.
Step 4:After the entire expression has been traversed, pop the final result from the stack. 

Example

For example, let us convert the infix expression we used into postfix for expression evaluation using stack. 

Postfix expression : 2 5 3 6 + * * 15 / 2 -

As we can see, the final answer here is also 16.

Code

import java.util.Scanner;
class Main
{
public static void main(String args[])
{
         String post = "2536+**5/2-";   //Postfix expression
         stack ob=new stack(post.length());   //Object of stack class is created
         for(int i=0;i<post.length();i++)   //Expression is traversed
         {
             char ch=post.charAt(i);
             if(ch>=48 && ch<=57)   //Checking for digit
                      ob.push(ch-48);
             else  
             {
                 //Two operands are being popped
                 int p1=ob.pop();  
                 int p2=ob.pop();
                 switch(ch)
                 {
                           case '+':
                             p1=p2+p1;
                             break;
                           case '-':
                             p1=p2-p1;
                             break;
                           case '*':
                             p1=p2*p1;
                             break;
                           case '/':
                                if (p1 == 0)
                           {
                                   System.out.println("Cannot divide by zero");
                                   break;
                           }
                             p1=p2/p1;
                             break;
                           case '^':
                             p1=(int)Math.pow(p2, p1);
                 }
                 ob.push(p1);  //Result is pushed to stack
             }
         }
         System.out.println(ob.pop());  //Final result is popped and printed
}
}

class stack
{
int st[];
int top;
stack(int n)
{
         st=new int[n];   //Stack is created
         top=-1;
}
boolean isfull()
{
         if(top==st.length-1)
             return true;
         else
             return false;
}
boolean isempty()
{
         if(top==-1)
         return true;
     else
         return false;
}
void push(int n)
{
         st[++top]=n;
}
int pop()
{
         return st[top--];
}
void display()
{
         for(int i=top;i>=0;i--)
          System.out.print(st[i]+" ");
}
}

You can also try this code with Online Java Compiler

Run Code

Output:

16

Prefix Expression Evaluation

The last kind of expression we are left to discuss is a prefix expression. Let us see how we’ll evaluate it.

Algorithm

Understanding the algorithm to evaluate a prefix expression will be very easy since we already know how to evaluate a postfix expression.

Here, we will first reverse the prefix expression, and the rest of the algorithm is the same as that for a postfix expression. 

Step 1: Reverse the postfix expression.
Step 2: Create an operand stack.
Step 3: If the character is an operand, push it to the operand stack.
Step 4: If the character is an operator, pop two operands from the stack, operate and push the result back to the stack.
Step 5:After the entire expression has been traversed, pop the final result from the stack.

Example

Let us again convert the infix expression from our first example to a prefix expression to evaluate it.

Prefix expression: - / * 2 * 5 + 3 6 5 2

Reversed prefix expression: 2 5 6 3 + 5 * 2 * / -

Code

import java.util.Stack;
public class Main
{
public static Double perform(double a, double b, char operator)  //Method to perform operations
{
         switch (operator)
         {
             case '+':
                 return a + b;
             case '-':
                 return b - a;
             case '*':
                 return a * b;
             case '/':
                 if(a == 0)
                 {
                         System.out.println("Cannot divide by zero");
                         return 0.0;
                 }
                 return(b/a);
         }
         return 0.0;
}
public static Double convert(String expression)  //Method to evaluate the prefix expression
{
         Stack<Double> stack = new Stack<>();
         StringBuilder input = new StringBuilder(expression);
         input.reverse();   //Prefix expression is reversed
         for (int i = 0; i < input.length(); i++)   //Traverses through the expression
         {
             char c = input.charAt(i);
             if (c == '*' || c == '/' || c == '^' || c == '+' || c == '-')   //Character is an operator
             {
                 //Operands popped
                 double s1 = stack.pop();  
                 double s2 = stack.pop();
                 double temp = perform(s2, s1, c);   //Statement is evaluated
                 stack.push(temp);   //Result is pushed to stack
             }
             else
             {
                 stack.push((double) (c-'0'));   //Operand is pushed to stack
             }
         }
         double result = stack.pop();   //Final result is popped
         return result;
}

public static void main(String[] args)
{
         String exp = "-/*2*5+3652";     
         System.out.println(convert(exp));
}
}

You can also try this code with Online Java Compiler

Run Code

Output:

16.0

We discussed three different methods to evaluate infix, postfix and prefix operations. So you may be wondering whether we have to know them all. 

Well, lucky for us, we don’t, but how? 

We can use our prior knowledge on infix, postfix and prefix conversions to convert any given expression to the desired type, suppose postfix. Then, since we know the algorithm for postfix evaluation, we can quickly write the code to solve any expression. You can try to solve any expression using that method here.

Before concluding, let us go through some common questions asked on evaluating expressions using a stack. 

Must Read Stack Operations

Frequently Asked Questions

Which expression is most suitable for evaluating using stack?

Postfix expressions are most suitable for evaluation with the help of a stack.

Why do we convert infix expressions to postfix or prefix?

Infix expressions are easily understandable and solvable by only humans and not computers. A computer cannot easily differentiate between operators and parentheses, so infix expressions are converted into postfix or prefix.

What determines the order of evaluation in an expression?

The precedence of operators determines the order of evaluation in an expression.

What is the precedence of operators?

The precedence of operators  for expression evaluation using stack is given as follows:
Exponential (^)
Multiplication and division (* /)
Addition and subtraction (+ –)

What is the best data structure for the evaluation of expressions?

Stack is the best data structure for expression evaluation.

How many stacks are required to evaluate infix, postfix and prefix expressions?

To evaluate infix expressions, we need two stacks (operator and operand stack), and to evaluate postfix and prefix expressions, we need only one stack (operand stack).

Conclusion

With the end of this article, we now know different methods for expression evaluation using stack. 

We are now one step closer to a job in our dream company, but to make our dream seem even more realistic, we need to practice more coding questions asked in interviews. Coding Ninjas Studio is a platform where we can find such questions, interview experiences of people from renowned companies and lots more. You can also consider our Mern Stack Course to give your career an edge over others.

Happy Learning!