0227. 基本计算器 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 栈

1. 📝 题目描述

• leetcode

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

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-2^31, 2^31 - 1] 的范围内。

---

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

---

示例 1：

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

示例 2：

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

示例 3：

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

---

提示：

• 1 <= s.length <= 3 * 10^5
• s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
• s 表示一个 有效表达式
• 表达式中的所有整数都是非负整数，且在范围 [0, 2^31 - 1] 内
• 题目数据保证答案是一个 32-bit 整数

2. 🎯 s.1 - 栈

c

int calculate(char* s) {
    int len = strlen(s);
    int* stack = (int*)malloc(sizeof(int) * (len + 1));
    int top = 0;
    long num = 0;
    char sign = '+';
    for (int i = 0; i <= len; i++) {
        char ch = (i < len) ? s[i] : '\0';
        if (ch >= '0' && ch <= '9') {
            num = num * 10 + (ch - '0');
        }
        if ((ch != ' ' && (ch < '0' || ch > '9')) || i == len) {
            if (sign == '+') stack[top++] = (int)num;
            else if (sign == '-') stack[top++] = (int)(-num);
            else if (sign == '*') stack[top - 1] *= (int)num;
            else if (sign == '/') stack[top - 1] /= (int)num;
            sign = ch;
            num = 0;
        }
    }
    int result = 0;
    for (int i = 0; i < top; i++) result += stack[i];
    free(stack);
    return result;
}

js

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function (s) {
  const stack = []
  let num = 0
  let sign = '+'
  for (let i = 0; i < s.length; i++) {
    const ch = s[i]
    if (ch >= '0' && ch <= '9') {
      num = num * 10 + (ch - '0')
    }
    if ((ch !== ' ' && (ch < '0' || ch > '9')) || i === s.length - 1) {
      if (sign === '+') stack.push(num)
      else if (sign === '-') stack.push(-num)
      else if (sign === '*') stack.push(stack.pop() * num)
      else if (sign === '/') stack.push(~~(stack.pop() / num))
      sign = ch
      num = 0
    }
  }
  return stack.reduce((a, b) => a + b, 0)
}

py

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

• 时间复杂度：$O(n)$，其中 $n$ 是字符串长度
• 空间复杂度：$O(n)$，栈的大小

算法思路：

• 用栈处理运算符优先级，遇到 +/- 时将数字压栈
• 遇到 *// 时立即与栈顶计算
• 最终栈内所有元素求和即为结果