[LeetCode]Evaluate Reverse Polish Notation

Question 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

---

本题难度Medium。

栈

【复杂度】 时间 O(N) 空间 O(1)

【思路】 遇到数字push到栈，遇到操作符将栈里的数字pop出来进行运算。

【附】 判断是否为数字就是看该字符串内是否含有数字字符。

【注意】 第11行不要写成：

int a=stack.pop(),b=stack.pop();

【代码】

public class Solution { public int evalRPN(String[] tokens) { //require if(tokens.length<1)return 0; Stack<Integer> stack=new Stack<>(); //invariant for(String str:tokens){ if(isNumeric(str)){ stack.push(Integer.parseInt(str)); }else{ int b=stack.pop(),a=stack.pop(); switch(str){ case "+":stack.push(a+b);break; case "-":stack.push(a-b);break; case "*":stack.push(a*b);break; case "/":stack.push(a/b);break; } } } //ensure return stack.pop(); } private boolean isNumeric(String str){ int size=str.length(); for(int i=0;i<size;i++) if(Character.isDigit(str.charAt(i)))return true; //ensure return false; } }