Evaluate Reverse Polish Notation
In this tutorial, we are going to solve a leetcode problem, Evaluate Reverse Polish Notation in Python.
Task:
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.
Example 1:
Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: 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 <= 104
- tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].
Solution:
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for item in tokens:
if item not in '+-/*':
stack.append(int(item))
else:
m, n = stack.pop(), stack.pop()
if item == '+':
o = n + m
elif item == '-':
o = n - m
elif item == '*':
o = n * m
else:
o = int(n / m)
stack.append(o)
return stack.pop()
Steps:
step1: In this problem, we will approach polish notations in a stack.
step2: First, we declare an empty stack.
step3: Now, we loop into the tokens list & check if item is not from "+-*/" if it isn't then we append the int() value into the stack.
step4: If the item is from "+-*/" then we first pop the 2 elements from the stack and store it into variables m and n.
step5: Now, we added some if-else statements to check if the item is one of the from "+-*/", then we evaluate and store the value into variable o.
step6: Now, after the if-else, we append the variable o into the stack and continue the iteration and after the loop, we return stack.pop() as only one element would be in the stack and that is the final answer.
