leetCode 150 Evaluate Reverse Polish Notation

参考资料：左神算法课

150. Evaluate Reverse Polish Notation
     You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are ‘+’, ‘-’, ‘*’, and ‘/’.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

Input: tokens = [“2”,“1”,“+”,“3”,“*”]
Output: 9
Explanation: ((2 + 1) * 3) = 9

思路：建立一个栈，依次把数放入。当遍历到运算符时，弹出两个数，计算结果并将其放入栈。最后的栈顶就是答案。

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        
        for(String s:tokens)
        {
            if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/"))
            {
                com(stack,s);               
            }else{
                stack.push(Integer.valueOf(s));
            }
        }

        return stack.peek();// Amazing ! peek is faster than pop
    }
    public void com(Stack<Integer> stack, String s)
    {
        int n2 = Integer.valueOf(stack.pop());
        int n1= Integer.valueOf(stack.pop());
        int ans=0;
                switch(s){
                    case "+":
                        ans=n1+n2;
                        break; 
                    case "-":
                        ans=n1-n2;
                        break; 
                    case "*":
                        ans=n1*n2;
                        break; 
                    case "/":
                        ans=n1/n2;
                        break;                   
                }
               stack.push(ans);
    }

    public static int evalRPN_zuo(String[] tokens) {
		Stack<Integer> stack = new Stack<>();
		for (String str : tokens) {
			if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
				compute(stack, str);
			} else {
				stack.push(Integer.valueOf(str));
			}
		}
		return stack.peek();
	}

	public static void compute(Stack<Integer> stack, String op) {
		int num2 = stack.pop();
		int num1 = stack.pop();
		int ans = 0;
		switch (op) {
		case "+":
			ans = num1 + num2;
			break;
		case "-":
			ans = num1 - num2;
			break;
		case "*":
			ans = num1 * num2;
			break;
		case "/":
			ans = num1 / num2;
			break;
		}
		stack.push(ans);
	}
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71