aboutsummaryrefslogtreecommitdiff
path: root/parse_boolean_expression.c
blob: f173258affeb012c5f026c88a974ce2038efd2aa (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// 1106. Parsing A Boolean Expression
#include "leetcode.h"

/*
 * 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
 */

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;
}

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;
  }
  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 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() {
  char e1[] = {"&(|(f))"}, e2[] = {"|(f,f,f,t)"}, e3[] = {"!(&(f,t))"};
  printf("%d\n", parseBoolExpr(e1)); // expect: 0
  printf("%d\n", parseBoolExpr(e2)); // expect: 1
  printf("%d\n", parseBoolExpr(e3)); // expect: 1
}