diff options
author | Jack Sangdahl <[email protected]> | 2024-10-19 21:40:53 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-19 21:40:53 -0600 |
commit | 68b8faee8c8cb41cb423bb8a9e34833a290dc22e (patch) | |
tree | b0f9dcc1ba6ec40d8b4daf38087e59065fbab874 /parse_boolean_expression.py | |
parent | 665f73a17b12ecec64f841623de9beef7e086abb (diff) | |
download | leetcode-68b8faee8c8cb41cb423bb8a9e34833a290dc22e.tar.gz leetcode-68b8faee8c8cb41cb423bb8a9e34833a290dc22e.zip |
1106. parsing a boolean expression
Diffstat (limited to 'parse_boolean_expression.py')
-rw-r--r-- | parse_boolean_expression.py | 49 |
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))")) |