224. Basic-Calculator

difficulty: Hard

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

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

Note:

• You may assume that the given expression is always valid.

• Do not use the eval built-in library function.

Method One

class Solution {
    public int calculate(String s) {
        Queue<Character> tokens = new ArrayDeque<>();
        for( char c : s.toCharArray() ) {
            if( c == ' ') {
                continue;
            }
            tokens.offer(c);
        }
        tokens.offer('t');
        return evaluate(tokens);
    }
​
    public int evaluate( Queue<Character> tokens ) {
        int sum = 0;
        int preNum = 0;
        char preOp = '+';
        int num = 0;

        while(  !tokens.isEmpty() ) {
            char c = tokens.poll();
            if( '0' <= c && c <= '9' ) {
                num = num*10 + (c - '0');
            }else if( c == '(') {
                num = evaluate(tokens);
            }else{
                switch(preOp) {
                    case '+':
                        sum += preNum;
                        preNum = num;
                        break;
                    case '-':
                        sum += preNum;
                        preNum = -num;
                        break;
                    case '*':
                        preNum *= num;
                        break;
                    case '/':
                        preNum /= num;
                        break;
                }
                if( c == ')') {
                    break;
                }
                preOp = c;
                num = 0;
            }
        }
        return sum + preNum;
    }
}
​