Can you solve this real interview question? 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.
class Solution:
def parseBoolExpr(self, expression: str) -> bool:
st = deque()
for c in expression:
if c == "," or c == "(":
continue
if c in ["t", "f", "!", "&", "|"]:
st.append(c)
elif c == ")":
has_true = False
has_false = False
while st[-1] not in ["!", "&", "|"]:
top_value = st.pop()
if top_value == "t":
has_true = True
elif top_value == "f":
has_false = True
op = st.pop()
if op == "!":
st.append("t" if not has_true else "f")
elif op == "&":
st.append("f" if has_false else "t")
else:
st.append("t" if has_true else "f")
return st[-1] == "t"