1106. Parsing A Boolean Expression

[mah-shamim]

Topics: String, Stack, Recursion

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 ','.

Hint:

1. Write a function "parse" which calls helper functions "parse_or", "parse_and", "parse_not".

[kovatz]

We will break down the solution into smaller functions that handle parsing and evaluating different types of expressions: parse_or, parse_and, parse_not, and a main parse function that handles the parsing of the expression recursively. We will use a stack to keep track of nested expressions and evaluate them step-by-step.

Approach:

1. Parsing and Recursion:

   • Use a stack to keep track of expressions when encountering nested parentheses.
   • Process characters sequentially and manage the stack for nested evaluations.
   • When encountering a closing parenthesis ), extract the last set of expressions and apply the logical operation (&, |, or !).

2. Helper Functions:

   • parse_or: Evaluates |(expr1, expr2, ..., exprN) by returning true if at least one sub-expression is true.
   • parse_and: Evaluates &(expr1, expr2, ..., exprN) by returning true only if all sub-expressions are true.
   • parse_not: Evaluates !(expr) by returning the opposite of the sub-expression.

3. Expression Handling:

   • Single characters like t and f directly translate to true and false.
   • When an operation is encountered (&, |, !), the inner expressions are evaluated based on their respective rules.

Let's implement this solution in PHP: 1106. Parsing A Boolean Expression

<?php
/**
 * @param String $expression
 * @return Boolean
 */
function parseBooleanExpression($expression) {
    $stack = [];
    
    for ($i = 0; $i < strlen($expression); $i++) {
        $char = $expression[$i];
        
        if ($char == ')') {
            // Process until we find a matching open parenthesis
            $subExpr = [];
            while ($stack && end($stack) != '(') {
                array_unshift($subExpr, array_pop($stack));
            }
            array_pop($stack); // Remove the '('

            // The operation comes before the '('
            $operation = array_pop($stack);

            // Evaluate the sub-expression
            if ($operation == '&') {
                $result = parse_and($subExpr);
            } elseif ($operation == '|') {
                $result = parse_or($subExpr);
            } elseif ($operation == '!') {
                $result = parse_not($subExpr);
            }
            
            // Push the result back to the stack as 't' or 'f'
            $stack[] = $result ? 't' : 'f';
        } elseif ($char != ',') {
            // Push characters except ',' into the stack
            $stack[] = $char;
        }
    }
    
    // The result should be the final element in the stack
    return $stack[0] == 't';
}

/**
 * the logical AND
 * 
 * @param $subExpr
 * @return bool
 */
function parse_and($subExpr) {
    foreach ($subExpr as $expr) {
        if ($expr == 'f') {
            return false;
        }
    }
    return true;
}

/**
 * the logical OR
 * 
 * @param $subExpr
 * @return bool
 */
function parse_or($subExpr) {
    foreach ($subExpr as $expr) {
        if ($expr == 't') {
            return true;
        }
    }
    return false;
}
/**
 * the logical NOT
 * 
 * @param $subExpr
 * @return bool
 */
function parse_not($subExpr) {
    // subExpr contains only one element for NOT operation
    return $subExpr[0] == 'f';
}

// Test cases
echo parseBooleanExpression("&(|(f))") ? "true" : "false"; // Output: false
echo "\n";
echo parseBooleanExpression("|(f,f,f,t)") ? "true" : "false"; // Output: true
echo "\n";
echo parseBooleanExpression("!(&(f,t))") ? "true" : "false"; // Output: true
?>

Explanation:

• Main Function (parseBooleanExpression):

  • Iterates through the expression and pushes characters to a stack.
  • When encountering a ), it collects all the elements inside the parentheses and evaluates them based on the operation (&, |, !).
  • Converts results to 't' (true) or 'f' (false) and pushes them back to the stack.

• Helper Functions:

  • parse_and: Returns true if all sub-expressions are 't' (true).
  • parse_or: Returns true if any sub-expression is 't'.
  • parse_not: Reverses the boolean value of a single sub-expression.

Example Walkthrough:

1. Input: "&(|(f))"

   • Stack processing:
     • &, (, |, (, f, ), ) → The inner expression |(f) is evaluated to f.
     • Resulting in &(f), which evaluates to f.
   • Output: false.

2. Input: "|(f,f,f,t)"

   • Evaluates the | operation:
     • Finds one 't', thus evaluates to true.
   • Output: true.

3. Input: "!(&(f,t))"

   • Stack processing:
     • !, (, &, (, f, ,, t, ), ) → &(f,t) evaluates to f.
     • !(f) is then evaluated to true.
   • Output: true.

Complexity:

• Time Complexity: O(N), where N is the length of the expression. Each character is processed a limited number of times.
• Space Complexity: O(N), due to the stack used to keep track of nested expressions.

This solution is well-suited for the constraints and should handle the input size effectively.

[mah-shamim]

Thanks to solve this problem

[kovatz]

Thanks