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-negativeintegers 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 evalbuilt-in library function.

Analysis

link:

https://leetcode.com/problems/basic-calculator/discuss/62362/JAVA-Easy-Version-To-Understand!!!!!

https://leetcode.com/problems/basic-calculator/discuss/62361/Iterative-Java-solution-with-stack

Only 5 possible input we need to pay attention:

1. digit: it should be one digit from the current number and consecutive digits forms sum
2. ‘+’: set the sign to 1;
3. ‘-’: set the sgin to -1;
4. ‘(’: push the previous result and the sign into the stack, set result to 0, just calculate the new result within the parenthesis.
5. ‘)’: pop out the top two numbers from stack, first one is the sign before this pair of parenthesis, second is the temporary result before this pair of parenthesis. We add them together.

Solution from LC Forum

public static int calculate(String s) {
    int len = s.length(), sign = 1, result = 0;
    Stack<Integer> stack = new Stack<Integer>();
    for (int i = 0; i < len; i++) {
        if (Character.isDigit(s.charAt(i))) {
            int sum = s.charAt(i) - '0';
            while (i + 1 < len && Character.isDigit(s.charAt(i + 1))) {
                sum = sum * 10 + s.charAt(i + 1) - '0';
                i++;
            }
            result += sum * sign;
        } else if (s.charAt(i) == '+')
            sign = 1;
        else if (s.charAt(i) == '-')
            sign = -1;
        else if (s.charAt(i) == '(') {
            stack.push(result);
            stack.push(sign);
            result = 0;
            sign = 1;
        } else if (s.charAt(i) == ')') {
            result = result * stack.pop() + stack.pop();
        }

    }
    return result;
}