本文共 3208 字，大约阅读时间需要 10 分钟。

问题分析与解决

Thema

给你一个字符串表达式 s，实现一个基本计算器，返回它的值。不允许使用任何将字符串作为数学表达式计算的内置函数。

问题描述

根据题意，输入 s 是一个有效的数学表达式，包含数字、加减符号、括号和空格。表达式的有效性保证了避免连续操作符、合理的括号格式等特性。目标是在不使用 eval() 等内置函数的情况下，对字符串表达式进行计算。

思路分析

处理此类表达式可以借助栈数据结构，因而解题思路围绕以下两个核心问题展开：

示例分析

• 示例1: s = "1 + 1"
  返回结果为2。

-示例2: s = " 2-1 + 2 "

-示例3: s = "(1+(4+5+2)-3)+(6+8)"

核心解决方案

代码解析

public class Solution {
    public int calculate(String s) {
        Stack
   
     st = new Stack<>();
        st.push(1); // 初始符号状态为正
        int flag = 1;
        long sum = 0;
        for (int i = 0; i < s.length(); ) {
            char c = s.charAt(i);
            if (c == '+' || c == '-') {
                if (c == '+') {
                    if (!st.isEmpty()) {
                        flag = st.top();
                        i++;
                    } else {
                        return 0; // 无法处理
                    }
                }
                if (c == '-') {
                    if (!st.isEmpty()) {
                        flag = -st.top();
                        i++;
                    } else {
                        return 0; // 无法处理
                    }
                }
            } else if (c == '(') {
                switch (flag) {
                    case 1: // 括号前正，括号内符号状态与外层相同
                        flag = 1;
                        break;
                    case -1: // 括号前负，括号内符号状态反转
                        flag = 1;
                        st.pop(); // 去掉初始的1，设置为-1
                        break;
                }
                i++;
            } else if (c == ')') {
                st.pop(); // 恢复外层符号状态
                i++;
            } else {
                // 处理数字和空格
                if (c == ' ') {
                    i++;
                    continue;
                }
                if (c < '0' || c > '9') {
                    // 不是数字字符，处理前面可能出现的数字
                    if (!stack.isEmpty()) {
                        // 做一个循环排除非数字字符
                        while (i < s.length() && s.charAt(i) < '0' || s.charAt(i) > '9') {
                            i++;
                        }
                    } else {
                        i++;
                    }
                    continue;
                }
                
                int num = 0;
                while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                sum += flag * num;
            }
        }
        return (int) sum;
    }
}
   

代码解释

• 初始化栈：用来保存符号状态，初始状态为正（1）。
• 遍历字符串：逐字符处理每个字符，更新符号状态、数字解析和总和。
• 符号处理：遇到 + - 时更新 flag，决定当前数值的符号。
• 括号处理：左括号更新符号状态，右括号恢复外层符号。
• 数字处理：遇到数字字符时逐位解析，结合当前符号状态更新总和。

处理细节

复杂度分析

• 时间复杂度: O(n)，字符串遍历一次。
• 空间复杂度: O(n)，栈中最多存储字符串长度数量的元素。

希望以上内容能为您提供清晰的思路和代码参考！