Evaluate Reverse Polish Notation
Clarify the problem:
- The problem requires us to evaluate an arithmetic expression in Reverse Polish Notation (RPN).
- Reverse Polish Notation is a mathematical notation in which every operator follows all of its operands.
- We need to implement a function that takes an RPN expression as input and returns the result of evaluating that expression.
Analyze the problem:
- Input: A list of strings representing the RPN expression.
- Output: The result of evaluating the RPN expression.
- Constraints:
- The given RPN expression is always valid and contains only integers and operators.
- The operators include "+", "-", "*", and "/".
- Division between two integers should truncate toward zero.
Design an algorithm:
- We can use a stack to evaluate the RPN expression.
- Iterate through each element in the input list:
- If the element is an operator, pop the last two operands from the stack, perform the operation, and push the result back to the stack.
- If the element is an operand, convert it to an integer and push it to the stack.
- At the end, the stack should contain only one element, which is the final result of the RPN expression.
Explain your approach:
- We will implement a function called
evalRPN
to solve the problem. - The function will take a list of strings representing the RPN expression as input.
- We will use a stack to store the intermediate results.
- We iterate through each element in the input list and handle operators and operands accordingly.
- After iterating through all elements, the stack should contain the final result, which we will return.
- We will implement a function called
Write clean and readable code:
pythondef evalRPN(tokens): stack = [] operators = {"+", "-", "*", "/"} for token in tokens: if token in operators: operand2 = stack.pop() operand1 = stack.pop() if token == "+": result = operand1 + operand2 elif token == "-": result = operand1 - operand2 elif token == "*": result = operand1 * operand2 elif token == "/": result = int(operand1 / operand2) stack.append(result) else: stack.append(int(token)) return stack[0]
Test your code:
pythonprint(evalRPN(["2", "1", "+", "3", "*"])) # Output: 9 print(evalRPN(["4", "13", "5", "/", "+"])) # Output: 6 print(evalRPN(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])) # Output: 22
Explanation:
- We test the solution with different RPN expressions to verify its correctness.
- In the first test case, the RPN expression is "2 1 + 3 *", which can be evaluated as (2 + 1) * 3 = 9.
- In the second test case, the RPN expression is "4 13 5 / +", which can be evaluated as 4 + (13 / 5) = 6.
- In the third test case, the RPN expression is "10 6 9 3 + -11 * / * 17 + 5 +", which can be evaluated as 10 * ((6 / (9 + 3)) * -11) + 17 + 5 = 22.
Optimize if necessary:
- The solution does not require further optimization as it already solves the problem efficiently.
Handle error cases:
- The code assumes that the input follows the problem constraints and does not explicitly handle invalid input cases, such as empty input or invalid RPN expressions. Handling such cases can be added to the code as needed.
Discuss complexity analysis:
- Let N be the length of the input list (number of tokens).
- The algorithm iterates through each token in the input list, resulting in a time complexity of O(N).
- The space complexity is O(N) as well since we use a stack to store the intermediate results.