aboutsummaryrefslogtreecommitdiff
path: root/parse_boolean_expression.py
diff options
context:
space:
mode:
Diffstat (limited to 'parse_boolean_expression.py')
-rw-r--r--parse_boolean_expression.py49
1 files changed, 49 insertions, 0 deletions
diff --git a/parse_boolean_expression.py b/parse_boolean_expression.py
new file mode 100644
index 0000000..8027439
--- /dev/null
+++ b/parse_boolean_expression.py
@@ -0,0 +1,49 @@
+# 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))"))