# 772 Basic Calculator III

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

Constraints:

• `1 <= s <= 104`
• `s` consists of digits, `'+'`, `'-'`, `'*'`, `'/'`, `'('`, and `')'`.
• `s` is a valid expression.
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 `````` ``````from collections import deque class Solution: def calculate(self, s: str) -> int: def calc(s: List) -> int: stack = [] sign = '+' num = 0 while len(s) > 0: c = s.popleft() if c.isdigit(): num = 10 * num + int(c) if c == '(': num = calc(s) if (not c.isdigit() and c != ' ') or len(s) == 0: if sign == '+': stack.append(num) elif sign == '-': stack.append(-num) elif sign == '*': stack[-1] = stack[-1] * num elif sign == '/': stack[-1] = int(stack[-1] / float(num)) num = 0 sign = c if c == ')': break return sum(stack) return calc(collections.deque(s))``````