##### Welcome to Subscribe On Youtube

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] != "(":
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]
}
}