Update appNew update is available. Click here to update.

Expression Evaluation Using Stack

Kushleen Waraich
Last Updated: Sep 2, 2022
MEDIUM
Stack

Introduction

Do you remember the questions in our school exams where we evaluated an infix, postfix or prefix expression?

gif


Source: giphy

The only thing we could wish for then is a computer program that would directly give us the answer on entering the expression as input. 

Well, guess what?
A common question in the coding rounds of interviews is to write a program for “Expression evaluation using Stack”. 

In this article, we will learn how to solve that question. 

Infix, Postfix and Prefix Expressions

Before we start writing the code for expression evaluation using stack, let us have a quick recap of the different kinds of expressions, namely, infix, postfix and prefix,  we’ll be solving. 

Infix Expressions

The usual expressions which we encounter are infix expressions. 

For example, 

(A + B) * C / D - E

Postfix Expressions

In postfix expressions, the operators are written after the operands as shown below:

A B C + * D /

Prefix Expressions

Here, the operators are written before the operands. An example is,

/ * A + B C D

Now that we know what expressions we’re dealing with, solving them will be even easier. Before moving on to evaluation, there is one more thing we need to learn - the precedence of operators.

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?
 

gif

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

Character

Action

Operand Stack

Operator Stack

2

Push to the operand stack

2

 

*

Push to the operator stack

2

*

(

Push to the operator stack

2

( *

5

Push to the operand stack

5 2 

( *

*

Push to the operator stack

5 2 

* ( *

(

Push to the operator stack

2 1

( * ( *

3

Push to the operand stack

3 5 2 

( * ( *

+

Push to the operator stack

3 2 1

+ ( * ( *

6

Push to the operand stack

6 3 5 2 

+ ( * ( *

)

Pop 6 and 3

5 2 

+ ( * ( *

 

Pop +

5 2 

( * ( *

 

6 + 3 = 9, push to operand stack

9 5 2 

( * ( *

 

Pop (

9 5 2 

* ( *

)

Pop 9 and 5

2

* ( *

 

Pop *

2

( *

 

9 * 5 = 45, push to operand stack

45 2

( *

 

Pop (

45 2

*

/

Push to the operator stack

45 2

/ *

5

Push to the operand stack

5 45 2

/ *

-

Pop 5 and 45

2

/ *

 

Pop /

2

*

 

45/5 = 9, push to the operand stack

9 2

*

 

Pop 9 and 2

 

*

 

Pop *

  
 

9 * 2 = 18, push to operand stack

18

 
 

Push - to the operator stack

18

-

2

Push to the operand stack

2 18

-

 

Pop 2 and 18

 

-

 

Pop -

  
 

18 - 2 = 16, push to operand stack

16

 

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


Output:

16

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 -

Character

Action

Operand Stack

2

Push to the operand stack

2

5

Push to the operand stack

5 2

3

Push to the operand stack

3 5 2

6

Push to the operand stack

6 3 5 2 

+

Pop 6 and 3 from the stack

5 2 

 

6 + 3 = 9, push to operand stack

9 5 2

*

Pop 9 and 5 from the stack

2

 

9 * 5 = 45, push to operand stack

45 2 

*

Pop 45 and 2 from the stack

 
 

45 * 2 = 90, push to stack

90 

5

Push to stack

5 90

/

Pop 15 and 90 from the stack

 
 

90 / 5 = 18, push to stack

18

2

Push to the stack

2 18

-

Pop 2 and 18 from the stack

 
 

18 - 2 = 16, push to stack

16

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]+" ");
}
}


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 * / -

Character

Action

Operand Stack

2

Push to the operand stack

2

5

Push to the operand stack

5 2

6

Push to the operand stack

6 5 2

3

Push to the operand stack

3 6 5 2 

+

Pop 3 and 6 from the stack

5 2 

 

3 + 6 = 9, push to operand stack

9 5 2

5

Push to the operand stack

5 9 5 2

*

Pop 5 and 9 from the stack

5 2

 

5 * 9 = 45, push to operand stack

45 5 2 

2

Push to operand stack

2 45 5 2

*

Pop 2 and 45 from the stack

5 2

 

2 * 45 = 90, push to stack

90 5 2

/

Pop 90 and 5 from the stack

2

 

90 / 5 = 18, push to stack

18 2

-

Pop 18 and 2 from the stack

 
 

18 - 2 = 16, push to stack

16

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


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. 

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. CodeStudio is a platform where we can find such questions, interview experiences of people from renowned companies and lots more. 

Happy Learning!

Was this article helpful ?
0 upvotes