LeetCode Entry

1106. Parsing A Boolean Expression

20.10.2024 hard 2024 kotlin rust

before evaluation, index i should point at the first token of the subproblem

1106. Parsing A Boolean Expression hard blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/774

Problem TDLR

Parse boolean expression #hard #stack #recursion

Intuition

The key to solving eval problems is to correctly define a subproblem: each subproblem should not have braces around it and must be evaluated to the result before returning.

One way is the recursion, another is the stack and a Polish Notation (evaluate-after).

Approach

• before evaluation, index i should point at the first token of the subproblem
• after evaluation, index i should point after the last token of the subproblem
• ’,’-operation can be done in-place
• polish notation solution: evaluate on each close ‘)’ bracket, otherwise just push-push-push
• or-result is interested in any true token, and- result interested in any false token

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\) for the recursion depth or stack

Code

    fun parseBoolExpr(expression: String): Boolean {
        var i = 0
        fun e(): Boolean = when (expression[i]) {
            'f' -> false
            't' -> true
            '!' -> { i += 2; !e() }
            '&' -> { i += 2; var x = e()
                while (expression[i] == ',') { i++; x = x and e() }; x }
            else -> { i += 2; var x = e()
                while (expression[i] == ',') { i++; x = x or e() }; x }
        }.also { i++ }
        return e()
    }

    pub fn parse_bool_expr(expression: String) -> bool {
        let (mut st, mut tf) = (vec![], [b't', b'f']);
        for b in expression.bytes() { if b == b')' {
            let (mut t, mut f) = (0, 0);
            while let Some(&c) = st.last() {
                st.pop(); if c == b'(' { break }
                t |= (c == b't') as usize; f |= (c == b'f') as usize;
            }
            let op = st.pop().unwrap();
            st.push(tf[match op { b'!' => t, b'&' => f, _ => 1 - t }])
        } else if b != b',' { st.push(b); }}
        st[0] == b't'
    }

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