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”.
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:
- Exponential (^)
- Multiplication and division (* /)
- 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
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
Postfix expressions are most suitable for evaluation with the help of a 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.
The precedence of operators determines the order of evaluation in an expression.
The precedence of operators for expression evaluation using stack is given as follows:
Exponential (^)
Multiplication and division (* /)
Addition and subtraction (+ –)
Stack is the best data structure for expression evaluation.
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
Leave a Reply