224. Basic Calculator

Problem:

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

9/19/2018 update:

• 在读取数的时候，要检验i+1, 而不是i,否则i会在外层循环重复加

--------------------------------------------------------------------------------------------------------------------------
Analysis:
Use stack, stack only stores sign and number.
For example: 2 + 3 - (4 + 5)
1. meet digit, calc current res with sign
2. meet left parentheses: add sign and current result to stack
3. meet right parentheses: minus or plus current result base on stack top sign, then combine current result and cached result.

input
2
	sign	1
	res	2
(+)
	sign	1
3
	res	2 + 3 = 5
-
	sign	-1
(
	stack	-,5]
4
	res	4
(+)
	sign	1
5
	res	9
)
		res*-1 + 5

Solution:

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        int sign = 1;
        for (int i = 0; i < s.length(); i++) {
            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++;
                }
                res += num*sign;
            } else if (c == '+') {
                sign = 1;
            } else if (c == '-') {
                sign = -1;
            } else if (c == '(') {
                stack.push(res);
                stack.push(sign);
                res = 0;
                sign = 1;
            } else if (c == ')') {
                res = res*stack.pop() + stack.pop();
            }
        }
        return res;
    }
}