Problem statement

https://binarysearch.com/problems/Calculator/

Solution

Similar to Leetcode 0772 Basic Calculator III, but here we need to deal with cases like -13*-12/3, so we can have -12 without brackets. So, here I borrowed solution, where redval() will read the next number and readterm() will read the next term of multiplictoin/division.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        s = deque(s)

        def readval():
            sign = -1 if s[0] == "-" else 1
            if s and s[0] == "-": s.popleft()
            val = 0
            while s and s[0].isdigit():
                val = val * 10 + int(s.popleft())
            return sign * val

        def readterm():
            term = readval()
            while s and s[0] in "*/":
                op = s.popleft()
                val = readval()
                term = term * val if op == "*" else floor(1.0 * term / val)
            return term

        ans = readterm()
        while s:
            op, term = s.popleft(), readterm()
            ans += term if op == "+" else -term
        return ans