Show problems as
Classic problem #1106HardStringStackRecursion

Parsing A Boolean Expression

Real-world version: Working Out a Nested Switch Formula
Tracked in this browser only
Read Parsing A Boolean Expression on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def parse_bool_expr(formula: str) -> bool:
Java
public boolean parseBoolExpr(String formula)

More on the same topics