Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Note:
- Division between two integers should truncate toward zero.
- The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.
Example 1:
Input: ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: ["4", "13", "5", "/", "+"] Output: 6 Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: ["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
Solution: Stack
Use a stack to store the operands, pop two whenever there is an operator, compute the result and push back to the stack.
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> s; for (const string& token : tokens) { if (isdigit(token.back())) { s.push(stoi(token)); } else { int n2 = s.top(); s.pop(); int n1 = s.top(); s.pop(); int n = 0; switch (token[0]) { case '+': n = n1 + n2; break; case '-': n = n1 - n2; break; case '*': n = n1 * n2; break; case '/': n = n1 / n2; break; } s.push(n); } } return s.top(); } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
# Author: Huahua class Solution: def evalRPN(self, tokens: List[str]) -> int: s = [] for token in tokens: if token[-1] not in '+-*/': s.append(int(token)) else: n2 = s.pop() n1 = s.pop() if token == '+': n = n1 + n2 elif token == '-': n = n1 - n2 elif token == '*': n = n1 * n2 elif token == '/': n = int(n1 / n2) s.append(n) return s[-1] |
Just for fun, f-string with eval
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 |
# Author: Huahua class Solution: def evalRPN(self, tokens: List[str]) -> int: s = [] for token in tokens: if token[-1] not in '+-*/': s.append(int(token)) else: n2 = s.pop() n1 = s.pop() s.append(int(eval(f'{n1}{token}{n2}'))) return s[-1] |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment