3.7.1 Recursive Descent Parsing

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

/*

Evaluate integer arithmetic expressions containing parentheses, unary plus and minus, multiplication
and division, and addition and subtraction. The parser represents these as three precedence levels.
At the tightest level, it consumes a chain of unary signs followed by either a decimal literal or a
parenthesized expression.

At each binary-operator level, the parser first evaluates one operand at the next tighter level,
then repeatedly consumes operators of the current level and their right operands. These loops make
binary operators left-associative, while recursively restarting at the loosest level inside
parentheses enforces grouping.

Literals must be nonnegative decimal integers, although unary signs may precede them. The input must
be valid and contain no whitespace. Division truncates toward zero, and every divisor must be
nonzero.

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

Overflow warning: All intermediate results must fit in `int`.

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

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

*/

#include <string>

int eval(const std::string &s) {
  std::string expr = s + '\0';
  auto it = expr.begin();
  auto rec = [&](auto &&rec, int prec) -> int {
    if (prec == 0) {
      int sign = 1, res = 0;
      for (; *it == '-' || *it == '+'; it++) {
        if (*it == '-') {
          sign *= -1;
        }
      }
      if (*it == '(') {
        it++;
        res = rec(rec, 2);
        it++;
      } else {
        while (*it >= '0' && *it <= '9') {
          res = 10 * res + (*(it++) - '0');
        }
      }
      return sign * res;
    }
    int num = rec(rec, prec - 1);
    while (!((prec == 2 && *it != '+' && *it != '-') || (prec == 1 && *it != '*' && *it != '/'))) {
      switch (*(it++)) {
        case '+':
          num += rec(rec, prec - 1);
          break;
        case '-':
          num -= rec(rec, prec - 1);
          break;
        case '*':
          num *= rec(rec, prec - 1);
          break;
        case '/':
          num /= rec(rec, prec - 1);
          break;
      }
    }
    return num;
  };
  return rec(rec, 2);
}

/*** Example Usage ***/

#include <cassert>

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