本文共 3141 字，大约阅读时间需要 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)，栈中最多存储字符串长度数量的元素。

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

转载地址：http://sagyk.baihongyu.com/