LeetCode Q 227 - Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces. The integer division should truncate toward zero.

Example 1: Input: "3+2*2" ; Output: 7
Example 2: Input: " 3/2 " ; Output: 1
Example 3: Input: " 3+5 / 2 " ; Output: 5

Note:

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

Solution

We use a stack to store numbers during calculation.

When we meet a ‘+’ or ‘-‘, we push num or -num into the stack, then update the sign and num;
When we meet a ‘*‘ or ‘/‘, we multiply or divide the popped number from stacknum by num, then push the result into the stack, then update the sign and num.

Code:

public int calculate(String s) {
  if (s == null || s.length() == 0) return 0;
  
  Deque<Integer> stack = new ArrayDeque<>();
  char sign = '+';
  
  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 = 10 * num + s.charAt(i++) - '0';

      if (sign == '+') stack.push(num);
      if (sign == '-') stack.push(-num);
      if (sign == '*') stack.push(stack.pop() * num);
      if (sign == '/') stack.push(stack.pop() / num);
      i--;
    } else {
      sign = ch;
    } 
  }
  
  int sum = 0;
  for (int num: stack) sum += num;
  
  return sum;
}

Reprint policy