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 | |
parent | 665f73a17b12ecec64f841623de9beef7e086abb (diff) | |
download | leetcode-68b8faee8c8cb41cb423bb8a9e34833a290dc22e.tar.gz leetcode-68b8faee8c8cb41cb423bb8a9e34833a290dc22e.zip |
1106. parsing a boolean expression
-rw-r--r-- | parse_boolean_expression.c | 77 | ||||
-rw-r--r-- | parse_boolean_expression.py | 49 |
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))")) |