Parsing A Boolean Expression

Hard
1255.

Parsing A Boolean Expression

Parsing A Boolean Expression is a hard coding problem on strings, stack and recursion, asked in Amazon, Google and Microsoft interviews.

A CodeKairo feature flag is written as a boolean expression in a tiny prefix language. An expression is one of:

  • t — true;
  • f — false;
  • !(e) — the logical NOT of the inner expression e;
  • &(e1,e2,...,ek) — the logical AND of one or more inner expressions;
  • |(e1,e2,...,ek) — the logical OR of one or more inner expressions.

Given a valid expression, return what it evaluates to.

Example 1

Input
expression = "|(&(t,f,t),!(f))"
Output
true
Explanation
`&(t,f,t)` is false and `!(f)` is true, so the OR is true.

Example 2

Input
expression = "&(|(f,t),!(t))"
Output
false

Example 3

Input
expression = "|(f)"
Output
false

Constraints

  • 1 <= expression.length <= 2 * 10^4
  • expression[i] is one of '(', ')', '&', '|', '!', 't', 'f' and ','
  • expression is a valid expression as defined above
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} expression
 * @return {boolean}
 */
var parseBoolExpr = function(expression) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Parsing A Boolean Expression — Problem & Solution

Parsing A Boolean Expression solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Parsing A Boolean Expression is a hard coding problem on strings, stack and recursion, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Hard
  • Topics: Strings, Stack, Recursion
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A CodeKairo feature flag is written as a boolean expression in a tiny prefix language. An expression is one of:

  • t — true;
  • f — false;
  • !(e) — the logical NOT of the inner expression e;
  • &(e1,e2,...,ek) — the logical AND of one or more inner expressions;
  • |(e1,e2,...,ek) — the logical OR of one or more inner expressions.

Given a valid expression, return what it evaluates to.

Example 1

Input: expression = "|(&(t,f,t),!(f))"
Output: true
Explanation: `&(t,f,t)` is false and `!(f)` is true, so the OR is true.

Example 2

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

Example 3

Input: expression = "|(f)"
Output: false

Constraints

  • 1 <= expression.length <= 2 * 10^4
  • expression[i] is one of '(', ')', '&', '|', '!', 't', 'f' and ','
  • expression is a valid expression as defined above

Hints for Parsing A Boolean Expression

  1. Hint 1

    An operator's value is only known once its closing ) is reached — that suggests a stack.

  2. Hint 2

    Push every character except commas. On ), pop values until the matching (, counting how many were t and how many f.

  3. Hint 3

    Then pop the ( and the operator below it: ! gives true iff the single value was f, & gives true iff no f was seen, | gives true iff some t was seen. Push the result as t/f.

How to solve Parsing A Boolean Expression

Evaluate bottom-up with one stack: by the time a ) arrives, all of its operands have already been reduced to single t/f characters sitting above its (.

Approach

  1. Scan the expression; skip commas and push every other character except ).
  2. On ): pop characters until the top is (, counting the ts and fs popped.
  3. Pop the ( and then the operator.
  4. Compute the result — !: true iff the operand was f; &: true iff the f-count is 0; |: true iff the t-count is positive — and push it as t or f.
  5. When the scan ends, the stack holds one character; return whether it is t.

Why it works

Each ) closes the innermost open operator, and every operand of that operator is either a literal or an inner expression whose own ) came earlier and was already replaced by its value. So the popped run is exactly the operator's list of operand values. AND and OR only need to know whether a false or a true value is present, which the counts provide.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Forgetting to skip commas mixes them into the operand counts.
  • An operator can have a single operand (|(f), &(t)); the counting rule handles it without special cases.
  • A recursive parser works too, but a 2 * 10^4-character expression can nest deeply — the explicit stack avoids recursion limits.

Reference solution

Python

def parseBoolExpr(expression: str) -> bool:
    st = []
    for c in expression:
        if c == ",":
            continue
        if c != ")":
            st.append(c)
            continue
        t = f = 0
        while st[-1] != "(":
            if st.pop() == "t":
                t += 1
            else:
                f += 1
        st.pop()
        op = st.pop()
        if op == "!":
            r = f > 0
        elif op == "&":
            r = f == 0
        else:
            r = t > 0
        st.append("t" if r else "f")
    return st[-1] == "t"

Java

public static boolean parseBoolExpr(String expression) {
    char[] st = new char[expression.length() + 1];
    int top = 0;
    for (int i = 0; i < expression.length(); i++) {
        char c = expression.charAt(i);
        if (c == ',') continue;
        if (c != ')') {
            st[top++] = c;
            continue;
        }
        int t = 0, f = 0;
        while (st[top - 1] != '(') {
            if (st[--top] == 't') t++;
            else f++;
        }
        top--;
        char op = st[--top];
        boolean r = op == '!' ? f > 0 : op == '&' ? f == 0 : t > 0;
        st[top++] = r ? 't' : 'f';
    }
    return st[top - 1] == 't';
}

C++

bool parseBoolExpr(string expression) {
    vector<char> st;
    for (char c : expression) {
        if (c == ',') continue;
        if (c != ')') {
            st.push_back(c);
            continue;
        }
        int t = 0, f = 0;
        while (st.back() != '(') {
            if (st.back() == 't') t++;
            else f++;
            st.pop_back();
        }
        st.pop_back();
        char op = st.back();
        st.pop_back();
        bool r = op == '!' ? f > 0 : op == '&' ? f == 0 : t > 0;
        st.push_back(r ? 't' : 'f');
    }
    return st.back() == 't';
}

JavaScript

var parseBoolExpr = function(expression) {
    var st = [];
    for (var i = 0; i < expression.length; i++) {
        var c = expression[i];
        if (c === ",") continue;
        if (c !== ")") {
            st.push(c);
            continue;
        }
        var t = 0, f = 0;
        while (st[st.length - 1] !== "(") {
            if (st.pop() === "t") t++;
            else f++;
        }
        st.pop();
        var op = st.pop();
        var r = op === "!" ? f > 0 : op === "&" ? f === 0 : t > 0;
        st.push(r ? "t" : "f");
    }
    return st[st.length - 1] === "t";
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Stack Data Structure