> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/227-basic-calculator-ii.md).

# 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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.