Leetcode

Basic Calculator II

May 26, 2022 by aAshish

Approach 1: Similar to 772. Basic Calculator III

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

C++

 
class Solution {
 public:
  int calculate(string s) {
    stack<int> nums;  // stores nums
    stack<char> ops;  // stores operators

    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');
          ++i;
        }
        nums.push(num);
      } else if (c == '+' || c == '-' || c == '*' || c == '/') {
        while (!ops.empty() && compare(ops.top(), c))
          nums.push(calculate(pop(ops), pop(nums), pop(nums)));
        ops.push(c);
      }
    }

    while (!ops.empty())
      nums.push(calculate(pop(ops), pop(nums), pop(nums)));

    return nums.top();
  }

 private:
  int calculate(char op, int b, int a) {
    switch (op) {
      case '+':
        return a + b;
      case '-':
        return a - b;
      case '*':
        return a * b;
      case '/':
        return a / b;
    }
    throw;
  }

  // return true if priority(op1) >= priority(op2)
  bool compare(char op1, char op2) {
    return op1 == '*' || op1 == '/' || op2 == '+' || op2 == '-';
  }

  char pop(stack<char>& ops) {
    const char op = ops.top();
    ops.pop();
    return op;
  }

  int pop(stack<int>& nums) {
    const int num = nums.top();
    nums.pop();
    return num;
  }
};

JAVA

 
class Solution {
  public int calculate(String s) {
    Deque<Integer> nums = new ArrayDeque<>();  // stores nums
    Deque<Character> ops = new ArrayDeque<>(); // stores operators and parentheses

    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');
          ++i;
        }
        nums.push(num);
      } else if (c == '+' || c == '-' || c == '*' || c == '/') {
        while (!ops.isEmpty() && compare(ops.peek(), c))
          nums.push(calculate(ops.pop(), nums.pop(), nums.pop()));
        ops.push(c);
      }
    }

    while (!ops.isEmpty())
      nums.push(calculate(ops.pop(), nums.pop(), nums.pop()));

    return nums.peek();
  }

  private int calculate(char op, int b, int a) {
    switch (op) {
      case '+':
        return a + b;
      case '-':
        return a - b;
      case '*':
        return a * b;
      case '/':
        return a / b;
    }
    throw new IllegalArgumentException();
  }

  // return true if priority(op1) >= priority(op2)
  private boolean compare(char op1, char op2) {
    return op1 == '*' || op1 == '/' || op2 == '+' || op2 == '-';
  }
}

Python

 
class Solution:
  def calculate(self, s: str) -> int:
    ans = 0
    prevNum = 0
    currNum = 0
    op = '+'

    for i, c in enumerate(s):
      if c.isdigit():
        currNum = currNum * 10 + int(c)
      if not c.isdigit() and c != ' ' or i == len(s) - 1:
        if op == '+' or op == '-':
          ans += prevNum
          prevNum = currNum if op == '+' else -currNum
        elif op == '*':
          prevNum = prevNum * currNum
        elif op == '/':
          if prevNum < 0:
            prevNum = ceil(prevNum / currNum)
          else:
            prevNum = prevNum // currNum
        op = c
        currNum = 0

    return ans + prevNum

Approach 2: $O(1)$ space

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

C++

 
class Solution {
 public:
  int calculate(string s) {
    int ans = 0;
    int prevNum = 0;
    int currNum = 0;
    char op = '+';

    for (int i = 0; i < s.length(); ++i) {
      const char c = s[i];
      if (isdigit(c))
        currNum = currNum * 10 + (c - '0');
      if (!isdigit(c) && !isspace(c) || i == s.length() - 1) {
        if (op == '+' || op == '-') {
          ans += prevNum;
          prevNum = op == '+' ? currNum : -currNum;
        } else if (op == '*') {
          prevNum *= currNum;
        } else if (op == '/') {
          prevNum /= currNum;
        }
        op = c;
        currNum = 0;
      }
    }

    return ans + prevNum;
  }
};

JAVA

 
class Solution {
  public int calculate(String s) {
    int ans = 0;
    int currNum = 0;
    int prevNum = 0;
    char op = '+';

    for (int i = 0; i < s.length(); ++i) {
      final char c = s.charAt(i);
      if (Character.isDigit(c))
        currNum = currNum * 10 + (c - '0');
      if (!Character.isDigit(c) && c != ' ' || i == s.length() - 1) {
        if (op == '+' || op == '-') {
          ans += prevNum;
          prevNum = op == '+' ? currNum : -currNum;
        } else if (op == '*') {
          prevNum *= currNum;
        } else if (op == '/') {
          prevNum /= currNum;
        }
        op = c;
        currNum = 0;
      }
    }

    return ans + prevNum;
  }
}

Python

 
class Solution:
  def calculate(self, s: str) -> int:
    ans = 0
    prevNum = 0
    currNum = 0
    op = '+'

    for i, c in enumerate(s):
      if c.isdigit():
        currNum = currNum * 10 + int(c)
      if not c.isdigit() and c != ' ' or i == len(s) - 1:
        if op == '+' or op == '-':
          ans += prevNum
          prevNum = (currNum if op == '+' else -currNum)
        elif op == '*':
          prevNum *= currNum
        elif op == '/':
          prevNum = int(prevNum / currNum)
        op = c
        currNum = 0

    return ans + prevNum