> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0772-basic-calculator-iii.md).

# 0772. Basic Calculator III

<https://leetcode.com/problems/basic-calculator-iii>

## Description

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, `'+'`, `'-'`, `'*'`, `'/'` operators, and open `'('` and closing parentheses `')'`. The integer division should **truncate toward zero**.

You may assume that the given expression is always valid. All intermediate results will be in the range of `[-231, 231 - 1]`.

**Note:** You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as `eval()`.

**Example 1:**

```
**Input:** s = "1+1"
**Output:** 2
```

**Example 2:**

```
**Input:** s = "6-4/2"
**Output:** 4
```

**Example 3:**

```
**Input:** s = "2*(5+5*2)/3+(6/2+8)"
**Output:** 21
```

**Example 4:**

```
**Input:** s = "(2+6*3+5-(3*14/7+2)*5)+3"
**Output:** -12
```

**Example 5:**

```
**Input:** s = "0"
**Output:** 0
```

**Constraints:**

* `1 <= s <= 104`
* `s` consists of digits, `'+'`, `'-'`, `'*'`, `'/'`, `'('`, and `')'`.
* `s` is a **valid** expression.

## ac: Stack

```java
class Solution {
    public int calculate(String s) {
        // Edge cases
        if (s == null || s.length() == 0) return 0;
        
        Deque<Character> operators = new ArrayDeque<>();
        Deque<Integer> nums = new ArrayDeque<>();
        
        int currNum = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ' ') continue;
            if (Character.isDigit(c)) {
                currNum = currNum * 10 + (c - '0');
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                while (!operators.isEmpty() && canDoPreviousOperation(operators.peek(), c)) {
                    currNum = doOperation(nums.pop(), operators.pop(), currNum);
                }
                
                operators.push(c);
                nums.push(currNum);
                currNum = 0;
            } else if (c == '(') {
                operators.push('(');
            } else if (c == ')') {
                while (operators.peek() != '(') {
                    currNum = doOperation(nums.pop(), operators.pop(), currNum);
                }
                operators.pop(); // evict '('
            }
        }
        
        while (!operators.isEmpty()) {
            currNum = doOperation(nums.pop(), operators.pop(), currNum);
        }
        
        return currNum;
    }
    
    private int doOperation(int num1, Character operator, int num2) {
        switch (operator) {
            case '+': return num1 + num2;
            case '-': return num1 - num2;
            case '*': return num1 * num2;
            case '/': return num1 / num2;
            default:
                throw new IllegalArgumentException("Invalid operator.");
        }
    }
    
    private boolean canDoPreviousOperation(Character op1, Character op2) {
        if (op1 == '(') return false;
        if (op2 == '+' || op2 == '-') {
            return true;
        } else {
            // op2 is * or /
            if (op1 == '*' || op1 == '/') return true; 
            
            return false;
        }
        
    }
}
/*
E.g. ...(6 - 4 / 2)...
num1, op1, currNum, {currOp}, {num3} ...
1. currOp is +/-, or op1 && currOp both are * or /: currNum = eval(num1, op1, currNum)
2. other cases: currNum = eval(currNum, currOp, num3). Because we don't know whether it is left parenthesis or num3 after currOp, let's push currNum, currOp to stack and do calculation later.
stack operators: [-]
stack nums: [6]
*/
```