[LeetCode]Evaluate Reverse Polish Notation

    xiaoxiao2021-12-15  41

    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; } }
    转载请注明原文地址: https://ju.6miu.com/read-1000106.html

    最新回复(0)