Boolean String Value

Solution: Simple (No Precedence)

function evalBooleanSimple(expr) {
    // Remove spaces
    expr = expr.replace(/s+/g, '');

    // Convert to lowercase for easier parsing
    expr = expr.toLowerCase();

    // Split by operators (this is naive, doesn't handle precedence)
    const tokens = expr.split(/(and|or)/);

    let result = parseBool(tokens[0]);

    for (let i = 1; i < tokens.length; i += 2) {
        const operator = tokens[i];
        const operand = parseBool(tokens[i + 1]);

        if (operator === 'and') {
            result = result && operand;
        } else if (operator === 'or') {
            result = result || operand;
        }
    }

    return result;
}

function parseBool(str) {
    str = str.trim().toLowerCase();
    if (str === 'true' || str === '1') return true;
    if (str === 'false' || str === '0') return false;
    throw new Error(`Invalid boolean: ${str}`);
}

// Tests
console.log(evalBooleanSimple("true AND false"));       // false
console.log(evalBooleanSimple("true OR false"));        // true
console.log(evalBooleanSimple("true OR false AND false")); // false (left-to-right)

With Recursive Descent (Precedence + Parentheses)

class BooleanParser {
    constructor(expr) {
        this.expr = expr.replace(/s+/g, '').toLowerCase();
        this.pos = 0;
    }

    parse() {
        return this.parseOr();
    }

    parseOr() {
        let left = this.parseAnd();

        while (this.match('or')) {
            const right = this.parseAnd();
            left = left || right;
        }

        return left;
    }

    parseAnd() {
        let left = this.parseNot();

        while (this.match('and')) {
            const right = this.parseNot();
            left = left && right;
        }

        return left;
    }

    parseNot() {
        if (this.match('not')) {
            return !this.parsePrimary();
        }
        return this.parsePrimary();
    }

    parsePrimary() {
        // Handle parentheses
        if (this.match('(')) {
            const result = this.parseOr();
            if (!this.match(')')) {
                throw new Error('Missing closing parenthesis');
            }
            return result;
        }

        // Parse boolean literal
        if (this.match('true')) return true;
        if (this.match('false')) return false;

        throw new Error(`Unexpected token at position ${this.pos}`);
    }

    match(str) {
        if (this.expr.substr(this.pos, str.length) === str) {
            this.pos += str.length;
            return true;
        }
        return false;
    }
}

function evalBoolean(expr) {
    const parser = new BooleanParser(expr);
    return parser.parse();
}

// Tests
console.log(evalBoolean("true AND false"));              // false
console.log(evalBoolean("true OR false AND false"));     // true (AND first)
console.log(evalBoolean("(true OR false) AND false"));   // false
console.log(evalBoolean("NOT false"));                   // true
console.log(evalBoolean("NOT (true AND false)"));        // true
console.log(evalBoolean("true AND (false OR true)"));    // true

With Symbols (1/0)

function evalBooleanSymbols(expr) {
    // Convert symbols to words
    expr = expr
        .replace(/1/g, 'true')
        .replace(/0/g, 'false')
        .replace(/&&/g, 'AND')
        .replace(/||/g, 'OR')
        .replace(/!/g, 'NOT ');

    return evalBoolean(expr);
}

console.log(evalBooleanSymbols("1 && 0"));       // false
console.log(evalBooleanSymbols("1 || 0"));       // true
console.log(evalBooleanSymbols("!(1 && 0)"));    // true

Using eval() (Not Recommended)

function evalBooleanEval(expr) {
    // DANGEROUS: Don't use in production!
    // Only for comparison/demonstration

    expr = expr
        .replace(/bANDb/gi, '&&')
        .replace(/bORb/gi, '||')
        .replace(/bNOTb/gi, '!')
        .replace(/btrueb/gi, 'true')
        .replace(/bfalseb/gi, 'false');

    return eval(expr);
}

// Works but NEVER use in production
console.log(evalBooleanEval("true AND false"));  // false

Operator Precedence

Standard precedence (high to low):

1. Parentheses ()
2. NOT
3. AND
4. OR

Example: "true OR false AND false"

Without precedence (left-to-right):
  (true OR false) AND false
  = true AND false
  = false

With precedence (AND before OR):
  true OR (false AND false)
  = true OR false
  = true ✓ (correct)

Complexity

Simple evaluation: O(n) time, O(1) space
Recursive descent: O(n) time, O(d) space where d is max nesting depth
With tokenization: O(n) time, O(n) space for tokens

Common Mistakes

• Ignoring precedence: AND should evaluate before OR
• Not handling whitespace: "true AND false" vs "trueANDfalse"
• Case sensitivity: "TRUE" vs "true" - normalize first
• Invalid expressions: Need error handling for malformed input

Follow-Up Questions

Q: Support variables? e.g., "x AND y"
A: Pass variable map, look up values during parsing

Q: Support XOR operator?
A: Add to parser, XOR has same precedence as OR typically

Q: Generate truth table?
A: Enumerate all variable combinations, evaluate for each

Related Problems

• int atoi( char* pStr ) - String parsing
• Removing a Character from a String - String processing
• Print String Permutations - String algorithms