aboutsummaryrefslogtreecommitdiff
path: root/parse_boolean_expression.c
blob: f85d6c5a842ffea23ed3fc23b4360a713d467c85 (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
// 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
 */

void substr(char *dst, char *src, int start, int len) {
  strncpy(dst, src + start, len);
  dst[len] = '\0';
}

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);
  }
  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() {
  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
}