aboutsummaryrefslogtreecommitdiff
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
parent665f73a17b12ecec64f841623de9beef7e086abb (diff)
downloadleetcode-68b8faee8c8cb41cb423bb8a9e34833a290dc22e.tar.gz
leetcode-68b8faee8c8cb41cb423bb8a9e34833a290dc22e.zip
1106. parsing a boolean expression
-rw-r--r--parse_boolean_expression.c77
-rw-r--r--parse_boolean_expression.py49
2 files changed, 79 insertions, 47 deletions
diff --git a/parse_boolean_expression.c b/parse_boolean_expression.c
index f970141..f85d6c5 100644
--- a/parse_boolean_expression.c
+++ b/parse_boolean_expression.c
@@ -1,7 +1,5 @@
// 1106. Parsing A Boolean Expression
-#include <stdbool.h>
-#include <stdio.h>
-#include <stdlib.h>
+#include "leetcode.h"
/*
* a boolean expression is an expression that evaluates to either 'true' or
@@ -18,53 +16,38 @@
* evaluation of that expression
*/
-#define IS_VALUE(c) ((c) == 't' || (c) == 'f')
-#define IS_OPERA(c) ((c) == '!' || (c) == '&' || (c) == '|')
-
-static char *expr, *s;
-
-bool parse() {
- if (IS_VALUE(*s))
- return (*s++) == 't';
- if (IS_OPERA(*s)) {
- char op = *s;
- s++;
- if (*s != '(') {
- fprintf(stderr, "error: unexpected char '%c' at pos %ld, expects '('\n",
- *s, s - expr);
- exit(1);
- }
- s++;
- bool b = false;
- if (op == '!')
- b = !parse();
- else {
- b = parse();
- while (*s == ',') {
- s++;
- bool n = parse();
- if (op == '&')
- b = b && n;
- else
- b = b || n;
- }
- }
- if (*s != ')') {
- fprintf(stderr, "error: unexpected char '%c' at pos %ld, expects ')'\n",
- *s, s - expr);
- exit(1);
- }
- s++;
- return b;
- }
- fprintf(stderr, "error: unexpected char '%c' at pos %ld\n", *s, s - expr);
- exit(1);
+void substr(char *dst, char *src, int start, int len) {
+ strncpy(dst, src + start, len);
+ dst[len] = '\0';
}
bool parseBoolExpr(char *expression) {
- expr = expression;
- s = expression;
- return parse();
+ int n = strlen(expression);
+ if (n == 1)
+ return expression[0] == 't';
+ if (expression[0] == '!') {
+ char sub_expr[n - 2];
+ substr(sub_expr, expression, 2, n - 3);
+ return !parseBoolExpr(sub_expr);
+ }
+ bool is_and = expression[0] == '&', ans = is_and;
+ int i = 2, j = 2, cnt = 0;
+ for (; ans == is_and && i < n; ++i) {
+ if (expression[i] == '(')
+ ++cnt;
+ if (expression[i] == ')')
+ --cnt;
+ if (i == n - 1 || (expression[i] == ',' && !(cnt))) {
+ char sub_expr[i - j + 1];
+ substr(sub_expr, expression, j, i - 1);
+ if (is_and)
+ ans &= parseBoolExpr(sub_expr);
+ else
+ ans |= parseBoolExpr(sub_expr);
+ j = i + 1;
+ }
+ }
+ return ans;
}
int main() {
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))"))