LeetCode 224: Basic Calculator

link

We want to process the string as a sequence of tokens where each token is an operator or an opening (or closing) parenthesis or a multi-digit number. So, we use a stack to store tokens as we process the string from left-to-right.

All binary operators, no parentheses

If we only had binary operators and no parentheses, our expression would look like:

$\texttt{exp} = \begin{cases} \texttt{number} \\ \texttt{exp} + \texttt{exp} \\ \texttt{exp} - \texttt{exp} \end{cases}$

As soon as we see a subsequence of three tokens like: $\langle \texttt{number}, \texttt{op}, \texttt{number} \rangle$ , we can replace the subsequence with the evaluated value or number.

All binary operators, with parentheses

If we had parentheses as well, our expression would like:

$\texttt{exp} = \begin{cases} \texttt{number} \\ \texttt{exp} + \texttt{exp} \\ \texttt{exp} - \texttt{exp} \\ (\texttt{exp}) \end{cases}$

We could record opening parentheses and when we see a closing parenthesis, we could evaluate operators backwards until the recent-most opening parenthesis. If we reuse the processing from the “All binary operators, no parentheses” case, additional processing involves short token subsequences like: $\langle\ (, \texttt{number}, ) \ \rangle$ or $\langle\ (, \texttt{number}, \texttt{op}, \texttt{number}, )\ \rangle$ . So, our backwards work, when we see a closing parenthesis, is still constant.

With unary negative

If we also have unary negative, our expression looks like:

$\texttt{exp} = \begin{cases} \texttt{number} \\ \texttt{exp} + \texttt{exp} \\ \texttt{exp} - \texttt{exp} \\ (\texttt{exp}) \\ - \texttt{exp}\end{cases}$

The number of operands for an operator aren’t alway two anymore. To reduce the problem to the all-binary case above, when we see a unary negative operator, we append a $0$ as its left operand. Note, a unary negative appears at the very beginning or right after an opening parenthesis like: $\langle\ -2+3 \ldots\ \rangle$ or $\langle\ \ldots (-2+3 \ldots\ \rangle$ .

Time: $\mathcal{O}(n)$ , space: same.

class Solution:
    def evaluate_binary_op(self, tokens) -> int:
        right = tokens.pop()
        op = tokens.pop()
        left = tokens.pop()

        if op == "+":
            tokens.append(left+right)
        else:
            tokens.append(left-right)

    def is_unary_negative(self, c, tokens) -> bool:
        return c == "-" and (not tokens or tokens[-1] == "(")

    def can_evaluate_binary_op(self, tokens) -> bool:
        def is_operator(token) -> bool:
            return isinstance(token, str) and token in "+-"

        def is_operand(token) -> bool:
            return isinstance(token, int)

        if len(tokens) < 3:
            return False

        return (
            is_operand(tokens[-3])
            and is_operator(tokens[-2])
            and is_operand(tokens[-1])
        )

    def calculate(self, s: str) -> int:
        num = None
        tokens = []
        sign = 1

        for c in s:
            if c == " ":
                continue
                
            if c.isdigit():
                d = int(c)
                num = d if num is None else (10 * num + d)
                continue

            if num is not None:
                tokens.append(num)
                num = None

            if c == "(":
                tokens.append(c)
                continue

            if self.is_unary_negative(c, tokens):
                # Make it binary negative
                tokens.append(0)
                tokens.append(c)
                continue

            if c in "+-":
                if self.can_evaluate_binary_op(tokens):
                    self.evaluate_binary_op(tokens)
                tokens.append(c)

            if c == ")":
                if self.can_evaluate_binary_op(tokens):
                    self.evaluate_binary_op(tokens)
                result = tokens.pop()
                # Throw away the matching "("
                tokens.pop()
                tokens.append(result)

        # If the string ended with a number
        if num is not None:
            tokens.append(num)

        # One binary op might be leftover
        if len(tokens) > 1:
            self.evaluate_binary_op(tokens)

        return tokens[-1]

All negatives as unary

Unary negative operator just changes the sign of either the next number or $( \cdots )$ . Since, $2 - 3 = 2 + (-3)$ , we can interpret all negative operators as unary or sign operator. So, our problem is then to sum a sequence of signed numbers. For example, the expression $3 - 1 - (4 - 1) + 5$ is like $\sum\langle +3, -1, -(4-1), +5 \rangle$ .

To evaluate a parenthesized signed number like $-(4-1)$ we use stack. When we start evaluating $-(4 - 1)$ , we first save the earlier sum: $\sum\langle 3, -1 \rangle$ and the sign ‘-‘ of the parenthesized number. Once we are done evaluating $(4 - 1)$ , we apply the saved sign and add the result to the saved earlier sum.

class Solution:
    def calculate(self, s: str) -> int:
        val, x = 0, 0
        sign = 1
        stack = []
        for c in s:
            if c == " ":
                continue

            if c.isdigit():
                x = 10*x + int(c)
                continue
            
            match c:
                case "+":
                    val += (sign * x)
                    # Sign for the next number
                    sign = 1
                case "-":
                    val += (sign * x)
                    # Sign for the next number
                    sign = -1
                # Use stack to evaluate: 
                # earlier_val + sign * ( ... )
                case "(":
                    # save earlier_val
                    stack.append( val )
                    # save sign
                    stack.append( sign )

                    # Reset val and sign to evaluate ( ... )
                    val = 0
                    sign = 1
                case ")":
                    # val = ( ... )
                    val += (sign * x)
                    
                    saved_sign = stack.pop()
                    earlier_val = stack.pop()
                    val = earlier_val + saved_sign * val

            # Parsed number has already been used
            x = 0
            
        # If string ends with a number
        return val + (sign * x)

unreasonably effective