224. 基本计算器

题目描述

输入一个表示算式的字符串 s，实现一个简单的计算器，算出它的值并返回。

s 里只会出现数字、'+'、'-'、'('、')' 和空格。表达式一定合法，不会出现两个运算符紧挨着的情况。

'-' 可以当作取负号使用，例如 "-1"、"-(2 + 3)"；'+' 不会这样用，"+1" 这类写法不会出现。

不能调用 eval() 之类直接把字符串当算式求值的内置函数。

示例 1

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

解释：1 加 1 等于 2。

示例 2

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

解释：忽略空格，2 - 1 + 2 = 3。

示例 3

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

解释：括号内 1 + 11 - 3 = 9，再加上 6 + 8 = 14，共 23。

数据范围

1 <= s.length <= 3 * 10^5
s 由数字、'+'、'-'、'('、')'、' ' 组成。
s 是合法的表达式。
'+' 不会作为一元运算符出现。
'-' 可以作为一元运算符出现。
不会出现连续两个运算符。
所有数字和中间计算结果都在 32 位有符号整数范围内。

解题思路

只有加减法时，整个表达式就是一串带符号数字的和，难点在于括号前的负号会翻转括号内所有数字的符号。从左到右扫描并维护三个量：当前层已经算好的 res、正在拼的数字 num、num 前面的符号 sign。遇到 + 或 - 就把 sign*num 结算进 res；遇到 ( 就把外层的 res 和括号前的 sign 压栈，然后从 0 开始计算括号内部；遇到 ) 就先结算最后一个数，再用 res = 括号前的 res + 括号前的 sign * 括号内结果回到外层。

为什么正确

任意时刻，res + sign*num 恰好等于当前这层括号里已经扫过部分的值；栈里每一对 (res, sign) 记录了一层尚未闭合的括号外面的进度。

复杂度分析

时间 O(n)，每个字符处理一次；空间 O(n)，最坏情况括号嵌套深度为 O(n)。

易错点

遇到 ) 时必须先把括号里最后一个数 sign*num 结算进 res，再乘以弹出的符号；弹栈顺序也不能反：后压入的是 sign，所以先弹出符号相乘，再弹出外层 res 相加。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        res = 0
        num = 0
        sign = 1
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == '+' or c == '-':
                res += sign * num
                num = 0
                sign = 1 if c == '+' else -1
            elif c == '(':
                stack.append(res)
                stack.append(sign)
                res = 0
                sign = 1
            elif c == ')':
                res += sign * num
                num = 0
                res *= stack.pop()
                res += stack.pop()
        return res + sign * num

class Solution {
    public int calculate(String s) {
        Deque<Long> stack = new ArrayDeque<>();
        long res = 0;
        long num = 0;
        long sign = 1;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                res += sign * num;
                num = 0;
                sign = c == '+' ? 1 : -1;
            } else if (c == '(') {
                stack.push(res);
                stack.push(sign);
                res = 0;
                sign = 1;
            } else if (c == ')') {
                res += sign * num;
                num = 0;
                res *= stack.pop();
                res += stack.pop();
            }
        }
        return (int) (res + sign * num);
    }
}

class Solution {
public:
    int calculate(string s) {
        vector<long long> stk;
        long long res = 0;
        long long num = 0;
        long long sign = 1;
        for (char c : s) {
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                res += sign * num;
                num = 0;
                sign = c == '+' ? 1 : -1;
            } else if (c == '(') {
                stk.push_back(res);
                stk.push_back(sign);
                res = 0;
                sign = 1;
            } else if (c == ')') {
                res += sign * num;
                num = 0;
                res *= stk.back(); stk.pop_back();
                res += stk.back(); stk.pop_back();
            }
        }
        return (int)(res + sign * num);
    }
};

func calculate(s string) int {
	stack := []int{}
	res := 0
	num := 0
	sign := 1
	for i := 0; i < len(s); i++ {
		c := s[i]
		if c >= '0' && c <= '9' {
			num = num*10 + int(c-'0')
		} else if c == '+' || c == '-' {
			res += sign * num
			num = 0
			if c == '+' {
				sign = 1
			} else {
				sign = -1
			}
		} else if c == '(' {
			stack = append(stack, res)
			stack = append(stack, sign)
			res = 0
			sign = 1
		} else if c == ')' {
			res += sign * num
			num = 0
			res *= stack[len(stack)-1]
			res += stack[len(stack)-2]
			stack = stack[:len(stack)-2]
		}
	}
	return res + sign*num
}

var calculate = function(s) {
    const stack = [];
    let res = 0;
    let num = 0;
    let sign = 1;
    for (const c of s) {
        if (c >= '0' && c <= '9') {
            num = num * 10 + Number(c);
        } else if (c === '+' || c === '-') {
            res += sign * num;
            num = 0;
            sign = c === '+' ? 1 : -1;
        } else if (c === '(') {
            stack.push(res);
            stack.push(sign);
            res = 0;
            sign = 1;
        } else if (c === ')') {
            res += sign * num;
            num = 0;
            res *= stack.pop();
            res += stack.pop();
        }
    }
    return res + sign * num;
};

function calculate(s: string): number {
    const stack: number[] = [];
    let res = 0;
    let num = 0;
    let sign = 1;
    for (const c of s) {
        if (c >= '0' && c <= '9') {
            num = num * 10 + Number(c);
        } else if (c === '+' || c === '-') {
            res += sign * num;
            num = 0;
            sign = c === '+' ? 1 : -1;
        } else if (c === '(') {
            stack.push(res);
            stack.push(sign);
            res = 0;
            sign = 1;
        } else if (c === ')') {
            res += sign * num;
            num = 0;
            res *= stack.pop()!;
            res += stack.pop()!;
        }
    }
    return res + sign * num;
}

载入编辑器，自己跑一遍 →

栈与堆专题的其他题目

查看栈与堆全部题目 →