LeetCode_栈_困难_227.基本计算器（不含乘除）

1.题目

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：
输入：s = “1 + 1”
输出：2

示例 2：
输入：s = " 2-1 + 2 "
输出：3

示例 3：
输入：s = “(1+(4+5+2)-3)+(6+8)”
输出：23

提示：
1 <= s.length <= 3 * 10⁵
s 由数字、‘+’、‘-’、‘(’、‘)’、和 ’ ’ 组成
s 表示一个有效的表达式
‘+’ 不能用作一元运算(例如，“+1” 和 “+(2 + 3)” 无效)
‘-’ 可以用作一元运算(即 “-1” 和 “-(2 + 3)” 是有效的)
输入中不存在两个连续的操作符
每个数字和运行的计算将适合于一个有符号的 32 位整数

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/basic-calculator

2.思路

（1）栈
思路参考本题官方题解。

3.代码实现（Java）

//思路1————栈
class Solution {
    public static int calculate(String s) {
        int res = 0;
        int length = s.length();
        //sign 记录每个数之前的符号，对于表达式中的第一个数，默认其符号为 '+'，即用 1 表示
        int sign = 1;
        Stack<Integer> opsStack = new Stack<>();
        opsStack.push(1);
        for (int i = 0; i < length; ) {
            switch (s.charAt(i)) {
                case ' ':
                    //遇到空格时直接跳过
                    i++;
                    break;
                case '+':
                    sign = opsStack.peek();
                    i++;
                    break;
                case '-':
                    sign = -opsStack.peek();
                    i++;
                    break;
                case '(':
                    opsStack.push(sign);
                    i++;
                    break;
                case ')':
                    opsStack.pop();
                    i++;
                    break;
                default:
	                //表示遍历表达式时遇到的每一个数
                    int num = 0;
                    while (i < length && Character.isDigit(s.charAt(i))) {
                        num = num * 10 + (s.charAt(i) - '0');
                        i++;
                    }
                    res += sign * num;
                    break;
            }
        }
        return res;
    }
}
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