• Posts

Problem 1106 Parsing A Boolean Expression

Problem Statement

Link - Problem 1106

Question

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

Solution

class Solution {
public:
    static bool parseBoolExpr(string& expr) {
        vector<char> stack;
        stack.reserve(expr.size());
        for (char c : expr) {
            switch (c) {
            case ',': break;
            case ')': {
                char s;
                vector<char> x;
                char t = stack.back();
                x.push_back(t);
                stack.pop_back();
                while (t != '(') {
                        x.push_back(t);
                        t = stack.back();
                        stack.pop_back();
                }
                char op = stack.back();
                stack.pop_back();
                switch (op) {
                case '!':
                    s = (x[0] == 'f') ? 't' : 'f';
                    break;
                case '&':
                    s = all_of(x.begin(), x.end(),[](char b) { return b == 't'; })? 't': 'f';
                    break;
                case '|':
                    s = any_of(x.begin(), x.end(),[](char b) { return b == 't'; })? 't': 'f';
                    break;
                }
                stack.push_back(s);
                break;
            }
            default:
                stack.push_back(c);
            }
        }
        return stack.back() == 't';
    }
};

Complexity Analysis

| Algorithm                         | Time Complexity | Space Complexity |
| --------------------------------- | --------------- | ---------------- |
| Stack-based Expression Evaluation | O(n)            | O(n)             |

Explanation

Intial Thoughts

To solve this problem, we should start by breaking down the boolean expression into its simplest components. This involves identifying the logical operators such as NOT, AND, and OR, and the boolean values true and false. We should think about how these operators interact with each other, like how NOT flips the value, AND requires all to be true, and OR requires at least one to be true. We should also consider how to handle nested expressions, thinking of them like layers of an onion that we peel back one at a time. A stack data structure could be useful here because we can push and pop elements as we encounter opening and closing parentheses, allowing us to process the expression from the innermost outwards.

Intuitive Analysis

Intuitively, we can think of solving this problem as if we’re following a recipe. First, we identify the ingredients, which are the boolean values and the operators. Then, we follow the order of operations, similar to how we follow steps in a recipe. We start with the innermost parentheses and work our way outwards, applying the operators as we go. The stack helps us keep track of where we are in the recipe, allowing us to temporarily set aside parts of the expression and come back to them later. We can also think of each operator as a filter that changes the boolean values as it encounters them. By thinking about the problem in this step-by-step, methodical way, we can break down even the most complex boolean expressions into manageable parts.

1. Intuition

• The problem requires evaluating a boolean expression with specific rules, so we need to break down the expression into smaller sub-expressions and evaluate them recursively.
• We can use a stack-based approach to parse the expression and evaluate the sub-expressions.
• The key insight is to identify the operator and the corresponding operands, and then apply the operator to the operands.
• We need to handle the !, &, and | operators separately, as they have different evaluation rules.
• The ! operator simply flips the boolean value of the operand, while the & and | operators require evaluating all the operands and then applying the operator.
• The solution works by iterating through the expression, pushing operands and operators onto the stack, and then popping them off when a ) is encountered to evaluate the sub-expression.
• The final result is the evaluation of the entire expression, which is the last element left on the stack.

2. Implementation

• We use a vector<char> as a stack to store the operands and operators, with stack.reserve(expr.size()) to pre-allocate memory for efficiency.
• The switch statement is used to handle different characters in the expression, with case ',' being a no-op as commas are ignored.
• When a ) is encountered, we pop the operands and operator off the stack, evaluate the sub-expression using switch (op) to handle the different operators, and then push the result back onto the stack.
• The all_of and any_of functions are used to evaluate the & and | operators, respectively, by checking if all or any of the operands are t.
• The ! operator is evaluated by simply flipping the boolean value of the operand using a ternary expression.
• The final result is returned as a boolean value by comparing the last element on the stack to 't' using return stack.back() == 't';
• The use of stack.back() and stack.pop_back() allows for efficient evaluation of the sub-expressions and avoids unnecessary memory allocations.

Complexity Analysis

Time Complexity:

• The algorithm iterates over the input string expr once, resulting in a linear time complexity. Each character in expr is processed in constant time, with the switch statement and stack operations (push_back, pop_back) taking O(1) time.
• The while loop inside the switch statement for the ')' case may seem like it could increase the time complexity, but it only runs until the matching '(' is found, and each character is only processed once. The use of all_of and any_of in the case '&' and case '|' blocks also take O(n) time in the worst case, where n is the number of elements in the x vector.
• Therefore, the overall time complexity is O(n), where n is the length of the input string expr. This is because the algorithm performs a constant amount of work for each character in the input string, resulting in a linear time complexity.

Space Complexity:

• The space complexity is dominated by the stack vector, which stores characters from the input string expr. In the worst case, the stack can grow up to the size of the input string, resulting in a space complexity of O(n).
• The x vector used to store the operands for the logical operators also contributes to the space complexity, but its size is bounded by the number of operands, which is at most the size of the input string.
• Therefore, the overall space complexity is O(n), where n is the length of the input string expr. This is because the algorithm uses a data structure (the stack vector) that grows linearly with the size of the input string.

Footnote

This question is rated as Hard difficulty.

Hints

Write a function “parse” which calls helper functions “parse_or”, “parse_and”, “parse_not”.