How hard is LeetCode 1106. Parsing A Boolean Expression?

LeetCode 1106. Parsing A Boolean Expression is rated Hard on LeetCode.

What is the time complexity of LeetCode 1106. Parsing A Boolean Expression?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1106. Parsing A Boolean Expression?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1106. Parsing A Boolean Expression cover?

LeetCode 1106. Parsing A Boolean Expression is tagged Stack, Recursion and String on LeetCode.

Parsing A Boolean Expression — LeetCode 1106 Python Solution

HardStackRecursionString

Problem: #1106
Pattern: Stack
Reading time: 4 min
Source: leetcode.com

The problem

A boolean expression is an expression that evaluates to either true or false. It can be in one of the following shapes: 't' that evaluates to true.

Example

Input: expression = "&(|(f))"
Output: false
Explanation: First, evaluate |(f) --> f. The expression is now "&(f)".

Python solution

Python

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        stk = []
        for c in expression:
            if c in 'tf!&|':
                stk.append(c)
            elif c == ')':
                t = f = 0
                while stk[-1] in 'tf':
                    t += stk[-1] == 't'
                    f += stk[-1] == 'f'
                    stk.pop()
                match stk.pop():
                    case '!':
                        c = 't' if f else 'f'
                    case '&':
                        c = 'f' if f else 't'
                    case '|':
                        c = 't' if t else 'f'
                stk.append(c)
        return stk[0] == 't'

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 1106. Parsing A Boolean Expression is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1106. Parsing A Boolean Expression?: LeetCode 1106. Parsing A Boolean Expression is rated Hard on LeetCode.
What is the time complexity of LeetCode 1106. Parsing A Boolean Expression?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1106. Parsing A Boolean Expression?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1106. Parsing A Boolean Expression cover?: LeetCode 1106. Parsing A Boolean Expression is tagged Stack, Recursion and String on LeetCode.