基本计算器

七崽爱吃小饼干2026/01/06阅读 0专栏算法合集

基本计算器

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

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

codeType

输入：s = "1 + 1"
输出：2

示例 2：

codeType

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

示例 3：

codeType

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

提示：

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

解法：

function calculate(s: string): number {
    // 栈仅存储数字（减法转为加负数），简化计算
    const stack: number[] = [];
    const n = s.length;
    let i = 0;
    // 记录当前运算符（初始为+，第一个数字默认加）
    let currentOp = '+';
    // 记录当前拼接的数字
    let currentNum = 0;

    while (i < n) {
        const char = s[i];

        // 1. 跳过空格
        if (char === ' ') {
            i++;
            continue;
        }

        // 2. 处理多位数拼接
        if (/\d/.test(char)) {
            currentNum = currentNum * 10 + Number(char);
            i++;
            continue;
        }

        // 3. 处理左括号：将当前运算符入栈，重置运算符为+（处理括号内的初始状态）
        if (char === '(') {
            stack.push(currentOp === '+' ? 1 : -1); // 用1/-1标记括号前的运算符
            stack.push(Infinity); // 标记左括号（用Infinity替代，方便识别）
            currentOp = '+'; // 括号内初始运算符为+
            currentNum = 0;
            i++;
            continue;
        }

        // 4. 处理右括号：计算括号内的和，并结合括号前的运算符入栈
        if (char === ')') {
            // 先把括号内最后一个数字入栈（根据当前运算符）
            if (currentOp === '+') stack.push(currentNum);
            else stack.push(-currentNum);
            
            // 计算括号内的总和（直到碰到左括号标记Infinity）
            let bracketSum = 0;
            while (stack[stack.length - 1] !== Infinity) {
                bracketSum += stack.pop()!;
            }
            stack.pop(); // 弹出左括号标记
            
            // 取出括号前的运算符标记（1=+，-1=-），并将括号结果入栈
            const opFlag = stack.pop()!;
            stack.push(bracketSum * opFlag);
            
            // 重置状态
            currentOp = '+';
            currentNum = 0;
            i++;
            continue;
        }

        // 5. 处理加减运算符：先将当前数字按上一个运算符入栈，再更新运算符
        if (char === '+' || char === '-') {
            if (currentOp === '+') {
                stack.push(currentNum);
            } else {
                stack.push(-currentNum);
            }
            currentOp = char;
            currentNum = 0;
            i++;
        }
    }

    // 6. 处理最后一个数字
    if (currentOp === '+') stack.push(currentNum);
    else stack.push(-currentNum);

    // 7. 栈内所有数字求和（核心：减法已转为加负数）
    return stack.reduce((sum, num) => sum + num, 0);
}