今天的题目来源于 LeetCode 第 224 号问题：基本计算器，难度为「困难」，根据评论区的反馈，在字节面试出现过。

一、题目描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

示例 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 * 105
• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
• s 表示一个有效的表达式

二、题目解析

对于一个表达式来说，它包含三部分：

• 1、左表达式
• 2、运算符
• 3、右表达式

左边和右边的表达式可以是一个数字，也可以是一个括号包起来的表达式；运算符可以是加减。

对于一个只包含加减和括号的表达式来说，是按照从左到右的顺序进行计算，但遇到括号就先算括号里面的。

具体操作如下：

1、使用栈来储存字符串表达式中的数字，设置变量 res 保存计算的结果，一开始可以认为 res = 0，作为左表达式，同时当前的运算符为 + ，接下来去变量字符数组，先去寻找出右表达式出来。

2、获取字符串里面的每个字符

3、如果当前字符是数字的话，需要去查看当前字符的后一位是否存在，如果后一位依旧是数字，那么就需要把后面的数字累加上来，比如下图中的 12，查看到 1 时，继续查看后面的数字是 2 ，于是和 1 组成了 12，再向后看发现是字符，自此，这个数字 12 就形成了。

4、一旦确定了一个数字，需要把这个数字进行一个计算， res = res + sign * value。

5、如果遇到的是运算符 + 或者 - ，那么为了方便计算，所有的操作都视为加法操作，即原先的减法操作就相当于是加一个负数。

6、如果遇到的是 （ ，根据数学计算规则，需要先计算括号里面的数字，而什么时候计算呢？遇到 ) 为止，所以，在遇到 ) 之前需要把之前计算好的结果存储起来再计算。

7、如果遇到的是 ），那么就需要把栈中存放的元素取出来了。

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 基本计算器（ LeetCode 224 ）:https://leetcode-cn.com/problems/basic-calculator
class Solution {
    public int calculate(String s) {

        // 使用栈来储存字符串表达式中的数字
        Stack<Integer> stack = new Stack<Integer>();

        // 为了方便计算，所有的操作都视为加法操作
        // 那么原先的减法操作就相当于是加一个负数
        // 默认都是正数
        int sign = 1;

        // 保存计算的结果
        int res = 0;

        // 获取字符串的长度，然后获取里面的每个字符
        int length = s.length();

        // 获取字符串里面的每个字符
        for (int i = 0; i < length; i++) {

            // 获取此时的字符
            char ch = s.charAt(i);

            // 如果当前字符是数字的话
            if (Character.isDigit(ch)) {

                // 那么可以通过 - '0' 这个操作把字符转换为整数
                // 相当于转换成了 ascii 码进行的数字运算
                int value = ch - '0';

                // 去查看当前字符的后一位是否存在
                // 如果操作并且后一位依旧是数字，那么就需要把后面的数字累加上来

                while (i + 1 < length && Character.isDigit(s.charAt(i + 1))){
                    
                    // i 向后移动，直到遇到非数字为止
                    i++;

                    // i 每向后移动一位，当前的值就需要乘以 10
                    // 比如 s 为 "123+456"
                    // 此时 i = 0，那么 value 为 1
                    // i = 1，那么 value 为 1 * 10 + 2 = 12
                    // i = 2，那么 value 为 12 * 10 + 3 = 123
                    value = value * 10 + s.charAt(i) - '0';

                }

                // 那么把获取到的数累加到结果 res 上
                res = res + sign * value;

              // 如果是 '+'
            } else if (ch == '+') {
                
                // 那么说明直接加一个正数
                sign = 1;

              // 如果是 '-'
            } else if (ch == '-') {

                // 那么说明加一个负数
                sign = -1;

              // 如果是 '('
            } else if (ch == '(') {
                // 根据数学计算规则，需要先计算括号里面的数字
                // 而什么时候计算呢？
                // 遇到 ) 为止
                // 所以，在遇到 ) 之前需要把之前计算好的结果存储起来再计算
                // ( ) 直接的计算规则和一开始是一样的

                // 1、先把 ( 之前的结果存放到栈中
                stack.push(res);

                // 2、重新初始化 res 为 0
                res = 0;
                // 3、把 ( 左边的操作符号存放到栈中
                // 比如如果是 5 - （ 2 + 3 ） ，那么就是把 -1 存放进去
                // 比如如果是 5 +（ 2 + 3 ） ，那么就是把 1 存放进去
                stack.push(sign);

                // 4、为了方便计算，所有的操作都视为加法操作
                // 那么原先的减法操作就相当于是加一个负数
                // 默认都是正数
                sign = 1;

                // 如果是 ')'
            } else if (ch == ')') {
                
                // 那么就需要把栈中存放的元素取出来了
                // 在 ch == '（' 这个判断语句中，每次都会往栈中存放两个元素
                // 1、先存放左括号外面的结果
                // 2、再存放左括号外面的符号

                // 1、先获取栈顶元素，即左括号外面的符号，查看是 + 还是 -
                int formerSign = stack.peek();

                // 把栈顶元素弹出
                stack.pop();

                // 2、再获取栈顶元素，即左括号结果
                int formerRes = stack.peek();

                // 把栈顶元素弹出
                stack.pop();

                // 那结果就是括号外面的结果 + 括号里面的结果，至于是加正数还是负数，取决于左括号外面的符号
                res = formerRes +  formerSign * res ;

            }
        }

        // 返回计算好的结果
        return res;
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 基本计算器（ LeetCode 224 ）:https://leetcode-cn.com/problems/basic-calculator
class Solution {
public:
    int calculate(string s) {
        // 使用栈来储存字符串表达式中的数字
        stack<int> st;

        // 为了方便计算，所有的操作都视为加法操作
        // 那么原先的减法操作就相当于是加一个负数
        // 默认都是正数
        int sign = 1;

        // 保存计算的结果
        int res = 0;

        // 获取字符串的长度，然后获取里面的每个字符
        int length = s.length();

        // 获取字符串里面的每个字符
        for(int i = 0;i < length;i++){

            // 获取此时的字符
            char ch = s[i];

            // 如果当前字符是数字的话
            if( ch >= '0' && ch <= '9' ) {
                // 那么可以通过 - '0' 这个操作把字符转换为整数
                // 相当于转换成了 ascii 码进行的数字运算
                long value = ch - '0';

                // 去查看当前字符的后一位是否存在
                // 如果操作并且后一位依旧是数字，那么就需要把后面的数字累加上来
                while (i + 1< length &&s[i+1]>='0'&&s[i+1]<='9'){
                    // i 向后移动，直到遇到非数字为止
                    i++;

                    // i 每向后移动一位，当前的值就需要乘以 10
                    // 比如 s 为 "123+456"
                    // 此时 i = 0，那么 value 为 1
                    // i = 1，那么 value 为 1 * 10 + 2 = 12
                    // i = 2，那么 value 为 12 * 10 + 3 = 123
                     value = value*10 + s[i] - '0';
                     
                }
                // 那么把获取到的数累加到结果 res 上
                res = res + sign * value;

              // 如果是 '+'
            }else if(ch == '+'){
                // 那么说明直接加一个正数
                sign = 1;
              // 如果是 '-'
            }else if(ch == '-'){
                // 那么说明加一个负数
                sign = -1;

              // 如果是 '('
            }else if(ch == '('){
                // 根据数学计算规则，需要先计算括号里面的数字
                // 而什么时候计算呢？
                // 遇到 ) 为止
                // 所以，在遇到 ) 之前需要把之前计算好的结果存储起来再计算
                // ( ) 直接的计算规则和一开始是一样的

                // 1、先把 ( 之前的结果存放到栈中
                st.push(res);

                // 2、重新初始化 res 为 0
                res = 0;

                // 3、把 ( 左边的操作符号存放到栈中
                // 比如如果是 5 - （ 2 + 3 ） ，那么就是把 -1 存放进去
                // 比如如果是 5 +（ 2 + 3 ） ，那么就是把 1 存放进去
                st.push(sign);
                
                // 4、为了方便计算，所有的操作都视为加法操作
                // 那么原先的减法操作就相当于是加一个负数
                // 默认都是正数
                sign = 1;

            // 如果是 ')'
            }else if(ch == ')'){
                // 那么就需要把栈中存放的元素取出来了
                // 在 ch == '（' 这个判断语句中，每次都会往栈中存放两个元素
                // 1、先存放左括号外面的结果
                // 2、再存放左括号外面的符号

                // 1、先获取栈顶元素，即左括号外面的符号，查看是 + 还是 -
                int formerSign = st.top();

                // 把栈顶元素弹出
                st.pop();

                // 2、再获取栈顶元素，即左括号结果
                int formerRes = st.top();

                // 把栈顶元素弹出
                st.pop();

                // 那结果就是括号外面的结果 + 括号里面的结果，至于是加正数还是负数，取决于左括号外面的符号
                res = formerRes +formerSign*res;
            }
        }

        // 返回计算好的结果
        return res;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 基本计算器（ LeetCode 224 ）:https://leetcode-cn.com/problems/basic-calculator
class Solution:
    def calculate(self, s: str) -> int:

        # 使用栈来储存字符串表达式中的数字
        stack = list()

        # 为了方便计算，所有的操作都视为加法操作
        # 那么原先的减法操作就相当于是加一个负数
        # 默认都是正数
        sign = 1

        # 保存计算的结果
        res = 0

        # 获取字符串的长度，然后获取里面的每个字符
        length = len(s)

        # 从 0 开始访问字符串中的每个字符
        i = 0

        # 获取字符串里面的每个字符
        while i < length:
            # 获取此时的字符
            ch = s[i]

            if ch == ' ' :
                i += 1
            # 如果当前字符是数字的话
            elif ch.isdigit() :
                # 那么把获取到的数累加到结果 res 上
                value = 0

                # 去查看当前字符的后一位是否存在
                # 如果操作并且后一位依旧是数字，那么就需要把后面的数字累加上来
                while i < length and s[i].isdigit():
                    value = value * 10 + ord(s[i]) - ord('0')
                    i += 1
                
                # 那么把获取到的数累加到结果 res 上
                res += value * sign

              # 如果是 '+'
            elif ch == '+' :
                # 那么说明直接加一个正数
                sign = 1

                i += 1

              # 如果是 '-'
            elif ch == '-' :

                # 那么说明加一个负数
                sign = -1

                i += 1

              # 如果是 '('
            elif ch == '(' :
                # 根据数学计算规则，需要先计算括号里面的数字
                # 而什么时候计算呢？
                # 遇到 ) 为止
                # 所以，在遇到 ) 之前需要把之前计算好的结果存储起来再计算
                # ( ) 直接的计算规则和一开始是一样的

                # 1、先把 ( 之前的结果存放到栈中
                stack.append(res)

                # 2、重新初始化 res 为 0
                res = 0
                # 3、把 ( 左边的操作符号存放到栈中
                # 比如如果是 5 - （ 2 + 3 ） ，那么就是把 -1 存放进去
                # 比如如果是 5 +（ 2 + 3 ） ，那么就是把 1 存放进去
                stack.append(sign)

                # 4、为了方便计算，所有的操作都视为加法操作
                # 那么原先的减法操作就相当于是加一个负数
                # 默认都是正数
                sign = 1

                i += 1

                # 如果是 ')'
            elif ch == ')' :
                
                # 那么就需要把栈中存放的元素取出来了
                # 在 ch == '（' 这个判断语句中，每次都会往栈中存放两个元素
                # 1、先存放左括号外面的结果
                # 2、再存放左括号外面的符号

                # 1、先获取栈顶元素，即左括号外面的符号，查看是 + 还是 -
                # 把栈顶元素弹出
                formerSign = stack.pop()

                # 2、再获取栈顶元素，即左括号结果
                # 把栈顶元素弹出
                formerRes = stack.pop()

                # 那结果就是括号外面的结果 + 括号里面的结果，至于是加正数还是负数，取决于左括号外面的符号
                res = formerRes +  formerSign * res 

                i += 1
             

        # 返回计算好的结果
        return res

四、复杂度分析

时间复杂度：O(n)，其中 n 为字符串 s 的长度。需要遍历字符串 s 一次，计算表达式的值。

空间复杂度：O(n)，其中 n 为字符串 s 的长度。空间复杂度主要取决于栈的空间，栈中的元素数量不超过 n。