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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author Gnawix
 * @Date 2022/5/9 17:25
 * @Version 1.0
 */
public class Calculator {
    public static void main(String[] args) {
        String s = "3+(4/2*2)^2-1-2*(1-1)";
        System.out.println(calculate(s));
    }

    private static Map<Character, Integer> map = new HashMap<Character, Integer>(){
        {
            put('+', 1);
            put('-', 1);
            put('*', 2);
            put('/', 2);
            put('%', 2);
            put('^', 3);
        }
    };

    private static int calculate(String s) {
        // 去掉所有掉空格
        s = s.replaceAll(" ", "");
        char[] cs = s.toCharArray();
        int n = s.length();
        // 数字栈
        Deque<Integer> num = new ArrayDeque<>();
        // 为了防止第一个数为负数，先往 nums 加个 0
        num.add(0);
        // 操作符栈
        Deque<Character> ops = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                // 计算两个括号间内容
                while (!ops.isEmpty()) {
                    if (ops.peek() != '(') {
                        calc(num, ops);
                    } else {
                        ops.pop();
                        break;
                    }
                }
            } else {
                if (Character.isDigit(c)) {
                    int tmp = 0;
                    int j = i;
                    while (j < n && Character.isDigit(cs[j])) {
                        tmp = tmp * 10 + (cs[j] - '0');
                        j++;
                    }
                    num.push(tmp);
                    i = j - 1;
                } else {
                    // (-2+1) ==> (0-2+1)
                    if (i > 0 && cs[i - 1] == '(') {
                        // 负数补0
                        num.push(0);
                    }
                    while (!ops.isEmpty() && ops.peek() != '(') {
                        char prev = ops.peek();
                        // 有一个新操作要入栈时，先把栈内可以算的都算了 
                        // 只有满足「栈内运算符」比「当前运算符」优先级高/同等，才进行运算
                        if (map.get(prev) >= map.get(c)) {
                            calc(num, ops);
                        } else {
                            break;
                        }
                    }
                    ops.push(c);
                }
            }
        }
        while (!ops.isEmpty()) {
            calc(num, ops);
        }
        return num.peek();
    }

    private static void calc(Deque<Integer> num, Deque<Character> ops) {
        if (num.isEmpty() || num.size() < 2) {
            return;
        }
        if (ops.isEmpty()) {
            return;
        }
        int ans = 0;
        int b = num.pop(), a = num.pop();
        char op = ops.pop();
        switch(op){
            case '+':
                ans = a + b;
                break;
            case '-':
                ans = a - b;
                break;
            case '*':
                ans = a * b;
                break;
            case '/':
                ans = a / b;
                break;
            case '^':
                ans = (int) Math.pow(a, b);
                break;
            case '%':
                ans = a % b;
                break;
            default:
                break;
        }
        num.push(ans);
    }
}