0994HardStringStackRecursion

Working Out a Nested Switch Formula

Tracked in this browser only

Trains the technique from

LeetCode 1106Parsing A Boolean Expression

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A switch formula is given as the string formula, built from these pieces:

't' on its own stands for on, and 'f' on its own stands for off.
'!' followed by one bracketed formula gives the opposite of it.
'&' followed by a bracketed run of one or more formulas separated by commas is on only when every one of them is on.
'|' followed by a bracketed run of one or more formulas separated by commas is on when at least one of them is on.

Return whether the whole formula comes out on.

Examples

Example 1

Input: formula = "&(t,f)"
Output: false

The run under the sign holds one value that is off, and that sign asks for every one of them to be on.

Example 2

Input: formula = "|(&(t,f),&(t,t))"
Output: true

The first bracketed part folds to off, since one of its two values is off. The second folds to on. The outer sign needs only one of them on, so the whole thing comes out on.

Example 3

Input: formula = "!(!(!(f)))"
Output: true

Starting from off, the innermost sign turns it on, the next turns it off again, and the outermost turns it back on.

Constraints

1 <= formula.length <= 2 * 10^4
Every character of formula is one of '(', ')', '&', '|', '!', 't', 'f' and ','.
The formula is well formed, so every bracket is matched and every sign has its run of formulas.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def parse_bool_expr(formula: str) -> bool:

Java

public boolean parseBoolExpr(String formula)

The intended approach

Time O(n) over the formula's length.Space O(n) for the stack, which is as deep as the formula nests.

One pass with a stack settles it, and nothing ever needs looking ahead. Read the characters in order. Drop the commas, since they only separate. Push everything else, so signs, values and opening brackets all go on the stack. On a closing bracket, pop values back until the opening bracket shows up, keeping a tally of how many were on and how many off. Then throw away that bracket, pop the sign sitting under it, and push back the single value the sign gives: the opposite for `'!'`, on when nothing was off for `'&'`, on when something was on for `'|'`. This works because a closing bracket always answers the nearest unclosed opener, so the values popped are exactly that sign's run, and any bracket nested inside has already been folded down to one value by the time the outer one closes. When the string runs out, one value is left, and that is the answer. Every character is pushed and popped at most once.

Pythonentry point: parse_bool_expr

def parse_bool_expr(formula):
    stack = []
    for ch in formula:
        if ch == ',':
            continue
        if ch != ')':
            stack.append(ch)
            continue
        on = 0
        off = 0
        while stack[-1] != '(':
            if stack.pop() == 't':
                on += 1
            else:
                off += 1
        stack.pop()
        sign = stack.pop()
        if sign == '!':
            stack.append('f' if on else 't')
        elif sign == '&':
            stack.append('t' if off == 0 else 'f')
        else:
            stack.append('t' if on else 'f')
    return stack[-1] == 't'

The obvious version

Walk the formula with a moving cursor and a routine that reads whatever formula starts at the cursor and hands back its value. A lone `'t'` or `'f'` is read straight off. Otherwise the routine notes the sign, steps past the opening bracket, calls itself for each part until the closing bracket shows up, then folds the parts it gathered. Leans on the call stack and a cursor instead of a stack of characters.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_parse_bool_expr(formula):
    at = [0]
    def read():
        ch = formula[at[0]]
        if ch == 't' or ch == 'f':
            at[0] += 1
            return ch == 't'
        sign = ch
        at[0] += 2
        parts = []
        while formula[at[0]] != ')':
            if formula[at[0]] == ',':
                at[0] += 1
                continue
            parts.append(read())
        at[0] += 1
        if sign == '!':
            return not parts[0]
        if sign == '&':
            for part in parts:
                if not part:
                    return False
            return True
        for part in parts:
            if part:
                return True
        return False
    return read()

How this problem was checked

Reference solution executed against 20 test cases — 20 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in