LeetCode Q 224 - Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

Example 1: Input: "1 + 1" ; Output: 2
Example 2: Input: " 2-1 + 2 " ; Output: 3
Example 3: Input: "(1+(4+5+2)-3)+(6+8)" ; Output: 23

Note:

You may assume that the given expression is always valid.
Do not use the eval built-in library function.

Solution

The key point is how we deal with “( )”.

Whenever we encounter a ‘(‘, we push the current number and sign into stack.
Whenever we encounter a ‘)’, we pop the sign and number in the stack and do the calculation.

Code:

public int calculate(String s) {
  int res = 0, sign = 1, temp = 0;
  Stack<Integer> stack = new Stack<>();

  for (int i = 0; i < s.length(); i++) {
    if (s.charAt(i) == ' ') {
      continue;
    } else if (Character.isDigit(s.charAt(i))) {
      temp = temp * 10 + (s.charAt(i) - '0');
    } else if (s.charAt(i) == '+') {
      res += sign * temp; sign = 1; temp = 0;
    } else if (s.charAt(i) == '-') {
      res += sign * temp; sign = -1; temp = 0;
    } else if (s.charAt(i) == '(') {
      stack.push(res); stack.push(sign);
      res = 0; sign = 1;
    } else if (s.charAt(i) == ')') {
      res += sign * temp; temp = 0;
      res *= stack.pop(); res += stack.pop();
    }
  }

  if (temp != 0)
    res += sign * temp;
  return res;
}

Code: A more intuitional version

public int calculate(String s) {
  if (s == null || s.length() == 0) return 0;

  Deque<Integer> stack = new ArrayDeque<>();
  int sum = 0, sign = 1;

  for (int i = 0; i < s.length(); i++) {
    char ch = s.charAt(i);
    if (ch == ' ') continue;
    
    if (Character.isDigit(ch)) {
      int num = 0;
      while (i < s.length() && Character.isDigit(s.charAt(i)))
        num = num * 10 + s.charAt(i++) - '0';
      sum += sign * num; i--;
    } else {
      if (ch == '+') sign = 1;
      if (ch == '-') sign = -1;
      if (ch == '(') {
        stack.push(sum); stack.push(sign);
        sum = 0; sign = 1;
      }
      if (ch == ')') {
        sum *= stack.pop(); sum += stack.pop();
      } 
    }
  }

  return sum;
}

Reprint policy