Basic Calculator

Description

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.

Hint

Train of Thought

Thanks for your answer. The following answer might be more slick (18ms):

Principle:

(Sign before '+'/'-') = (This context sign); (Sign after '+'/'-') = (This context sign) * (1 or -1); Algorithm:

Start from +1 sign and scan s from left to right; if c == digit: This number = Last digit 10 + This digit; if c == '+': Add num to result before this sign; This sign = Last context sign 1; clear num; if c == '-': Add num to result before this sign; This sign = Last context sign * -1; clear num; if c == '(': Push this context sign to stack; if c == ')': Pop this context and we come back to last context; Add the last num. This is because we only add number after '+' / '-'.

Code

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

int result = 0;
int sign = 1;
int num = 0;

Stack<Integer> stack = new Stack<Integer>();
stack.push(sign);

for(int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);

    if(c >= '0' && c <= '9') {
        num = num * 10 + (c - '0');

    } else if(c == '+' || c == '-') {
        result += sign * num;
        sign = stack.peek() * (c == '+' ? 1: -1); 
        num = 0;

    } else if(c == '(') {
        stack.push(sign);

    } else if(c == ')') {
        stack.pop();
    }
}

result += sign * num;
return result;

}

Complexity