【LeetCode-中等题】150. 逆波兰表达式求值

题目

方法一：栈

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> deque= new LinkedList<>();
        String rpn = "+-*/";//符号集  用来判断扫描的是否为运算符
        int sum = 0;
        for(int i = 0 ; i < tokens.length ; i++){
            if(!rpn.contains(tokens[i])) deque.push(Integer.valueOf(tokens[i]));// 如果当前字符不为运算符  则直接入栈 
            else{// 如果当前字符为运算符  则将栈顶两个元素弹出  根据    后出 +-*/ 先出 的规则运算，再将结果压入栈中
                sum = eval(tokens[i],deque);
                deque.push(sum);
            }
        }
        return deque.peek();//最后遍历完字符数组  最后栈中的唯一元素就是最终结果

    }
    //匹配运算
    public int eval(String s ,   Deque<Integer> deque){
        int  first = deque.pop();
        int  second = deque.pop();
        if(s.equals("+")){
          return second + first;
        }else if(s.equals("-")){
          return second - first;
        }else if(s.equals("*")){
          return second * first;
        }else{
          return second / first;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30