DEV Community

Cover image for 1106. Parsing A Boolean Expression
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

1106. Parsing A Boolean Expression

1106. Parsing A Boolean Expression

Difficulty: Hard

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".

Solution:

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) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * the logical AND
 * 
 * @param $subExpr
 * @return bool
 */
function parse_and($subExpr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * the logical OR
 * 
 * @param $subExpr
 * @return bool
 */
function parse_or($subExpr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
/**
 * the logical NOT
 * 
 * @param $subExpr
 * @return bool
 */
function parse_not($subExpr) {
    // subExpr contains only one element for NOT operation
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// 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
?>
Enter fullscreen mode Exit fullscreen mode

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.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Speedy emails, satisfied customers

Postmark Image

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay