Parsing A Boolean Expression - Practice Coding Problems

Parsing A Boolean Expression - Problem

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
'&(subExpr₁, subExpr₂, ..., subExprₙ)' that evaluates to the logical AND of the inner expressions subExpr₁, subExpr₂, ..., subExprₙ where n ≥ 1
'|(subExpr₁, subExpr₂, ..., subExprₙ)' that evaluates to the logical OR of the inner expressions subExpr₁, subExpr₂, ..., subExprₙ 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.

Input & Output

Example 1 — OR Expression

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

› Output: true

💡 Note: OR operation with operands false and true: f | t = true

Example 2 — Nested AND with OR and NOT

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

› Output: false

💡 Note: First evaluate inner expressions: |(t,f,t) = true, !(t) = false. Then: &(true,false) = false

Example 3 — Complex Nesting

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

› Output: true

💡 Note: Inner expressions: !(f) = true, &(t,t,t) = true. Then: |(true,true) = true

Constraints

1 ≤ expression.length ≤ 2 * 10⁴
expression[i] is one of 't', 'f', '!', '&', '|', '(', ')', and ','
expression is a valid boolean expression

Visualization

Tap to expand

Understanding the Visualization

Input Structure

Nested boolean expression with operators and operands

Parse & Evaluate

Process operators with their operands systematically

Boolean Result

Final true/false evaluation

Key Takeaway

🎯 Key Insight: Parse nested boolean expressions by handling operators and their operands systematically, evaluating from innermost expressions outward

Asked in

f Facebook 12 G Google 8 a Amazon 6 M Microsoft 4

The key insight is to parse boolean expressions using proper nesting handling. The stack-based approach is most efficient, processing each character once and using the stack to manage nested operations naturally. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive with Memoization	O(n)	O(d)	Recursively parse sub-expressions with caching for optimization
Stack-Based Parsing	O(n)	O(n)	Use a stack to handle nested operations systematically
Character-by-Character Parsing	O(n²)	O(n)	Manually parse and evaluate each character while tracking nesting levels

Recursive with Memoization — Algorithm Steps

Identify base cases (t, f)
For operators, find and parse sub-expressions recursively
Cache results for potential reuse
Combine results based on operator logic

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse Structure

Identify operator and sub-expressions

Recursive Calls

Recursively evaluate each sub-expression

Cache & Combine

Cache results and combine with operator logic

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_MEMO 10000

struct MemoEntry {
    char expr[1000];
    bool result;
    bool valid;
} memo[MAX_MEMO];

int memoCount = 0;

bool findMemo(char* expr) {
    for (int i = 0; i < memoCount; i++) {
        if (strcmp(memo[i].expr, expr) == 0) {
            return memo[i].result;
        }
    }
    return false;
}

bool hasMemo(char* expr) {
    for (int i = 0; i < memoCount; i++) {
        if (strcmp(memo[i].expr, expr) == 0) {
            return true;
        }
    }
    return false;
}

void addMemo(char* expr, bool result) {
    if (memoCount < MAX_MEMO) {
        strcpy(memo[memoCount].expr, expr);
        memo[memoCount].result = result;
        memo[memoCount].valid = true;
        memoCount++;
    }
}

bool parse(char* expr) {
    if (hasMemo(expr)) {
        return findMemo(expr);
    }
    
    if (strcmp(expr, "t") == 0) return true;
    if (strcmp(expr, "f") == 0) return false;
    
    char op = expr[0];
    char subExprs[100][1000];
    int subCount = 0;
    
    int i = 2, depth = 0, start = 2;
    int len = strlen(expr);
    
    while (i < len - 1) {
        char c = expr[i];
        if (c == '!' || c == '&' || c == '|') {
            depth++;
        } else if (c == '(') {
            depth++;
        } else if (c == ')') {
            depth--;
        } else if (c == ',' && depth == 0) {
            strncpy(subExprs[subCount], expr + start, i - start);
            subExprs[subCount][i - start] = '\0';
            subCount++;
            start = i + 1;
        }
        i++;
    }
    
    if (start < len - 1) {
        strncpy(subExprs[subCount], expr + start, len - 1 - start);
        subExprs[subCount][len - 1 - start] = '\0';
        subCount++;
    }
    
    bool result;
    if (op == '!') {
        result = !parse(subExprs[0]);
    } else if (op == '&') {
        result = true;
        for (int j = 0; j < subCount; j++) {
            if (!parse(subExprs[j])) {
                result = false;
                break;
            }
        }
    } else {
        result = false;
        for (int j = 0; j < subCount; j++) {
            if (parse(subExprs[j])) {
                result = true;
                break;
            }
        }
    }
    
    addMemo(expr, result);
    return result;
}

bool solution(char* expression) {
    memoCount = 0;
    return parse(expression);
}

int main() {
    char expression[20000];
    fgets(expression, sizeof(expression), stdin);
    expression[strcspn(expression, "\n")] = 0;
    
    bool result = solution(expression);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each character is processed once during parsing, with constant time operations per character

✓ Linear Growth

Space Complexity

O(d)

Recursion depth d for nested expressions, plus space for memoization map (though rarely used)

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler