Problem statement

https://binarysearch.com/problems/S-Expression-Evaluation/

Solution

  1. First of all, let us create d is correspondence between open and closing brackets.
  2. part(i) function will do the following, if symbol s[i] is - or digit, we grab this number. If it is brackets, we find closing bracket and evaluate expression inside. What is returned is value, index of last traversed element.
  3. Now, dp(i) will deal with string recursively. First, we create first part, then second, then apply operation. Notice, that we need this part function, because we can have cases (- 123 123), (+ 123 (...)), (* (...) 123), (/ (...) (...)).
  4. Also be careful about division.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        def corr(s):
            stack, d = [], {}
            for i, elem in enumerate(s):
                if elem == "(":
                    stack.append(i)
                elif elem == ")":
                    last = stack.pop()
                    d[last] = i
            return d

        def op(x, y, o):
            if o == "-": return x - y
            if o == "+": return x + y
            if o == "/": 
                sgn = -1 if x * y < 0 else 1
                return sgn * (abs(x) // abs(y))
            if o == "*": return x * y

        def part(i):
            if s[i] == "(":
                return (dp(i), d[i] + 1)
            else:
                j = i
                while s[j + 1].isdigit(): j += 1
                return (int(s[i: j+1]), j + 1)

        def dp(i):
            part1, idx = part(i + 3)
            part2, _ = part(idx + 1)
            return op(part1, part2, s[i + 1])

        d = corr(s)
        return dp(0)