第一题150. 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

ψ(｀∇´)ψ 我的思路

• 题目上提示的已经很清晰了

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

package stackandqueue;

import java.util.Stack;

public class EvalRPN {

    public int evalRPN(String[] tokens) {
        int m,n;
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            //如果是运算符的话，取出栈顶的两个元素，和运算符计算，结果入栈
            if(tokens[i].equals("+")){
                stack.push(String.valueOf(Integer.parseInt(stack.pop())+Integer.parseInt(stack.pop())));
            } else if (tokens[i].equals("-")) {
                m = Integer.parseInt(stack.pop());
                n = Integer.parseInt(stack.pop());
                stack.push(String.valueOf(n-m));
            } else if (tokens[i].equals("*")) {
                stack.push(String.valueOf(Integer.parseInt(stack.pop())*Integer.parseInt(stack.pop())));
            }else if (tokens[i].equals("/")) {
                m = Integer.parseInt(stack.pop());
                n = Integer.parseInt(stack.pop());
                stack.push(String.valueOf(n/m));
            } else {
                stack.push(tokens[i]);//如果不是运算符的话，入栈
            }
        }
        return Integer.parseInt(stack.pop());
    }
}

时间复杂度O(n)

• 在力扣上debug也太方便了吧
  标签：nums,int,元素,随想录,pop,public,求值,stack,第十三天
  From： https://www.cnblogs.com/xiannveryao/p/16750425.html