# 227 Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, \*, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

```
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5.
```

Note: Do not use the eval built-in library function.

**The Idea:** This algorithm follows the same strategy found in Polish Notation String Calculator in Chapter Self. Here, we first remove white spaces and split the characters while keep their delimitors using some regex. Then we perform two recursive operations. The first tries to identify / and *, as per order of operations. The first instance it finds, it solves and reduces the list of tokens with the calculation by the operator. This process recurses on itself (and reduces the list in the process) until all* and / operators are exhausted. Finally the same kind of operation is performed with + and -, except the terminating condition is when we identify a single list element.

**Complexity:** O(n^2) time and O(n) space

```python
import operator
import re

map_op = {'+': operator.add, '-': operator.sub,
          '*': operator.mul, '/': operator.truediv}


class Solution:
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        s = "".join(s.split())
        tokens = re.split('( |\+|\/|\-|\*)', s)
        self._calculateP1(tokens)
        return self._calculateP2(tokens)

    def _calculateP1(self, tokens):
        if '*' not in tokens and '/' not in tokens:
            return
        for i, token in enumerate(tokens):
            if token is '*' or token is '/':
                calc = int(map_op[token](int(tokens[i-1]), int(tokens[i+1])))
                tokens[i-1] = str(calc)
                del tokens[i:i+2]
                return self._calculateP1(tokens)

    def _calculateP2(self, tokens):
        if len(tokens) is 1:
            return int(tokens[0])
        for i, token in enumerate(tokens):
            if token is '+' or token is '-':
                calc = int(map_op[token](int(tokens[i-1]), int(tokens[i+1])))
                tokens[i-1] = str(calc)
                del tokens[i:i+2]
                return self._calculateP2(tokens)
```

**Testing**:

```python
obj = Solution()
print(obj.calculate("1 + 1"))
print(obj.calculate("0-0"))
print(obj.calculate("42"))
print(obj.calculate("3+2*2"))
print(obj.calculate(" 3/2 "))
print(obj.calculate(" 3+5 / 2 "))
print(obj.calculate("1*1*2*2/2/1/1/2/3/2+5+4-9-10/1"))
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/227-basic-calculator-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.