227. 基本计算器 II

题目描述

输入一个字符串 s，它是一个算术表达式，包含非负整数、运算符 +、-、*、/，以及任意数量的空格。

计算这个表达式并返回结果。乘除的优先级高于加减，同级运算从左到右进行。

整数除法只保留整数部分，即向零取整。

不能借助 eval() 这类直接把字符串当作表达式求值的内置函数。题目保证表达式合法，且计算过程中每一步的结果都落在 [-2^31, 2^31 - 1] 之内。

示例 1

输入：s = "3+2*2"
输出：7

解释：先算乘法 2*2 = 4，再加 3，得到 7。

示例 2

输入：s = " 3/2 "
输出：1

解释：3/2 向零取整为 1。

示例 3

输入：s = " 3+5 / 2 "
输出：5

解释：先算 5/2 = 2，再算 3 + 2 = 5。

数据范围

1 <= s.length <= 3 * 10^5
s 只含整数、运算符 +、-、*、/ 和空格。
s 是一个合法的表达式。
表达式里的整数都是非负数，取值在 [0, 2^31 - 1] 之间。
最终答案可以用 32 位整数表示。

解题思路：栈

乘除的优先级高于加减。可以把整个表达式看成若干“项”相加：每个 + 或 - 开启一个新项，而 * 和 / 只会改变当前最后一项。所以用栈保存所有项：读完一个数字后，看它前面的运算符 op：+ 就把 num 压栈，- 就把 -num 压栈，* 或 / 就弹出栈顶，与 num 计算后再压回。最后把栈里所有项加起来。

为什么正确

栈里每个元素是一个已经算完乘除的项（带符号），栈中所有元素之和等于已经扫过部分的值；op 始终是还没有处理的那个数字前面的运算符。

复杂度分析

时间 O(n)；空间 O(n)，栈里最多存 O(n) 个项。

易错点

最后一个数字后面没有运算符，必须用 i == n-1 强制结算一次；而且判断数字和判断结算是两个独立的 if，不能写成 if/elif，否则末尾的数字会漏掉。除法要向零截断：Python 里用 int(a / b)，不能用 a // b（负数时结果不同）。

参考代码

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

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        op = '+'
        n = len(s)
        for i, c in enumerate(s):
            if c.isdigit():
                num = num * 10 + int(c)
            if (not c.isdigit() and c != ' ') or i == n - 1:
                if op == '+':
                    stack.append(num)
                elif op == '-':
                    stack.append(-num)
                elif op == '*':
                    stack.append(stack.pop() * num)
                else:
                    stack.append(int(stack.pop() / num))
                op = c
                num = 0
        return sum(stack)

class Solution {
    public int calculate(String s) {
        Deque<Long> stack = new ArrayDeque<>();
        long num = 0;
        char op = '+';
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            }
            if ((!Character.isDigit(c) && c != ' ') || i == n - 1) {
                if (op == '+') {
                    stack.push(num);
                } else if (op == '-') {
                    stack.push(-num);
                } else if (op == '*') {
                    stack.push(stack.pop() * num);
                } else {
                    stack.push(stack.pop() / num);
                }
                op = c;
                num = 0;
            }
        }
        long sum = 0;
        for (long x : stack) sum += x;
        return (int) sum;
    }
}

class Solution {
public:
    int calculate(string s) {
        vector<long long> stk;
        long long num = 0;
        char op = '+';
        int n = s.size();
        for (int i = 0; i < n; i++) {
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            }
            if ((!isdigit(c) && c != ' ') || i == n - 1) {
                if (op == '+') {
                    stk.push_back(num);
                } else if (op == '-') {
                    stk.push_back(-num);
                } else if (op == '*') {
                    stk.back() *= num;
                } else {
                    stk.back() /= num;
                }
                op = c;
                num = 0;
            }
        }
        long long sum = 0;
        for (long long x : stk) sum += x;
        return (int)sum;
    }
};

func calculate(s string) int {
	stack := []int{}
	num := 0
	op := byte('+')
	n := len(s)
	for i := 0; i < n; i++ {
		c := s[i]
		isDigit := c >= '0' && c <= '9'
		if isDigit {
			num = num*10 + int(c-'0')
		}
		if (!isDigit && c != ' ') || i == n-1 {
			switch op {
			case '+':
				stack = append(stack, num)
			case '-':
				stack = append(stack, -num)
			case '*':
				stack[len(stack)-1] *= num
			default:
				stack[len(stack)-1] /= num
			}
			op = c
			num = 0
		}
	}
	sum := 0
	for _, x := range stack {
		sum += x
	}
	return sum
}

var calculate = function(s) {
    const stack = [];
    let num = 0;
    let op = '+';
    const n = s.length;
    for (let i = 0; i < n; i++) {
        const c = s[i];
        const isDigit = c >= '0' && c <= '9';
        if (isDigit) {
            num = num * 10 + Number(c);
        }
        if ((!isDigit && c !== ' ') || i === n - 1) {
            if (op === '+') {
                stack.push(num);
            } else if (op === '-') {
                stack.push(-num);
            } else if (op === '*') {
                stack.push(stack.pop() * num);
            } else {
                stack.push(Math.trunc(stack.pop() / num));
            }
            op = c;
            num = 0;
        }
    }
    return stack.reduce((a, b) => a + b, 0);
};

function calculate(s: string): number {
    const stack: number[] = [];
    let num = 0;
    let op = '+';
    const n = s.length;
    for (let i = 0; i < n; i++) {
        const c = s[i];
        const isDigit = c >= '0' && c <= '9';
        if (isDigit) {
            num = num * 10 + Number(c);
        }
        if ((!isDigit && c !== ' ') || i === n - 1) {
            if (op === '+') {
                stack.push(num);
            } else if (op === '-') {
                stack.push(-num);
            } else if (op === '*') {
                stack.push(stack.pop()! * num);
            } else {
                stack.push(Math.trunc(stack.pop()! / num));
            }
            op = c;
            num = 0;
        }
    }
    return stack.reduce((a, b) => a + b, 0);
}

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

其他解法

两种方法都只扫描一遍。栈的写法便于理解和扩展；常数空间累加把栈压缩成两个变量。

解法 2：常数空间累加时间 O(n)，空间 O(1)

栈里只有栈顶会被乘除修改，更早的项只等着最后求和。用 res 保存已经确定的和，用 last 保存当前还可能被乘除修改的项。遇到加减号时把 last 加进 res，再让 last 等于带符号的新数；遇到乘除号时直接用新数修改 last。最后返回 res + last。

省掉了栈，额外空间降到 O(1)。代价是思路不如栈直观，扩展到括号时仍要回到栈的写法。

class Solution:
    def calculate(self, s: str) -> int:
        res = last = num = 0
        op = '+'
        n = len(s)
        for i, c in enumerate(s):
            if c.isdigit():
                num = num * 10 + int(c)
            if (not c.isdigit() and c != ' ') or i == n - 1:
                if op == '+':
                    res += last
                    last = num
                elif op == '-':
                    res += last
                    last = -num
                elif op == '*':
                    last = last * num
                else:
                    last = int(last / num)
                op = c
                num = 0
        return res + last

class Solution {
    public int calculate(String s) {
        long res = 0, last = 0, num = 0;
        char op = '+';
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            }
            if ((!Character.isDigit(c) && c != ' ') || i == n - 1) {
                if (op == '+') {
                    res += last;
                    last = num;
                } else if (op == '-') {
                    res += last;
                    last = -num;
                } else if (op == '*') {
                    last = last * num;
                } else {
                    last = last / num;
                }
                op = c;
                num = 0;
            }
        }
        return (int) (res + last);
    }
}

class Solution {
public:
    int calculate(string s) {
        long long res = 0, last = 0, num = 0;
        char op = '+';
        int n = s.size();
        for (int i = 0; i < n; i++) {
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            }
            if ((!isdigit(c) && c != ' ') || i == n - 1) {
                if (op == '+') {
                    res += last;
                    last = num;
                } else if (op == '-') {
                    res += last;
                    last = -num;
                } else if (op == '*') {
                    last = last * num;
                } else {
                    last = last / num;
                }
                op = c;
                num = 0;
            }
        }
        return (int)(res + last);
    }
};

func calculate(s string) int {
	res, last, num := 0, 0, 0
	op := byte('+')
	n := len(s)
	for i := 0; i < n; i++ {
		c := s[i]
		isDigit := c >= '0' && c <= '9'
		if isDigit {
			num = num*10 + int(c-'0')
		}
		if (!isDigit && c != ' ') || i == n-1 {
			switch op {
			case '+':
				res += last
				last = num
			case '-':
				res += last
				last = -num
			case '*':
				last = last * num
			default:
				last = last / num
			}
			op = c
			num = 0
		}
	}
	return res + last
}

var calculate = function(s) {
    let res = 0, last = 0, num = 0;
    let op = '+';
    const n = s.length;
    for (let i = 0; i < n; i++) {
        const c = s[i];
        const isDigit = c >= '0' && c <= '9';
        if (isDigit) {
            num = num * 10 + Number(c);
        }
        if ((!isDigit && c !== ' ') || i === n - 1) {
            if (op === '+') {
                res += last;
                last = num;
            } else if (op === '-') {
                res += last;
                last = -num;
            } else if (op === '*') {
                last = last * num;
            } else {
                last = Math.trunc(last / num);
            }
            op = c;
            num = 0;
        }
    }
    return res + last;
};

function calculate(s: string): number {
    let res = 0, last = 0, num = 0;
    let op = '+';
    const n = s.length;
    for (let i = 0; i < n; i++) {
        const c = s[i];
        const isDigit = c >= '0' && c <= '9';
        if (isDigit) {
            num = num * 10 + Number(c);
        }
        if ((!isDigit && c !== ' ') || i === n - 1) {
            if (op === '+') {
                res += last;
                last = num;
            } else if (op === '-') {
                res += last;
                last = -num;
            } else if (op === '*') {
                last = last * num;
            } else {
                last = Math.trunc(last / num);
            }
            op = c;
            num = 0;
        }
    }
    return res + last;
}

栈与堆专题的其他题目

查看栈与堆全部题目 →