aboutsummaryrefslogtreecommitdiff
path: root/parse_boolean_expression.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-19 21:40:53 -0600
committerJack Sangdahl <[email protected]>2024-10-19 21:40:53 -0600
commit68b8faee8c8cb41cb423bb8a9e34833a290dc22e (patch)
treeb0f9dcc1ba6ec40d8b4daf38087e59065fbab874 /parse_boolean_expression.py
parent665f73a17b12ecec64f841623de9beef7e086abb (diff)
downloadleetcode-68b8faee8c8cb41cb423bb8a9e34833a290dc22e.tar.gz
leetcode-68b8faee8c8cb41cb423bb8a9e34833a290dc22e.zip
1106. parsing a boolean expression
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))"))