# Solving Leetcode Interviews in Seconds with AI: Parsing A Boolean Expression


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "1106" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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. 'f' that evaluates to false. '!(subExpr)' that evaluates to the logical NOT of the inner expression subExpr. '&(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical AND of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1. '|(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical OR of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1.  Given a string expression that represents a boolean expression, return the evaluation of that expression. It is guaranteed that the given expression is valid and follows the given rules.   Example 1:  Input: expression = "&(|(f))" Output: false Explanation:  First, evaluate |(f) --> f. The expression is now "&(f)". Then, evaluate &(f) --> f. The expression is now "f". Finally, return false.  Example 2:  Input: expression = "|(f,f,f,t)" Output: true Explanation: The evaluation of (false OR false OR false OR true) is true.  Example 3:  Input: expression = "!(&(f,t))" Output: true Explanation:  First, evaluate &(f,t) --> (false AND true) --> false --> f. The expression is now "!(f)". Then, evaluate !(f) --> NOT false --> true. We return true.    Constraints:  1 <= expression.length <= 2 * 104 expression[i] is one following characters: '(', ')', '&', '|', '!', 't', 'f', and ','.  

	# Explanation
	*   **Recursive Evaluation:** The solution uses recursion to evaluate the boolean expression. The main function `evaluate` identifies the outermost operator and recursively calls itself to evaluate the sub-expressions within the operator's scope.
*   **Operator Handling:** The function handles the different operators ('!', '&', '|') by processing the sub-expressions based on the operator's logic (NOT, AND, OR).
*   **Base Cases:** The base cases for the recursion are 't' (true) and 'f' (false), which directly return their boolean values.

*   **Runtime Complexity:** O(n), where n is the length of the expression string.
*   **Storage Complexity:** O(d), where d is the maximum depth of the recursion, which in the worst case can be O(n).

	
	# Code
	```python
	def evaluate(expression: str) -> bool:
    """
    Evaluates a boolean expression represented as a string.

    Args:
        expression: The boolean expression string.

    Returns:
        The boolean evaluation of the expression.
    """

    if expression == "t":
        return True
    if expression == "f":
        return False

    if expression[0] == "!":
        return not evaluate(expression[2:-1])
    elif expression[0] == "&":
        sub_expressions = split_sub_expressions(expression[2:-1])
        result = True
        for sub_expression in sub_expressions:
            result = result and evaluate(sub_expression)
        return result
    elif expression[0] == "|":
        sub_expressions = split_sub_expressions(expression[2:-1])
        result = False
        for sub_expression in sub_expressions:
            result = result or evaluate(sub_expression)
        return result
    else:
        raise ValueError("Invalid expression")


def split_sub_expressions(expression: str) -> list[str]:
    """
    Splits a comma-separated list of expressions into a list of individual expressions.

    Args:
        expression: The comma-separated expression string.

    Returns:
        A list of individual expression strings.
    """

    sub_expressions = []
    count = 0
    start = 0
    for i, char in enumerate(expression):
        if char == "(":
            count += 1
        elif char == ")":
            count -= 1
        elif char == "," and count == 0:
            sub_expressions.append(expression[start:i].strip())
            start = i + 1
    sub_expressions.append(expression[start:].strip())
    return sub_expressions
	```