[LeetCode] 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 .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

Thought process:

Iterate through string. Use a variable to store the previous operation (+ / -). If it's -, that means I need to add (-1) * number. There are six cases:

1. Number: keep track of current number. Only perform an operation when I see + or -, because number can have more than one digit.
2. Space: do nothing.
3. +: add sign * number to result. Set sign to 1 and reset number.
4. -: add sign * number to result. Set sign to -1 and reset number.
5. (: Push previous result and sign onto stack. Reset result to start calculation inside parentheses.
6. ): Store result inside the parentheses into number. Pop the previous sign and result.

At the end, add sign * last number.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

public class Solution { public int calculate(String s) { Stack<Integer> stack = new Stack<>(); int result = 0; int sign = 1; int number = 0; for (char c : s.toCharArray()) { if (Character.isDigit(c)) { number = number * 10 + (c - '0'); } else if (c == '+') { result += sign * number; sign = 1; number = 0; } else if (c == '-') { result += sign * number; sign = -1; number = 0; } else if (c == '(') { stack.push(result); stack.push(sign); result = 0; sign = 1; } else if (c == ')') { result += sign * number; number = result; sign = stack.pop(); result = stack.pop(); } } result += sign * number; return result; } }

Time complexity: O(n).