See all coding puzzles and patterns here.

Problem Definition

Given a string representing a valid math expression, evaluate the expression and return its value. The expression contains the characters [0-9]+-() and does not contain multiplication nor division of any sort. Assume that the input is valid and does not contain any other characters.

Examples

Some test cases to verify our solution.

assert evaluate("1+2+3") == 6
assert evaluate("-(2 + 3)") == -5
assert evaluate("-(3 + 5 + (1 + 2 - (4 - 4)))") == -11
assert evaluate("(3 + 4)") == 7
assert evaluate("   (  3 ) ") == 3
assert evaluate("1-1") == 0

Solution

The string will represent a sequence of items to add, with those items possibly being negative.

For 1+2+3, the items are 1, 2, and 3. For -(2 + 3), the items are -x, with x being its own sum consisting of the items 2 and 3.

For s = -(3 + 5 + (1 + 2 - (4 - 4))), we have:

$$ \begin{gather*} s = \sum\{-x\} \\ x = \sum\{3, 5, y\} \\ y = \sum\{1, 2, -z\} \\ z = \sum\{4, -4\} \end{gather*} $$

As this breakdown suggests, we can use a stack to store the state of the outer calculation while we calculate the inner value - we can store the state of the calculation of s while we calculate the value for x; we can store the state of the calculation of x while we calculate the value for y; etc.

We'll implement our algorithm as follows:

  1. We will create an res variable to contain the current running sum.
  2. We will initialize a num with value 0 to capture newly encountered numbers.
  3. When we encounter a number, we will multiply the existing num by 10 and add the new number to it, thereby constructing our number as we go along.
  4. When we encounter a -, we will note that the next value to be added will be negative.
  5. When we encounter a (, we will push the current state of the current running sum onto a stack in the form of a(res, negative) tuple.
  6. Inside the (, we will start a new res and calculate the sum.
  7. Once we hit a ), we'll pop a frame off our stack and add the current inner res to the outer res, with it possibly negated based on the popped stack frame's negative value.
  8. We will simply ignore all spaces.
  9. Whenever we hit a non-number, other than a space, we will add the existing num to the res.

def evaluate(s: str) -> int:
    res = 0
    negative = False
    stack = []
    num = 0
    for c in s:
        if c == "-":
            res += -num if negative else num
            num = 0
            negative = True
        elif c == "+":
            res += -num if negative else num
            num = 0
            negative = False
        elif c == "(":
            res += -num if negative else num
            num = 0
            stack.append((res, negative))
            res = 0
            negative = False
        elif c == ")":
            res += -num if negative else num
            num = 0
            prev_res, prev_negative = stack.pop()
            res = prev_res + (-res if prev_negative else res)
        elif c != " ":
            num = num * 10 + int(c)
    return res + (-num if negative else num)

Complexity

Let $n =$ len(s).

Runtime complexity should be $\Theta(n)$ since we are traversing the string fully once.

Auxiliary space complexity should be $O(n)$ since we might create roughly $\frac{n}{2} - 1$ elements in our stack. For example, the calculation of something like (((((1))))) would generate 5 stack items.