Vultr DocsLatest Content

Parsing A Boolean Expression

Updated on 09 July, 2025
Parsing A Boolean Expression header image

Problem Statement

Boolean expressions are fundamental in programming and logic, involving operations that result in boolean values: true or false. These expressions are structured and can take specific pre-defined forms:

  • A single character 't' representing a true value.
  • A single character 'f' representing a false value.
  • An expression prefixed by ! inside parentheses denoting the logical negation of the enclosed expression.
  • Multiple expressions enclosed within parentheses and prefixed by &, representing the logical AND of all enclosed expressions.
  • Multiple expressions inside parentheses, prefixed by |, indicating the logical OR of all enclosed expressions.

The task is to evaluate a given string expression that represents one such boolean expression. The output should be the result of the evaluated expression, allowing us to decipher complex logical conditions programmatically.

Examples

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

Approach and Intuition

The evaluation of the boolean expression from the input string must systematically simplify according to the operations:

  1. Identify the basic operations ('t', 'f', '!', '&', '|') and their scope.
  2. Begin by evaluating the innermost expression, working outwardly:
    • For !, convert the result of the inner expression to its logical opposite.
    • For &, check all inner expressions; if all are true, result in true; otherwise, false.
    • For |, any one true inner expression results in true; all false results in false.
  3. Utilize a stack or recursive method to handle nested expressions effectively, ensuring operations follow their precedence and associativity.

This approach systematically reduces the complexity of nested expressions, turning a potentially large and convoluted expression into simpler, manageable components until a single boolean value remains. By simplifying from inside out, the constructs like !, &, and | get effectively resolved by paying attention to their operational characteristics.

Solutions

  • C++
cpp 
class Solution {
public:
    bool evaluateBooleanExpression(string expr) {
        stack<char> s;
    
        for (char ch : expr) {
            if (ch == ',' || ch == '(')
                continue;
    
            if (ch == 't' || ch == 'f' || ch == '!' || ch == '&' || ch == '|') {
                s.push(ch);
            } else if (ch == ')') {
                bool foundTrue = false, foundFalse = false;
                while (s.top() != '!' && s.top() != '&' && s.top() != '|') {
                    char topChar = s.top();
                    s.pop();
                    if (topChar == 't') foundTrue = true;
                    if (topChar == 'f') foundFalse = true;
                }
    
                char operatorChar = s.top();
                s.pop();
                if (operatorChar == '!') {
                    s.push(foundTrue ? 'f' : 't');
                } else if (operatorChar == '&') {
                    s.push(foundFalse ? 'f' : 't');
                } else {
                    s.push(foundTrue ? 't' : 'f');
                }
            }
        }
    
        return s.top() == 't';
    }
};

The C++ program provided involves a method to evaluate a complex boolean expression using a stack data structure. This method processes each character of the input string representing the expression:

  • It skips commas and open parentheses to focus on relevant characters that affect the boolean logic (i.e., truth values and boolean operators).
  • The stack collects characters representing boolean values (t for true, f for false) and operators (! for NOT, & for AND, | for OR).
  • When encountering a closing parenthesis, it resolves the immediate expression within the innermost preceding open parenthesis:
    • It evaluates this sub-expression based on the boolean operator it finds, considering both unary (!) and binary (&, |) operators.
  • Finally, by iterating through all characters and reducing expressions step by step, the method concludes with the top of the stack containing the result of the entire expression (t for true, f for false).

This approach efficiently evaluates the truth of nested boolean expressions, allowing logical constructions of considerable complexity.

Key points to manage and modify the code include:

  • Ensure proper initialization of boolean flags and careful handling of the stack to account for multiple nested expressions.
  • Modification of the approach to handle different forms of boolean logic if the input specification changes.
  • Optimize for performance based on the expected size and complexity of expressions.
  • Java
java 
public class Solution {
    
    public boolean evaluateExpression(String expr) {
        Stack<Character> stack = new Stack<>();
    
        // Loop through each character in the expression
        for (char character : expr.toCharArray()) {
            if (character == ',' || character == '(') continue; // Skip non-essential characters
    
            // Capture relevant characters in the stack
            if (character == 't' || character == 'f' || character == '!' || character == '&' || character == '|') {
                stack.push(character);
            } 
            // Evaluate expressions within closed brackets
            else if (character == ')') {
                boolean foundTrue = false, foundFalse = false;
    
                // Pull values from the stack until an operator is reached
                while (stack.peek() != '!' && stack.peek() != '&' && stack.peek() != '|') {
                    char topChar = stack.pop();
                    if (topChar == 't') foundTrue = true;
                    if (topChar == 'f') foundFalse = true;
                }
    
                // Operate based on the encountered operator
                char operator = stack.pop();
                if (operator == '!') {
                    stack.push(foundTrue ? 'f' : 't');
                } else if (operator == '&') {
                    stack.push(foundFalse ? 'f' : 't');
                } else {
                    stack.push(foundTrue ? 't' : 'f');
                }
            }
        }
    
        // The final result is the last item in the stack
        return stack.peek() == 't';
    }
}

In this Java solution to parsing a boolean expression, the evaluateExpression method utilizes a Stack to manage and compute the logic based on the characters of a given expression string, expr.

  • Begin by creating a Stack of Character type.
  • Iterate through each character in expr.
    • Ignore characters like ',' and '(' since they don't directly impact the outcome.
    • Push relevant tokens (t, f, !, &, |) onto the stack.
    • When a ')' is encountered:
      • Pop characters from the stack until an operator !, &, or | is found, keeping track of any t or f encountered.
      • Depending on the operator:
        • For !, push f if a t was found, otherwise push t.
        • For &, push f if a f was found, otherwise push t.
        • For |, push t if a t was found, otherwise push f.
  • After processing the entire string, the final result is determined by the last character left in the stack, which indicates true if it's t.

This method effectively handles the parsing and logical computation of nested and complex boolean expressions using standard stack operations to manage intermediate values and results.

  • Python
python 
class Solution:
    def evaluateExpression(self, expr: str) -> bool:
        stack = deque()
    
        for element in expr:
            if element == "," or element == "(":
                continue
                
            # Push characters to the stack
            if element in ["t", "f", "!", "&", "|"]:
                stack.append(element)
                
            # Handling the closing bracket
            elif element == ")":
                res_true = False
                res_false = False
    
                # Resolving until an operator is found
                while stack[-1] not in ["!", "&", "|"]:
                    value = stack.pop()
                    if value == "t":
                        res_true = True
                    elif value == "f":
                        res_false = True
    
                # Evaluating based on the operator
                operator = stack.pop()
                if operator == "!":
                    stack.append("t" if not res_true else "f")
                elif operator == "&":
                    stack.append("f" if res_false else "t")
                else:
                    stack.append("t" if res_true else "f")
    
        return stack[-1] == "t"

The solution for parsing a boolean expression in Python involves using a stack to efficiently manage and evaluate the operators and operands in the given expression string. Follow this approach to correctly implement the evaluateExpression method:

  1. Initialize a stack to help with operations.
  2. Iterate through each character of the expression.
  3. Skip the character if it's either a comma or an opening parenthesis, as these don't directly affect the outcome.
  4. Add any character that is 't', 'f', '!', '&', or '|' directly to the stack.
  5. If a closing parenthesis ')' is encountered:
    • Continue to resolve the expression until hitting an operator ('!', '&', '|').
    • Pop elements from the stack and evaluate them according to the truths ('t') and falsehoods ('f') encountered.
    • With the final operator determined, evaluate it:
      • For '!', push 't' if false, otherwise 'f'.
      • For '&', push 'f' if any 'f' was encountered, otherwise 't'.
      • For '|', push 't' if any 't' was found, otherwise 'f'.
  6. Once the full expression is processed, the remaining element in the stack represents the result. Check if it's 't' to return true, otherwise return false.

This method effectively uses the stack to handle various operations and conditions, making sure the boolean logic is precisely evaluated based on the sequence of operators and values in the expression.

Comments

No comments yet.