# 224. Basic-Calculator

difficulty: Hard

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

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
```

&#x20;**Note:**

* You may assume that the given expression is always valid.
* **Do not** use the `eval` built-in library function.

## Method One

```java
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;
    }
}
​
```
