Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/150.html
150 Evaluate Reverse Polish Notation
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
@tag-stack
Algorithm
Traverse the array from front to back. When encountering a number, it is pushed onto the stack. When encountering a symbol, the two numbers on the top of the stack are taken out for operation, and the result is pushed onto the stack again, until the entire array is traversed, and the number on the top of the stack is final answer.
The biggest pit, pay attention to the order of division, the order of pop comes out is reversed, you need to reverse
regex judges the number and reports errors several times
s.matches("[+-]?\\d+")) //"d"
is only one digit, should be d+
Code
Java
-
import java.util.Stack; public class Evaluate_Reverse_Polish_Notation { public static void main(String[] args) { Evaluate_Reverse_Polish_Notation out = new Evaluate_Reverse_Polish_Notation(); Solution s = out.new Solution(); System.out.print(s.evalRPN(new String[] { "18" })); } public class Solution { public int evalRPN(String[] tokens) { if (tokens == null || tokens.length == 0) return 0; Stack<String> sk = new Stack<>(); for (int i = 0; i < tokens.length; i++) { String s = tokens[i]; if (s.matches("[+-]?\\d+")) { //"d" is only one digit, should be d+ sk.push(s); } else if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) { /* @note: order of poping! Runtime Error Message: Line 23: java.lang.ArithmeticException: / by zero Last executed input: ["0","3","/"] */ int b = Integer.parseInt(sk.pop()); // did not check isEmpty, exception handler deal with it int a = Integer.parseInt(sk.pop()); int c = 0; switch(s) { case "+": c = a + b; break; case "-": c = a - b; break; case "*": c = a * b; break; case "/": c = a / b; break; // defaut: break; } sk.push(c + ""); // String.valueOf() } } return Integer.parseInt(sk.pop()); } } }
-
// OJ: https://leetcode.com/problems/evaluate-reverse-polish-notation/ // Time: O(N) // Space: O(N) class Solution { public: int evalRPN(vector<string>& A) { stack<int> s; for (auto &t : A) { if (isdigit(t.back())) { s.push(stoi(t)); } else { int n = s.top(); s.pop(); switch (t[0]) { case '+': s.top() += n; break; case '-': s.top() -= n; break; case '*': s.top() *= n; break; case '/': s.top() /= n; break; } } } return s.top(); } };
-
class Solution: def evalRPN(self, tokens: List[str]) -> int: nums = [] for t in tokens: if len(t) > 1 or t.isdigit(): nums.append(int(t)) else: if t == "+": nums[-2] += nums[-1] elif t == "-": nums[-2] -= nums[-1] elif t == "*": nums[-2] *= nums[-1] else: nums[-2] = int(nums[-2] / nums[-1]) nums.pop() return nums[0] ############ class Solution(object): def evalRPN(self, tokens): """ :type tokens: List[str] :rtype: int """ stack = [] for token in tokens: if token in ["+", "-", "*", "/"]: b, a = stack.pop(), stack.pop() if token == "+": res = a + b if token == "-": res = a - b if token == "*": res = a * b if token == "/": res = int(float(a) / float(b)) stack.append(res) else: stack.append(int(token)) return stack.pop()