Formatted question description: https://leetcode.ca/all/1106.html

1106. Parsing A Boolean Expression (Hard)

Return the result of evaluating a given boolean expression, represented as a string.

An expression can either be:

"t", evaluating to True;
"f", evaluating to False;
"!(expr)", evaluating to the logical NOT of the inner expression expr;
"&(expr1,expr2,...)", evaluating to the logical AND of 2 or more inner expressions expr1, expr2, ...;
"|(expr1,expr2,...)", evaluating to the logical OR of 2 or more inner expressions expr1, expr2, ...

Example 1:

Input: expression = "!(f)"
Output: true

Example 2:

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

Example 3:

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

Example 4:

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

Constraints:

1 <= expression.length <= 20000
expression[i] consists of characters in {'(', ')', '&', '|', '!', 't', 'f', ','}.
expression is a valid expression representing a boolean, as given in the description.

Related Topics:
String

Solution 1.

// OJ: https://leetcode.com/problems/parsing-a-boolean-expression/
// Time: O(N)
// Space: O(H) where H is the maximum depth of the expression
class Solution {
    int i = 0;
    bool dfs(string &s) {
        if (s[i] == 't' || s[i] == 'f') return s[i++] == 't';
        char op = s[i++];
        ++i; // (
        bool ans;
        if (op == '!') ans = !dfs(s);
        else {
            ans = op == '&';
            while (s[i] != ')') {
                if (s[i] == ',') ++i;
                if (op == '&') ans = dfs(s) && ans;
                else ans = dfs(s) || ans;
            }
        }
        ++i; // )
        return ans;
    }
public:
    bool parseBoolExpr(string s) {
        return dfs(s);
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/parsing-a-boolean-expression/
// Time: O(N)
// Space: O(H) where H is the maximum depth of the expression
class Solution {
public:
    bool parseBoolExpr(string s) {
        stack<char> op;
        stack<bool> ans;
        int i = 0, N = s.size();
        while (i < N) {
            if (s[i] == 't' || s[i] == 'f') ans.push(s[i++] == 't');
            else if (s[i] == '!' || s[i] == '&' || s[i] == '|') {
                op.push(s[i]);
                if (s[i] != '!') ans.push(op.top() == '&');
                i += 2;
            } else if (s[i] == ',' || s[i] == ')') {
                if (op.top() == '&' || op.top() == '|') {
                    bool val = ans.top();
                    ans.pop();
                    if (op.top() == '&') ans.top() = ans.top() && val;
                    else ans.top() = ans.top() || val;
                } else ans.top() = !ans.top();
                if (s[i] == ')') op.pop();
                ++i;
            }
        }
        return ans.top();
    }
};

class Solution {
    public boolean parseBoolExpr(String expression) {
        Stack<Character> stack = new Stack<Character>();
        int length = expression.length();
        for (int i = 0; i < length; i++) {
            char c = expression.charAt(i);
            if (c == ',')
                continue;
            else if (c == ')') {
                int tCount = 0, fCount = 0;
                while (stack.peek() != '(') {
                    char prevC = stack.pop();
                    if (prevC == 't')
                        tCount++;
                    else if (prevC == 'f')
                        fCount++;
                }
                stack.pop();
                char operator = stack.pop();
                if (operator == '!') {
                    if (tCount == 1)
                        stack.push('f');
                    else
                        stack.push('t');
                } else if (operator == '&') {
                    if (fCount == 0)
                        stack.push('t');
                    else
                        stack.push('f');
                } else if (operator == '|') {
                    if (tCount == 0)
                        stack.push('f');
                    else
                        stack.push('t');
                }
            } else
                stack.push(c);
        }
        return stack.pop() == 't' ? true : false;
    }
}

############

class Solution {
    public boolean parseBoolExpr(String expression) {
        Deque<Character> stk = new ArrayDeque<>();
        for (char c : expression.toCharArray()) {
            if (c != '(' && c != ')' && c != ',') {
                stk.push(c);
            } else if (c == ')') {
                int t = 0, f = 0;
                while (stk.peek() == 't' || stk.peek() == 'f') {
                    t += stk.peek() == 't' ? 1 : 0;
                    f += stk.peek() == 'f' ? 1 : 0;
                    stk.pop();
                }
                char op = stk.pop();
                c = 'f';
                if ((op == '!' && f > 0) || (op == '&' && f == 0) || (op == '|' && t > 0)) {
                    c = 't';
                }
                stk.push(c);
            }
        }
        return stk.peek() == 't';
    }
}

// OJ: https://leetcode.com/problems/parsing-a-boolean-expression/
// Time: O(N)
// Space: O(H) where H is the maximum depth of the expression
class Solution {
    int i = 0;
    bool dfs(string &s) {
        if (s[i] == 't' || s[i] == 'f') return s[i++] == 't';
        char op = s[i++];
        ++i; // (
        bool ans;
        if (op == '!') ans = !dfs(s);
        else {
            ans = op == '&';
            while (s[i] != ')') {
                if (s[i] == ',') ++i;
                if (op == '&') ans = dfs(s) && ans;
                else ans = dfs(s) || ans;
            }
        }
        ++i; // )
        return ans;
    }
public:
    bool parseBoolExpr(string s) {
        return dfs(s);
    }
};

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        stk = []
        for c in expression:
            if c in 'tf!&|':
                stk.append(c)
            elif c == ')':
                t = f = 0
                while stk[-1] in 'tf':
                    t += stk[-1] == 't'
                    f += stk[-1] == 'f'
                    stk.pop()
                match stk.pop():
                    case '!':
                        c = 't' if f else 'f'
                    case '&':
                        c = 'f' if f else 't'
                    case '|':
                        c = 't' if t else 'f'
                stk.append(c)
        return stk[0] == 't'

############

# 1106. Parsing A Boolean Expression
# https://leetcode.com/problems/parsing-a-boolean-expression/

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        stack = []
        
        for c in expression:
            if c == ")":
                seen = set()
                while stack and stack[-1] != "(":
                    seen.add(stack.pop())
                stack.pop()
                operator = stack.pop()
                stack.append(all(seen) if operator == "&" else any(seen) if operator == "|" else not seen.pop())
            elif c != ",":
                stack.append(True if c == 't' else False if c == 'f' else c)
        
        return stack.pop()

func parseBoolExpr(expression string) bool {
	stk := []rune{}
	for _, c := range expression {
		if c != '(' && c != ')' && c != ',' {
			stk = append(stk, c)
		} else if c == ')' {
			var t, f int
			for stk[len(stk)-1] == 't' || stk[len(stk)-1] == 'f' {
				if stk[len(stk)-1] == 't' {
					t++
				} else {
					f++
				}
				stk = stk[:len(stk)-1]
			}
			op := stk[len(stk)-1]
			stk = stk[:len(stk)-1]
			c = 'f'
			if (op == '!' && f > 0) || (op == '&' && f == 0) || (op == '|' && t > 0) {
				c = 't'
			}
			stk = append(stk, c)
		}
	}
	return stk[0] == 't'
}

function parseBoolExpr(expression: string): boolean {
    const expr = expression;
    const n = expr.length;
    let i = 0;
    const dfs = () => {
        let res: boolean[] = [];
        while (i < n) {
            const c = expr[i++];
            if (c === ')') {
                break;
            }

            if (c === '!') {
                res.push(!dfs()[0]);
            } else if (c === '|') {
                res.push(dfs().some(v => v));
            } else if (c === '&') {
                res.push(dfs().every(v => v));
            } else if (c === 't') {
                res.push(true);
            } else if (c === 'f') {
                res.push(false);
            }
        }
        return res;
    };
    return dfs()[0];
}

impl Solution {
    fn dfs(i: &mut usize, expr: &[u8]) -> Vec<bool> {
        let n = expr.len();
        let mut res = Vec::new();
        while *i < n {
            let c = expr[*i];
            *i += 1;
            match c {
                b')' => {
                    break;
                }
                b't' => {
                    res.push(true);
                }
                b'f' => {
                    res.push(false);
                }
                b'!' => {
                    res.push(!Self::dfs(i, expr)[0]);
                }
                b'&' => {
                    res.push(Self::dfs(i, expr).iter().all(|v| *v));
                }
                b'|' => {
                    res.push(Self::dfs(i, expr).iter().any(|v| *v));
                }
                _ => {}
            }
        }
        res
    }

    pub fn parse_bool_expr(expression: String) -> bool {
        let expr = expression.as_bytes();
        let mut i = 0;
        Self::dfs(&mut i, expr)[0]
    }
}

1106 - Parsing A Boolean Expression

1106. Parsing A Boolean Expression (Hard)

Solution 1.

Solution 2.

All Problems

All Solutions

Welcome to Subscribe On Youtube

1106. Parsing A Boolean Expression (Hard)

Solution 1.

Solution 2.

All Problems

All Solutions