CSInterviewing
Problems
Register
Login
Problems
Register
Login
menu
Evaluate Reverse Polish Notation
stack
math
# Evaluate Reverse Polish Notation ## Difficulty Medium ## Tags `stack`, `math` ## Problem Statement Evaluate the value of an arithmetic expression in Reverse Polish Notation (Postfix notation). Valid operators are `+`, `-`, `*`, `/`. Each operand may be an integer or another expression. **Note:** - Division between two integers truncates toward zero. - The given expression is always valid. - No division by zero will occur. ## Constraints - 1 ≤ tokens.length ≤ 10⁴ - tokens[i] is either an operator or an integer in range [-200, 200] ## Signatures ### Python ```python def eval_rpn(tokens: List[str]) -> int: pass ``` ### Java ```java public class Solution { public int eval_rpn(List<String> tokens) { return null; } } ``` ### Csharp ```csharp public class Solution { public int eval_rpn(IList<string> tokens) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int eval_rpn(vector<string> tokens) { } }; ``` ### C ```c int eval_rpn(vector<char*> tokens) { } ``` ### Ruby ```ruby def eval_rpn(tokens) end ``` ### Perl ```perl sub eval_rpn { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def eval_rpn(tokens: List[String]): Int = { } } ``` ### Haskell ```haskell eval_rpn :: ... -> ... eval_rpn args = undefined ``` ### Clojure ```clojure (defn eval_rpn [tokens] ) ``` ### Scheme ```scheme (define (eval_rpn tokens) ) ``` ## Examples ### 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)) = 4 + 2 = 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 = 22 ## Hints 1. Use a stack to store operands. 2. When you encounter a number, push it onto the stack. 3. When you encounter an operator, pop two numbers, apply the operator, push the result. 4. Be careful with order: for subtraction and division, the second popped value is the left operand. 5. For Python, use `int(a / b)` to truncate toward zero (not `//`).
Login required
Please log in to view the solution editor and submit code.
Login
Register