aboutsummaryrefslogtreecommitdiff
path: root/parse_boolean_expression.c
blob: f970141999f728fec039e822c1488264330b649b (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
// 1106. Parsing A Boolean Expression
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.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
 */

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

bool parseBoolExpr(char *expression) {
  expr = expression;
  s = expression;
  return parse();
}

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
}