We will evaluate postfix expression here. Postfix expression is also called Reverse Polish Notation. This is a common LeetCode problem “150. Evaluate Reverse Polish Notation”.
Let’s take an example & see how postfix expression works.
Input: ["6", "1", "-", "3", "*"] Output: 15
Postfix means operator comes after the two operands. If you see the above expression, “6” & “1” are the first two operands. Then we apply “-” on the two operands. We get “5” after the subtraction operation. So “5” is the new operand. Next operand is “3”. Then we get “*” as the operator. We apply multiplication on the last two operands which are “5” & “3”. We get 15 which is the final result.
If we go from left to right, we can see that we apply an operator on last two operands. So stack would be useful here. We push operands on stack. When we encounter an operator, we pop last two elements from stack & apply operator on them. We push the new value after the operation on stack as a new operand. Stack is a good choice as it is last-in first-out data structure. So it is easy to get last two operands in O(1) time.
Here is a simple diagram that illustrates the above flow.
Below you can find the working solution of the LeetCode problem in Java language. We traverse all the elements of the string array once. So time complexity in O(n). Stack push & pop operations are of O(1) or constant time complexity. So stack operations don’t add to overall time complexity. We can conclude that the overall time complexity of the below solution is O(n) which is linear.
Space complexity of the above problem might seem to be O(n). But if you see the above diagram, we can have maximum of two elements in the stack at any given moment. So stack size doesn’t depend on the input. We can conclude that space complexity of the solution is O(1) which is constant.
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<Integer>();
for(String token : tokens){
Integer current = null;
//check if current value is operand
try{
current = Integer.parseInt(token);
} catch(NumberFormatException e){
}
if(current != null){
stack.push(current);
} else{
// find last two operands
int operand2 = stack.pop();
int operand1 = stack.pop();
//apply current operator on these operands
int value = calculate(operand1, operand2, token);
stack.push(value);
}
}
return stack.pop();
}
private int calculate(int operand1, int operand2, String token){
int result = 0;
if(token.equals("+")){
result = operand1 + operand2;
} else if(token.equals("-")){
result = operand1 - operand2;
} else if(token.equals("*")){
result = operand1 * operand2;
} else if(token.equals("/")){
result = operand1 / operand2;
}
return result;
}
}