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 totrue.'f'that evaluates tofalse.'!(subExpr)'that evaluates to the logical NOT of the inner expressionsubExpr.'&(subExpr1, subExpr2, ..., subExprn)'that evaluates to the logical AND of the inner expressionssubExpr1, subExpr2, ..., subExprnwheren >= 1.'|(subExpr1, subExpr2, ..., subExprn)'that evaluates to the logical OR of the inner expressionssubExpr1, subExpr2, ..., subExprnwheren >= 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;
}
list.add(temp);
}
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;
}
}
Input
expression = "&(|(f))"
Output
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]
}
Input
expression = "&(|(f))"
Output
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()
Input
expression = "|(f,f,f,t)"
Output
true