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

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:

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"))