Question

227. 基本计算器 II

English Version

题目描述

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

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

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

解法

方法一：栈

遍历字符串 $s$，并用变量 sign 记录每个数字之前的运算符，对于第一个数字，其之前的运算符视为加号。每次遍历到数字末尾时，根据 sign 来决定计算方式：

• 加号：将数字压入栈；
• 减号：将数字的相反数压入栈；
• 乘除号：计算数字与栈顶元素，并将栈顶元素替换为计算结果。

遍历结束后，将栈中元素求和即为答案。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $s$ 的长度。

class Solution:
  def calculate(self, s: str) -> int:
    v, n = 0, len(s)
    sign = '+'
    stk = []
    for i, c in enumerate(s):
      if c.isdigit():
        v = v * 10 + int(c)
      if i == n - 1 or c in '+-*/':
        match sign:
          case '+':
            stk.append(v)
          case '-':
            stk.append(-v)
          case '*':
            stk.append(stk.pop() * v)
          case '/':
            stk.append(int(stk.pop() / v))
        sign = c
        v = 0
    return sum(stk)

class Solution {
  public int calculate(String s) {
    Deque<Integer> stk = new ArrayDeque<>();
    char sign = '+';
    int v = 0;
    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      if (Character.isDigit(c)) {
        v = v * 10 + (c - '0');
      }
      if (i == s.length() - 1 || c == '+' || c == '-' || c == '*' || c == '/') {
        if (sign == '+') {
          stk.push(v);
        } else if (sign == '-') {
          stk.push(-v);
        } else if (sign == '*') {
          stk.push(stk.pop() * v);
        } else {
          stk.push(stk.pop() / v);
        }
        sign = c;
        v = 0;
      }
    }
    int ans = 0;
    while (!stk.isEmpty()) {
      ans += stk.pop();
    }
    return ans;
  }
}

class Solution {
public:
  int calculate(string s) {
    int v = 0, n = s.size();
    char sign = '+';
    stack<int> stk;
    for (int i = 0; i < n; ++i) {
      char c = s[i];
      if (isdigit(c)) v = v * 10 + (c - '0');
      if (i == n - 1 || c == '+' || c == '-' || c == '*' || c == '/') {
        if (sign == '+')
          stk.push(v);
        else if (sign == '-')
          stk.push(-v);
        else if (sign == '*') {
          int t = stk.top();
          stk.pop();
          stk.push(t * v);
        } else {
          int t = stk.top();
          stk.pop();
          stk.push(t / v);
        }
        sign = c;
        v = 0;
      }
    }
    int ans = 0;
    while (!stk.empty()) {
      ans += stk.top();
      stk.pop();
    }
    return ans;
  }
};

func calculate(s string) int {
  sign := '+'
  stk := []int{}
  v := 0
  for i, c := range s {
    digit := '0' <= c && c <= '9'
    if digit {
      v = v*10 + int(c-'0')
    }
    if i == len(s)-1 || !digit && c != ' ' {
      switch sign {
      case '+':
        stk = append(stk, v)
      case '-':
        stk = append(stk, -v)
      case '*':
        stk[len(stk)-1] *= v
      case '/':
        stk[len(stk)-1] /= v
      }
      sign = c
      v = 0
    }
  }
  ans := 0
  for _, v := range stk {
    ans += v
  }
  return ans
}

using System.Collections.Generic;
using System.Linq;

struct Element
{
  public char Op;
  public int Number;
  public Element(char op, int number)
  {
    Op = op;
    Number = number;
  }
}

public class Solution {
  public int Calculate(string s) {
    var stack = new Stack<Element>();
    var readingNumber = false;
    var number = 0;
    var op = '+';
    foreach (var ch in ((IEnumerable<char>)s).Concat(Enumerable.Repeat('+', 1)))
    {
      if (ch >= '0' && ch <= '9')
      {
        if (!readingNumber)
        {
          readingNumber = true;
          number = 0;
        }
        number = (number * 10) + (ch - '0');
      }
      else if (ch != ' ')
      {
        readingNumber = false;
        if (op == '+' || op == '-')
        {
          if (stack.Count == 2)
          {
            var prev = stack.Pop();
            var first = stack.Pop();
            if (prev.Op == '+')
            {
              stack.Push(new Element(first.Op, first.Number + prev.Number));
            }
            else // '-'
            {
              stack.Push(new Element(first.Op, first.Number - prev.Number));
            }
          }
          stack.Push(new Element(op, number));
        }
        else
        {
          var prev = stack.Pop();
          if (op == '*')
          {
            stack.Push(new Element(prev.Op, prev.Number * number));
          }
          else // '/'
          {
            stack.Push(new Element(prev.Op, prev.Number / number));
          }
        }
        op = ch;
      }
    }

    if (stack.Count == 2)
    {
      var second = stack.Pop();
      var first = stack.Pop();
      if (second.Op == '+')
      {
        stack.Push(new Element(first.Op, first.Number + second.Number));
      }
      else // '-'
      {
        stack.Push(new Element(first.Op, first.Number - second.Number));
      }
    }

    return stack.Peek().Number;
  }
}