3.7.1 Recursive Descent Parsing (Simple)

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

/*

Evaluate an expression in accordance to the order of operations (parentheses, unary plus and minus
signs, multiplication/division, addition/subtraction). The following is a minimalistic recursive
descent implementation using iterators. Each precedence level is parsed by its own function that
obtains operands by calling the next-tighter level, so the call structure itself enforces the order
of operations.

- `eval(s)` returns an evaluation of the arithmetic expression `s`.

Time Complexity:
- O(n) per call to `eval(s)`, where $n$ is the length of `s`.

Space Complexity:
- O(n) auxiliary stack space for `eval(s)`, where $n$ is the length of `s`.

*/

#include <string>

template<class It>
int eval(It &it, int prec) {
  if (prec == 0) {
    int sign = 1, res = 0;
    for (; *it == '-'; it++) {
      sign *= -1;
    }
    if (*it == '(') {
      res = eval(++it, 2);
      it++;
    } else
      while (*it >= '0' && *it <= '9') {
        res = 10 * res + (*(it++) - '0');
      }
    return sign * res;
  }
  int num = eval(it, prec - 1);
  while (!((prec == 2 && *it != '+' && *it != '-') || (prec == 1 && *it != '*' && *it != '/'))) {
    switch (*(it++)) {
      case '+':
        num += eval(it, prec - 1);
        break;
      case '-':
        num -= eval(it, prec - 1);
        break;
      case '*':
        num *= eval(it, prec - 1);
        break;
      case '/':
        num /= eval(it, prec - 1);
        break;
    }
  }
  return num;
}

int eval(const std::string &s) {
  std::string expr = s + '\0';
  auto it = expr.begin();
  return eval(it, 2);
}

/*** Example Usage ***/

#include <cassert>

int main() {
  assert(eval("1++1") == 2);
  assert(eval("1+2*3*4+3*(2+2)-100") == -63);
  return 0;
}