Expression Evaluation Using Stack

Expression Evaluation Using Stack
Expression Evaluation Using Stack

Introduction

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

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 (+ –)
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

CharacterActionOperand StackOperator Stack
2Push to the operand stack2
*Push to the operator stack2*
(Push to the operator stack2( *
5Push to the operand stack5 2 ( *
*Push to the operator stack5 2 * ( *
(Push to the operator stack2 1( * ( *
3Push to the operand stack3 5 2 ( * ( *
+Push to the operator stack3 2 1+ ( * ( *
6Push to the operand stack6 3 5 2 + ( * ( *
)Pop 6 and 35 2 + ( * ( *
Pop +5 2 ( * ( *
6 + 3 = 9, push to operand stack9 5 2 ( * ( *
Pop (9 5 2 * ( *
)Pop 9 and 52* ( *
Pop *2( *
9 * 5 = 45, push to operand stack45 2( *
Pop (45 2*
/Push to the operator stack45 2/ *
5Push to the operand stack5 45 2/ *
Pop 5 and 452/ *
Pop /2*
45/5 = 9, push to the operand stack9 2*
Pop 9 and 2*
Pop *
9 * 2 = 18, push to operand stack18
Push – to the operator stack18
2Push to the operand stack2 18
Pop 2 and 18
Pop –
18 – 2 = 16, push to operand stack16

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 –

CharacterActionOperand Stack
2Push to the operand stack2
5Push to the operand stack5 2
3Push to the operand stack3 5 2
6Push to the operand stack6 3 5 2 
+Pop 6 and 3 from the stack5 2 
6 + 3 = 9, push to operand stack9 5 2
*Pop 9 and 5 from the stack2
9 * 5 = 45, push to operand stack45 2 
*Pop 45 and 2 from the stack
45 * 2 = 90, push to stack90 
5Push to stack5 90
/Pop 15 and 90 from the stack
90 / 5 = 18, push to stack18
2Push to the stack2 18
Pop 2 and 18 from the stack
18 – 2 = 16, push to stack16

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

CharacterActionOperand Stack
2Push to the operand stack2
5Push to the operand stack5 2
6Push to the operand stack6 5 2
3Push to the operand stack3 6 5 2 
+Pop 3 and 6 from the stack5 2 
3 + 6 = 9, push to operand stack9 5 2
5Push to the operand stack5 9 5 2
*Pop 5 and 9 from the stack5 2
5 * 9 = 45, push to operand stack45 5 2 
2Push to operand stack2 45 5 2
*Pop 2 and 45 from the stack5 2
2 * 45 = 90, push to stack90 5 2
/Pop 90 and 5 from the stack2
90 / 5 = 18, push to stack18 2
Pop 18 and 2 from the stack
18 – 2 = 16, push to stack16

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.

Which expression is most suitable for evaluating using stack?

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).

Key Takeaways

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!

By: Neelakshi Lahiri

Exit mobile version