# 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?

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

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

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

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 –

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

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

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

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