Leetcode: 224. Basic Calculator

Mistake: Missing edge case. I came up with -(-2) and forgot about (8) which is also a valid expression.

The trick part is how we are going to handle the unary minus operator. Can we simplify the problem while keeping it the same? It would make the problem easier if all operator were binary what would require to transform -2 in 0-2. There is only two cases were - is an unary operator: (1) it occurs in the beginning of the stack or (2) after an open parentheses. While parsing, we can insert a 0 at the right moment and make sure that all operators are binary. Time and space complexity is \(O(n)\).

class Solution:
    def calculate(self, s: str) -> int:
        s = "(" + s + ")"

        st = []
        op = []
        i = 0
        maybe_unary = None

        while i < len(s):
            if s[i] == "(":
                op.append("(")
                maybe_unary = True
                i += 1
            elif "0" <= s[i] <= "9":
                j = i
                n = 0
                while j < len(s) and "0" <= s[j] <= "9":
                    n = n * 10 + ord(s[j]) - ord("0")
                    j += 1
                st.append(n)
                maybe_unary = False
                i = j
            elif s[i] == " ":
                i += 1
            else:
                while len(op) > 0:
                    if op[-1] == "+":
                        b = st.pop()
                        a = st.pop()
                        st.append(a + b)
                        op.pop()
                    elif op[-1] == "-":
                        b = st.pop()
                        a = st.pop()
                        st.append(a - b)
                        op.pop()
                    elif op[-1] == "(":
                        if s[i] == ")":
                            op.pop()
                        break

                if s[i] == "-" and maybe_unary:
                    st.append(0)

                if s[i] != ")":
                    op.append(s[i])

                maybe_unary = False
                i += 1

        return st[0]

assert Solution().calculate("1 + 1") == 2
assert Solution().calculate(" 2-1 + 2 ") == 3
assert Solution().calculate("(1+(4+5+2)-3)+(6+8)") == 23
assert Solution().calculate("-(-2)") == 2
assert Solution().calculate("(2)") == 2

class Solution:
    def calculate(self, s: str) -> int:
        s = "(" + s + ")"
        N = len(s)

        def dfs(i, left, right, sign):
            if i == N:
                return left + sign * right

            if s[i] == " ":
                return dfs(i + 1, left, right, sign)

            if s[i].isdigit():
                j = i
                while j < N and s[j].isdigit():
                    j += 1
                return dfs(j, left, int(s[i:j]), sign)

            if s[i] in "+-":
                return dfs(i + 1, left + sign * right, 0, +1 if s[i] == "+" else -1)

            if s[i] == "(":
                ni, right = dfs(i + 1, 0, 0, +1)
                return dfs(ni, left + sign * right, 0, +1)

            return i + 1, left + sign * right

        return dfs(0, 0, 0, +1)