aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-11-13 12:29:22 -0700
committerJack Sangdahl <[email protected]>2024-11-13 12:29:22 -0700
commit6ce80ea59406da5284927cffc5cf770fb1f09bcd (patch)
treebcf4b4f70eb6d20e33772a39e60f752d14680f4f
parent727982d9551b2d1c8238cf40e3fdfeb32c0355ad (diff)
downloadleetcode-6ce80ea59406da5284927cffc5cf770fb1f09bcd.tar.gz
leetcode-6ce80ea59406da5284927cffc5cf770fb1f09bcd.zip
1106. parsing a boolean expression (improvements)
-rw-r--r--parse_boolean_expression.c111
1 files changed, 84 insertions, 27 deletions
diff --git a/parse_boolean_expression.c b/parse_boolean_expression.c
index f85d6c5..f173258 100644
--- a/parse_boolean_expression.c
+++ b/parse_boolean_expression.c
@@ -16,38 +16,95 @@
* evaluation of that expression
*/
-void substr(char *dst, char *src, int start, int len) {
- strncpy(dst, src + start, len);
- dst[len] = '\0';
+struct parse_node {
+ char op;
+ char val;
+ int num_ops;
+ int cap;
+ struct parse_node **operand;
+};
+
+struct parse_node *parse_node_create(void) {
+ struct parse_node *p = (struct parse_node *)malloc(sizeof(struct parse_node));
+ p->op = '\0';
+ p->num_ops = 0;
+ p->cap = 4;
+ p->operand =
+ (struct parse_node **)malloc(p->cap * sizeof(struct parse_node *));
+ p->val = '?';
+ return p;
}
-bool parseBoolExpr(char *expression) {
- 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);
+void parse_node_free(struct parse_node *p) {
+ for (int i = 0; i < p->num_ops; i++)
+ parse_node_free(p->operand[i]);
+ free(p->operand);
+ free(p);
+}
+
+void parse_node_addop(struct parse_node *res, const struct parse_node *expr) {
+ res->operand[res->num_ops++] = (struct parse_node *)expr;
+ if (res->num_ops >= res->cap) {
+ res->cap <<= 1;
+ res->operand = (struct parse_node **)realloc(
+ res->operand, res->cap * sizeof(struct parse_node *));
+ }
+}
+
+int parse_expr(const char *expr, struct parse_node *res) {
+ char *orig_expr = (char *)expr;
+ switch (*expr) {
+ case '&':
+ case '|':
+ case '!':
+ res->op = *expr;
+ expr++;
+ do {
+ expr++;
+ struct parse_node *e = parse_node_create();
+ expr += parse_expr(expr, e);
+ parse_node_addop(res, e);
+ } while (*expr != ')');
+ expr++;
+ break;
+ case 't':
+ case 'f':
+ res->val = *expr++;
+ break;
}
- 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 expr - orig_expr;
+}
+
+bool parse_node_eval(struct parse_node *p) {
+ if (p->val != '?')
+ return p->val == 't';
+ if (p->op == '!')
+ return p->val = !parse_node_eval(p->operand[0]);
+ if (p->op == '&') {
+ for (int i = 0; i < p->num_ops; i++) {
+ bool v = parse_node_eval(p->operand[i]);
+ if (!v)
+ return p->val = false;
+ }
+ return p->val = true;
+ }
+ if (p->op == '|') {
+ for (int i = 0; i < p->num_ops; i++) {
+ bool v = parse_node_eval(p->operand[i]);
+ if (v)
+ return p->val = true;
}
+ return p->val = false;
}
- return ans;
+ return false;
+}
+
+bool parseBoolExpr(char *expression) {
+ struct parse_node *root = parse_node_create();
+ int len = parse_expr(expression, root);
+ bool eval = parse_node_eval(root);
+ parse_node_free(root);
+ return eval;
}
int main() {