parse_boolean_expression.py (1660B)
| # 1106. Parsing A Boolean Expression
"""
a boolean expression is an expression that evaluates to either 'true' or
'false'. it can be one of the following shapes:
- 't' that evaluates to true
- 'f' that evaluates to false
- '!(subExpr)' that evalutes to the logical not of the inner expression
'subExpr'
- '&(subExpr1, subExpr2, ..., subExprn)' that evalutes 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
"""
class Solution(object):
def parseBoolExpr(self, expression):
"""
:type expression: str
:rtype: bool
"""
stack = []
for c in expression:
if c == ")":
seen = set()
while stack[-1] != "(":
seen.add(stack.pop())
stack.pop()
op = stack.pop()
stack.append(
all(seen)
if op == "&"
else any(seen)
if op == "|"
else not seen.pop()
)
elif c != ",":
stack.append(True if c == "t" else False if c == "f" else c)
return stack.pop()
if __name__ == "__main__":
obj = Solution()
print(obj.parseBoolExpr(expression="&(|(f))"))
print(obj.parseBoolExpr(expression="|(f,f,f,t)"))
print(obj.parseBoolExpr(expression="!(&(f,t))"))
|
