## Algorithm

Problem Name: 1106. Parsing A Boolean Expression

A boolean expression is an expression that evaluates to either `true` or `false`. It can be in one of the following shapes:

• `'t'` that evaluates to `true`.
• `'f'` that evaluates to `false`.
• `'!(subExpr)'` that evaluates to the logical NOT of the inner expression `subExpr`.
• `'&(subExpr1, subExpr2, ..., subExprn)'` that evaluates to the logical AND of the inner expressions `subExpr1, subExpr2, ..., subExprn` where `n >= 1`.
• `'|(subExpr1, subExpr2, ..., subExprn)'` that evaluates to the logical OR of the inner expressions `subExpr1, subExpr2, ..., subExprn` where `n >= 1`.

Given a string `expression` that represents a boolean expression, return the evaluation of that expression.

It is guaranteed that the given expression is valid and follows the given rules.

Example 1:

```Input: expression = "&(|(f))"
Output: false
Explanation:
First, evaluate |(f) --> f. The expression is now "&(f)".
Then, evaluate &(f) --> f. The expression is now "f".
Finally, return false.
```

Example 2:

```Input: expression = "|(f,f,f,t)"
Output: true
Explanation: The evaluation of (false OR false OR false OR true) is true.
```

Example 3:

```Input: expression = "!(&(f,t))"
Output: true
Explanation:
First, evaluate &(f,t) --> (false AND true) --> false --> f. The expression is now "!(f)".
Then, evaluate !(f) --> NOT false --> true. We return true.
```

Constraints:

• `1 <= expression.length <= 2 * 104`
• expression[i] is one following characters: `'('`, `')'`, `'&'`, `'|'`, `'!'`, `'t'`, `'f'`, and `','`.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean parseBoolExpr(String expression) {
char[] chars = expression.toCharArray();
Stack < Character> operations = new Stack<>();
Stack boolValues = new Stack<>();

for (int i = 0; i  <  chars.length; i++) {
char c = chars[i];
if (c == '!' || c == '&' || c == '|') {
operations.push(c);
}
else if (c == '(') {
boolValues.push('#');
}
else if (c == 't' || c == 'f') {
boolValues.push(chars[i]);
}
else if (c == ',') {
continue;
}
else {
List < Character> list = new ArrayList<>();
while (!boolValues.isEmpty()) {
char temp = boolValues.pop();
if (temp == '#') {
break;
}

}

boolValues.push(performOperation(list, operations.pop()));
}
}

return boolValues.peek() == 't' ? true : false;
}

private Character performOperation(List < Character> list, Character operation) {
if (operation == '|') {
return performOr(list);
}
else if (operation == '&') {
return performAnd(list);
}
else {
return list.get(0) == 't' ? 'f' : 't';
}
}

private Character performAnd(List < Character> list) {
boolean val = getBooleanValue(list.get(0));
for (int i = 1; i  <  list.size(); i++) {
val &= getBooleanValue(list.get(i));
}

return val ? 't' : 'f';
}

private Character performOr(List < Character> list) {
boolean val = getBooleanValue(list.get(0));
for (int i = 1; i  <  list.size(); i++) {
val |= getBooleanValue(list.get(i));
}

return val ? 't' : 'f';
}

private boolean getBooleanValue(Character character) {
return character == 't' ? true : false;
}
}
``````
Copy The Code &

Input

cmd
expression = "&(|(f))"

Output

cmd
false

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const parseBoolExpr = function(expression) {
const stack = []
for (let ch of expression) {
if (ch === '|' || ch === '&' || ch === '!') stack.push(ch)
if (ch === 't') stack.push(true)
if (ch === 'f') stack.push(false)
if (ch === ')') {
const tmp = []
while (stack.length) {
let t = stack.pop()
if (t === true || t === false) tmp.push(t)
else {
let res = tmp.pop()
if (t === '|') {
while (tmp.length) res = tmp.pop() || res
} else if (t === '&') {
while (tmp.length) res = tmp.pop() && res
} else if (t === '!') {
res = !res
}
stack.push(res)
break
}
}
}
}
return stack[0]
}
``````
Copy The Code &

Input

cmd
expression = "&(|(f))"

Output

cmd
false

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def parseBoolExpr(self, expression: str) -> bool:
stack = []
for c in expression:
if c == ')':
cache = []
while stack[-1] != '(':
cache.append(stack.pop())
stack.pop()
cur = stack.pop()
stack.append(all(cache) if cur == '&' else any(cache) if cur == '|' else not cache.pop())
elif c != ',':
stack.append(True if c == 't' else False if c == 'f' else c)
return stack.pop()
``````
Copy The Code &

Input

cmd
expression = "|(f,f,f,t)"

Output

cmd
true