Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Evaluate Boolean Expression

HARDProblemSolveExternal Links

Description

A boolean expression is a string that evaluates to either true or false. The expression uses the following grammar:

  • 't' — evaluates to true.
  • 'f' — evaluates to false.
  • '!(subExpr)' — evaluates to the logical NOT of the inner expression subExpr.
  • '&(subExpr₁, subExpr₂, ..., subExprₙ)' — evaluates to the logical AND of n inner expressions (where n ≥ 1).
  • '|(subExpr₁, subExpr₂, ..., subExprₙ)' — evaluates to the logical OR of n inner expressions (where n ≥ 1).

Given a string expression that represents a boolean expression, return the evaluation of that expression.

The expression is guaranteed to be valid. The challenge is to correctly parse the nested, recursive structure and evaluate each sub-expression according to its operator.

Note that:

  • NOT (!) flips the boolean value — true becomes false, false becomes true.
  • AND (&) returns true only if all sub-expressions are true.
  • OR (|) returns true if at least one sub-expression is true.

Examples

Example 1

Input: expression = "&(|(f))"

Output: false

Explanation:

  • First, evaluate the innermost expression: |(f) → false (OR of a single false is false).
  • The expression simplifies to &(f).
  • Evaluate &(f) → false (AND of a single false is false).
  • Return false.

Example 2

Input: expression = "|(f,f,f,t)"

Output: true

Explanation:

  • Evaluate |(f, f, f, t) → true.
  • OR returns true because at least one sub-expression is true (t).

Example 3

Input: expression = "!(&(f,t))"

Output: true

Explanation:

  • First, evaluate &(f, t) → false (AND of false and true is false).
  • The expression becomes !(f).
  • Evaluate !(f) → true (NOT of false is true).
  • Return true.

Constraints

  • 1 ≤ expression.length ≤ 2 × 10^4
  • expression[i] is one of: '(', ')', '&', '|', '!', 't', 'f', ','.
  • The expression is guaranteed to be valid and follows the given rules.

Editorial

Brute Force

Intuition

The expression has a naturally recursive structure — operators contain sub-expressions which may themselves contain operators. The most intuitive approach is to parse it exactly as its grammar defines it: recursive descent parsing.

Think of reading the expression like reading a sentence. When you encounter an operator like &, you know it will be followed by (, then a comma-separated list of sub-expressions, then ). Each sub-expression could itself be t, f, or another operator with its own sub-expressions.

We maintain a pointer pos into the string and advance it as we read characters. The key insight is that the current character tells us exactly what to do:

  • If it's t or f, we have a literal boolean value — return it.
  • If it's !, &, or |, we have an operator — consume (, recursively parse each sub-expression separated by ,, consume ), then apply the operator.

This naturally handles arbitrary nesting because each recursive call handles one level of the expression, and we always parse inner expressions before combining them with the outer operator.

While this approach is correct and efficient at O(n), it relies on the function call stack for its recursion. For deeply nested expressions like !(!(!(!(...)))), the recursion depth could approach n/4, which may cause stack overflow in constrained environments.

Step-by-Step Explanation

Let's trace through expression = "!(&(f,t))" using recursive descent.

Step 1: pos = 0, char = '!'. This is a NOT operator. Advance pos to 1.

Step 2: pos = 1, char = '('. Consume the opening parenthesis. Advance pos to 2.

Step 3: Recursively parse the sub-expression. pos = 2, char = '&'. This is an AND operator. Advance pos to 3.

Step 4: pos = 3, char = '('. Consume opening parenthesis. Advance pos to 4. Start collecting sub-expressions for AND.

Step 5: Recursively parse first sub-expression. pos = 4, char = 'f'. It's a literal false. Advance pos to 5. Return false.

Step 6: pos = 5, char = ','. Comma separator — more sub-expressions to come. Advance pos to 6.

Step 7: Recursively parse second sub-expression. pos = 6, char = 't'. It's a literal true. Advance pos to 7. Return true.

Step 8: pos = 7, char = ')'. Closing parenthesis — end of AND's sub-expressions. Advance pos to 8. We collected [false, true].

Step 9: Apply AND operator: false AND true = false. Return false to the NOT operator's context.

Step 10: pos = 8, char = ')'. Closing parenthesis — end of NOT's sub-expression. Advance pos to 9. NOT received [false].

Step 11: Apply NOT operator: NOT false = true. Return true.

Step 12: pos = 9, end of string. Final answer: true. ✓

Algorithm

  1. Maintain a pointer pos initialized to 0.
  2. Define parseExpr():
    • If expression[pos] is 't': advance pos, return true.
    • If expression[pos] is 'f': advance pos, return false.
    • If expression[pos] is '!', '&', or '|':
      a. Record the operator, advance pos.
      b. Advance past '('.
      c. Parse sub-expressions: call parseExpr() repeatedly, separated by ','.
      d. Advance past ')'.
      e. Apply the operator to the collected results:
      • !: return NOT result[0]
      • &: return true if ALL are true, else false
      • |: return true if ANY is true, else false
  3. Return parseExpr().

Code

class Solution {
public:
    bool parseBoolExpr(string expression) {
        int pos = 0;
        return parseExpr(expression, pos);
    }

private:
    bool parseExpr(const string& s, int& pos) {
        char c = s[pos];
        if (c == 't') { pos++; return true; }
        if (c == 'f') { pos++; return false; }

        char op = c;
        pos++; // skip operator
        pos++; // skip '('

        vector<bool> values;
        values.push_back(parseExpr(s, pos));
        while (s[pos] == ',') {
            pos++; // skip ','
            values.push_back(parseExpr(s, pos));
        }
        pos++; // skip ')'

        if (op == '!') return !values[0];
        if (op == '&') {
            for (bool v : values) if (!v) return false;
            return true;
        }
        // op == '|'
        for (bool v : values) if (v) return true;
        return false;
    }
};
class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        self.pos = 0
        self.s = expression
        return self._parse()

    def _parse(self) -> bool:
        c = self.s[self.pos]
        if c == 't':
            self.pos += 1
            return True
        if c == 'f':
            self.pos += 1
            return False

        op = c
        self.pos += 1  # skip operator
        self.pos += 1  # skip '('

        values = [self._parse()]
        while self.s[self.pos] == ',':
            self.pos += 1  # skip ','
            values.append(self._parse())
        self.pos += 1  # skip ')'

        if op == '!':
            return not values[0]
        if op == '&':
            return all(values)
        return any(values)  # op == '|'
class Solution {
    private int pos;
    private String s;

    public boolean parseBoolExpr(String expression) {
        this.s = expression;
        this.pos = 0;
        return parseExpr();
    }

    private boolean parseExpr() {
        char c = s.charAt(pos);
        if (c == 't') { pos++; return true; }
        if (c == 'f') { pos++; return false; }

        char op = c;
        pos++; // skip operator
        pos++; // skip '('

        List<Boolean> values = new ArrayList<>();
        values.add(parseExpr());
        while (s.charAt(pos) == ',') {
            pos++; // skip ','
            values.add(parseExpr());
        }
        pos++; // skip ')'

        if (op == '!') return !values.get(0);
        if (op == '&') {
            for (boolean v : values) if (!v) return false;
            return true;
        }
        // op == '|'
        for (boolean v : values) if (v) return true;
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n)

Where n is the length of the expression string. Each character is visited exactly once as the pointer pos monotonically advances from 0 to n-1. At each position, we do O(1) work (read character, compare, advance pointer).

Space Complexity: O(n)

The recursion depth is proportional to the nesting depth of the expression. In the worst case (e.g., !(!(!(!(...))))) this could be O(n/4) ≈ O(n). Additionally, each recursive call may store a values list, but the total number of elements across all lists is bounded by the number of t/f characters in the string, which is O(n).

Why This Approach Is Not Efficient

While the recursive descent parser runs in optimal O(n) time, it has practical drawbacks:

  1. Recursion overhead: Each nesting level adds a frame to the function call stack. For expressions with deep nesting (up to ~5000 levels with n = 2×10⁴), this consumes significant stack memory and may cause a stack overflow in languages with limited default stack sizes.

  2. Intermediate list allocation: The values list collects all parsed sub-expression results before applying the operator. For &(expr1, expr2, ..., exprN) with many operands, we allocate a list of size N even though we could short-circuit (AND can stop at the first false, OR at the first true).

  3. State management complexity: The shared mutable pos pointer requires careful management — passing by reference in C++, using instance variables in Python/Java. This makes the code harder to reason about.

An iterative stack-based approach eliminates recursion entirely, avoids stack overflow risks, and can be more cache-friendly by processing the string in a simple left-to-right scan.

Optimal Approach - Stack-Based Evaluation

Intuition

Instead of recursion, we can use an explicit stack to simulate the evaluation process. The key insight is beautifully simple:

  1. Push meaningful characters (t, f, !, &, |) onto the stack.
  2. Skip noise (( and , carry no semantic meaning).
  3. Evaluate on ) — when we hit a closing parenthesis, it means a complete sub-expression just ended. Pop all the boolean values, pop the operator, compute the result, and push it back.

Why does this work? Because the expression is well-formed: every ) corresponds to exactly one operator, and the boolean values between that operator and the ) are exactly that operator's operands.

Rather than storing the actual boolean values, we use a clever counting trick: count how many ts and fs we pop. Then:

  • NOT: If there were any fs → result is t (there's exactly one operand for NOT).
  • AND: If there were any fs → result is f (one false makes AND false).
  • OR: If there were any ts → result is t (one true makes OR true).

This avoids allocating lists entirely. After processing the entire string, exactly one value remains on the stack — our answer.

Step-by-Step Explanation

Let's trace expression = "!(&(f,t))" using the stack approach.

Step 1: Read '!'. It's an operator — push it. Stack: ['!'].

Step 2: Read '('. Skip it. Stack unchanged: ['!'].

Step 3: Read '&'. It's an operator — push it. Stack: ['!', '&'].

Step 4: Read '('. Skip it. Stack unchanged: ['!', '&'].

Step 5: Read 'f'. It's a boolean value — push it. Stack: ['!', '&', 'f'].

Step 6: Read ','. Skip it. Stack unchanged: ['!', '&', 'f'].

Step 7: Read 't'. It's a boolean value — push it. Stack: ['!', '&', 'f', 't'].

Step 8: Read ')'. Time to evaluate! Pop boolean values: pop 't' (trueCount=1), pop 'f' (falseCount=1). Pop operator '&'. AND: falseCount > 0 → result is 'f'. Push 'f'. Stack: ['!', 'f'].

Step 9: Read ')'. Time to evaluate again! Pop boolean values: pop 'f' (falseCount=1). Pop operator '!'. NOT: falseCount > 0 → result is 't'. Push 't'. Stack: ['t'].

Step 10: End of string. Stack has ['t']. Return true. ✓

Stack-Based Evaluation of !(&(f,t)) — Watch how each character is processed left to right. Operators and values get pushed; commas and opening parentheses are skipped; closing parentheses trigger evaluation of the top sub-expression.

Let's also trace a more complex expression to see how the stack handles multiple nesting levels.

Expression: "|(f,&(t,f))"

StepCharActionStack After
1|Push operator['|']
2(Skip['|']
3fPush value['|', 'f']
4,Skip['|', 'f']
5&Push operator['|', 'f', '&']
6(Skip['|', 'f', '&']
7tPush value['|', 'f', '&', 't']
8,Skip['|', 'f', '&', 't']
9fPush value['|', 'f', '&', 't', 'f']
10)Eval: pop t,f → &: f>0 → 'f'['|', 'f', 'f']
11)Eval: pop f,f → |: t=0 → 'f'['f']

Result: false. OR of (false, AND(true, false)) = OR(false, false) = false. ✓

Algorithm

  1. Initialize an empty stack.
  2. Iterate through each character c in the expression:
    • If c is 't', 'f', '!', '&', or '|': push it onto the stack.
    • If c is '(' or ',': skip it (no semantic value).
    • If c is ')': evaluate the sub-expression:
      a. Initialize trueCount = 0, falseCount = 0.
      b. While the stack top is 't' or 'f':
      • Pop it. Increment trueCount or falseCount accordingly.
        c. Pop the operator ('!', '&', or '|').
        d. Compute the result:
      • '!': result = 't' if falseCount > 0 else 'f'
      • '&': result = 'f' if falseCount > 0 else 't'
      • '|': result = 't' if trueCount > 0 else 'f'
        e. Push the result back onto the stack.
  3. Return true if stack[0] == 't', else false.

Code

class Solution {
public:
    bool parseBoolExpr(string expression) {
        stack<char> stk;

        for (char c : expression) {
            if (c == 't' || c == 'f' || c == '!' || c == '&' || c == '|') {
                stk.push(c);
            } else if (c == ')') {
                int trueCount = 0, falseCount = 0;
                while (stk.top() == 't' || stk.top() == 'f') {
                    if (stk.top() == 't') trueCount++;
                    else falseCount++;
                    stk.pop();
                }
                char op = stk.top();
                stk.pop();

                char result;
                if (op == '!') result = falseCount > 0 ? 't' : 'f';
                else if (op == '&') result = falseCount > 0 ? 'f' : 't';
                else result = trueCount > 0 ? 't' : 'f'; // '|'

                stk.push(result);
            }
            // skip '(' and ','
        }

        return stk.top() == 't';
    }
};
class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        stack = []

        for c in expression:
            if c in 'tf!&|':
                stack.append(c)
            elif c == ')':
                true_count = 0
                false_count = 0
                while stack[-1] in 'tf':
                    if stack[-1] == 't':
                        true_count += 1
                    else:
                        false_count += 1
                    stack.pop()

                op = stack.pop()

                if op == '!':
                    result = 't' if false_count > 0 else 'f'
                elif op == '&':
                    result = 'f' if false_count > 0 else 't'
                else:  # '|'
                    result = 't' if true_count > 0 else 'f'

                stack.append(result)
            # skip '(' and ','

        return stack[0] == 't'
class Solution {
    public boolean parseBoolExpr(String expression) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : expression.toCharArray()) {
            if (c == 't' || c == 'f' || c == '!' || c == '&' || c == '|') {
                stack.push(c);
            } else if (c == ')') {
                int trueCount = 0, falseCount = 0;
                while (stack.peek() == 't' || stack.peek() == 'f') {
                    if (stack.pop() == 't') trueCount++;
                    else falseCount++;
                }
                char op = stack.pop();

                char result;
                if (op == '!') result = falseCount > 0 ? 't' : 'f';
                else if (op == '&') result = falseCount > 0 ? 'f' : 't';
                else result = trueCount > 0 ? 't' : 'f';

                stack.push(result);
            }
            // skip '(' and ','
        }

        return stack.peek() == 't';
    }
}

Complexity Analysis

Time Complexity: O(n)

Where n is the length of the expression. We iterate through each character exactly once. Each character is pushed onto and popped from the stack at most once. The total push + pop operations across the entire algorithm is bounded by 2n, so the amortized cost per character is O(1).

Space Complexity: O(n)

The stack stores at most all the operators and boolean values before any closing parenthesis triggers evaluation. In the worst case (e.g., a flat expression like &(t,t,t,...,t) with n/2 operands), the stack size is O(n). However, this is an explicit stack on the heap — no recursion, no risk of call-stack overflow.

This is the optimal approach because:

  • O(n) time — we must read every character at least once, so this is tight.
  • O(n) space — we need to store intermediate values during evaluation; a stack-based approach can't avoid this.
  • No recursion — purely iterative, no stack overflow risk.
  • Cache-friendly — simple left-to-right scan with stack operations.