772. Basic Calculator III

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  int calculate(string s) {
    stack<int> nums;
    stack<int> ops;
    bool hasPrevNum = false;

    auto calc = [&]() {
      const int b = nums.top();
      nums.pop();
      const int a = nums.top();
      nums.pop();
      const char op = ops.top();
      ops.pop();
      if (op == '+')
        nums.push(a + b);
      else if (op == '-')
        nums.push(a - b);
      else if (op == '*')
        nums.push(a * b);
      else  // op == '/'
        nums.push(a / b);
    };

    for (int i = 0; i < s.length(); ++i) {
      const char c = s[i];
      if (isdigit(c)) {
        int num = c - '0';
        while (i + 1 < s.length() && isdigit(s[i + 1]))
          num = num * 10 + (s[i++ + 1] - '0');
        nums.push(num);
        hasPrevNum = true;
      } else if (c == '(') {
        ops.push('(');
        hasPrevNum = false;
      } else if (c == ')') {
        while (ops.top() != '(')
          calc();
        ops.pop();  // Pop '('.
      } else if (c == '+' || c == '-' || c == '*' || c == '/') {
        if (!hasPrevNum)
          nums.push(0);
        while (!ops.empty() && precedes(ops.top(), c))
          calc();
        ops.push(c);
      }
    }

    while (!ops.empty())
      calc();

    return nums.top();
  }

 private:
  // Returns true if the previous character is a operator and the priority of
  // the previous operator >= the priority of the current character (operator).
  bool precedes(char prev, char curr) {
    if (prev == '(')
      return false;
    return prev == '*' || prev == '/' || curr == '+' || curr == '-';
  }
};

class Solution {
  public int calculate(String s) {
    Deque<Integer> nums = new ArrayDeque<>();
    Deque<Character> ops = new ArrayDeque<>();
    boolean hasPrevNum = false;

    for (int i = 0; i < s.length(); ++i) {
      final char c = s.charAt(i);
      if (Character.isDigit(c)) {
        int num = c - '0';
        while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1)))
          num = num * 10 + (s.charAt(i++ + 1) - '0');
        nums.push(num);
        hasPrevNum = true;
      } else if (c == '(') {
        ops.push('(');
        hasPrevNum = false;
      } else if (c == ')') {
        while (ops.peek() != '(')
          calc(nums, ops);
        ops.pop(); // Pop '('.
      } else if (c == '+' || c == '-' || c == '*' || c == '/') {
        if (!hasPrevNum)
          nums.push(0);
        while (!ops.isEmpty() && precedes(ops.peek(), c))
          calc(nums, ops);
        ops.push(c);
      }
    }

    while (!ops.isEmpty())
      calc(nums, ops);

    return nums.peek();
  }

  private void calc(Deque<Integer> nums, Deque<Character> ops) {
    final int b = nums.pop();
    final int a = nums.pop();
    final char op = ops.pop();
    if (op == '+')
      nums.push(a + b);
    else if (op == '-')
      nums.push(a - b);
    else if (op == '*')
      nums.push(a * b);
    else // op == '/'
      nums.push(a / b);
  }

  // Returns true if the previous character is a operator and the priority of
  // the previous operator >= the priority of the current character (operator).
  private boolean precedes(char prev, char curr) {
    if (prev == '(')
      return false;
    return prev == '*' || prev == '/' || curr == '+' || curr == '-';
  }
}

class Solution:
  def calculate(self, s: str) -> int:
    nums = []
    ops = []

    def calc():
      b = nums.pop()
      a = nums.pop()
      op = ops.pop()
      if op == '+':
        nums.append(a + b)
      elif op == '-':
        nums.append(a - b)
      elif op == '*':
        nums.append(a * b)
      else:  # op == '/'
        nums.append(int(a / b))

    def precedes(prev: str, curr: str) -> bool:
      """
      Returns True if the previous character is a operator and the priority of
      the previous operator >= the priority of the current character (operator).
      """
      if prev == '(':
        return False
      return prev in '*/' or curr in '+-'

    i = 0
    hasPrevNum = False

    while i < len(s):
      c = s[i]
      if c.isdigit():
        num = int(c)
        while i + 1 < len(s) and s[i + 1].isdigit():
          num = num * 10 + int(s[i + 1])
          i += 1
        nums.append(num)
        hasPrevNum = True
      elif c == '(':
        ops.append('(')
        hasPrevNum = False
      elif c == ')':
        while ops[-1] != '(':
          calc()
        ops.pop()  # Pop '('
      elif c in '+-*/':
        if not hasPrevNum:  # Handle input like "-1-(-1)"
          num.append(0)
        while ops and precedes(ops[-1], c):
          calc()
        ops.append(c)
      i += 1

    while ops:
      calc()

    return nums.pop()