Swift Leetcode Series: Evaluate Reverse Polish Notation
Stacks + Expressions = Leetcode 150 🚀 🚀 🚀
Read the full story on The Swift Nerd blog with the link above.
Problem Description
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, and /. Each operand may be an integer or another expression.
Note that division between two integers should truncate toward zero.
It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.
Examples
Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
Constraints
1 <= tokens.length <= 104tokens[i]is either an operator:"+","-","*", or"/", or an integer in the range[-200, 200].
Solution
We can immediately think of a brute force approach where we can keep evaluating result on the fly. However, the problem arises when there is a nested expression where we need to backtrack. For example:
Input : ["4","13","5","/","+"]
Result : (4 + (13 / 5)) = 6In such cases, we will might have to track back the whole array in reverse which would increase its complexity to O(N2). We need to come up with a better approach.
If you know about history of reverse polish notation, it was designed specifically to make computing easier with the more efficient use of a stack. Using the stack would enable us to get the last two operands and easily store the resultant value for future calculations. Since it is given that input would always be a valid reverse polish expression, hence we would always have at least two operands before any operator(+ / — *). One more thing to note is that in case of / and -, the order of the operands matters. So if input is 3 2 –, then result should be 3–2 and not 2–3. We can ensure this by using the top of the stack as second operand and value popped after it as the first operand. We also need to push the result back into the stack and ultimately the final result would be left on the stack which we can return.
Complexity Analysis
We are iterating linearly on the input array and popping last two elements in case we encounter an operator which is O(1) operation. Hence, it is a O(N) algorithm. For space, we are using a stack which in the worst case, would contain all the elements at once.
Time = O(N)
Space = O(N)
Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!
You can find me on TheSwiftNerd | LinkedIn | Github
