LeetCode 224. Basic Calculator

December 02, 2020

Since we only have $+$ , $-$ , and $()$ , we can process the input from left to right. We can use a stack to cache parenthesized contents.

The stack solution:

For each char, $c$ :

peek the top of the stack, $t$
if $c$ and $t$ are both numbers, pop the stack and push $t+c$
if $c$ is a number and $t$ is $-$ , pop the stack and push $-c$
if $c$ is a number and $t$ is none of the above, push $c$
if $c$ is $($ or $-$ push $c$
if $c$ is $)$ pop the stack until the corresponding $($ is popped, sum the intervening numbers, and push that sum

After this, the stack should contain only numbers that we can sum for the result

The time and space complexities are both $O(n)$ . We're popping and pushing back onto the stack, but that's all an amortized $O(n)$ since we handle a given number at most 2 times in the stack (once when we add it and again when we squash it).

import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.calculate("1 + 1"), 2)
        self.assertEqual(self.s.calculate(" 2-1 + 2 "), 3)
        self.assertEqual(self.s.calculate("(1+(4+5+2)-3)+(6+8)"), 23)
        self.assertEqual(self.s.calculate("2147483647"), 2147483647)

    def test_empty(self):
        # empty string should be an error(?), but we'll use 0 for now
        self.assertEqual(self.s.calculate(""), 0)
        self.assertEqual(self.s.calculate("     "), 0)
        self.assertEqual(self.s.calculate("()"), 0)
        self.assertEqual(self.s.calculate("( )"), 0)
        self.assertEqual(self.s.calculate("  (   )   "), 0)

    def test_nesting(self):
        self.assertEqual(self.s.calculate("1 + (2 + 3 + (1 + ( 4 + 5) + 3))"), 19)
        self.assertEqual(self.s.calculate("1 + (2 + 3 + 1 + 4 + 5 + 3)"), 19)
        self.assertEqual(self.s.calculate("1 + (2 + (3 + 1 + 4 + 5 + 3))"), 19)
        self.assertEqual(self.s.calculate("1 + (2 + (3 + (1 + 4 + 5 + 3)))"), 19)
        self.assertEqual(self.s.calculate("1 + (2 + (3 + (1 + (4 + 5 + 3))))"), 19)
        self.assertEqual(self.s.calculate("1 + (2 + (3 + (1 + (4 + 5 + (3)))))"), 19)
        self.assertEqual(self.s.calculate("((((((1) + 2) + 3) + 1) + 4) + 5) + 3"), 19)

    def test_sibling_parens(self):
        self.assertEqual(self.s.calculate("1 + (2 + 3) + (1 + 4) + 5 + (3)"), 19)

    def test_negatives(self):
        self.assertEqual(self.s.calculate("1 + (2 - 3 + (1 + ( 4 - 5) + 3))"), 3)
        self.assertEqual(self.s.calculate("1 - (2 - 3 + (1 + ( 4 - 5) + 3))"), -1)
        self.assertEqual(self.s.calculate("1 - (2 - 3 + (1 + ( 4 - 5) - 3))"), 5)
    
class Solution:

    def calculate(self, s: str) -> int:
        numbers = {str(x) for x in range(10)}
        st = []
        num = ""
        for c in "("+s+")":
            if num and not c.isnumeric():
                if st and st[-1] == "-":
                    st[-1] = -int(num)
                elif st and isinstance(st[-1], int):
                    st[-1] += int(num)
                else:
                    st.append(int(num))
                num = ""
            if c.isnumeric():
                num += c
            elif c == "(" or c == "-":
                st.append(c)
            elif c == ")": 
                squash = 0 
                while st:
                    c = st.pop()
                    if c == "(":
                        break
                    squash += c
                if st and st[-1] == "-":
                    st[-1] = -squash
                else:
                    st.append(squash)
        return sum(st)

if __name__ == "__main__":
    unittest.main()