[337] | 1 | #include <stdlib.h>
|
---|
| 2 | #include <ctype.h>
|
---|
| 3 |
|
---|
| 4 | /*
|
---|
| 5 | grammar:
|
---|
| 6 |
|
---|
| 7 | Start = Expr ';'
|
---|
| 8 | Expr = Or | Or '?' Expr ':' Expr
|
---|
| 9 | Or = And | Or '||' And
|
---|
| 10 | And = Eq | And '&&' Eq
|
---|
| 11 | Eq = Rel | Eq '==' Rel | Eq '!=' Rel
|
---|
| 12 | Rel = Add | Rel '<=' Add | Rel '>=' Add | Rel '<' Add | Rel '>' Add
|
---|
| 13 | Add = Mul | Add '+' Mul | Add '-' Mul
|
---|
| 14 | Mul = Prim | Mul '*' Prim | Mul '/' Prim | Mul '%' Prim
|
---|
| 15 | Prim = '(' Expr ')' | '!' Prim | decimal | 'n'
|
---|
| 16 |
|
---|
| 17 | internals:
|
---|
| 18 |
|
---|
| 19 | recursive descent expression evaluator with stack depth limit.
|
---|
| 20 | for binary operators an operator-precedence parser is used.
|
---|
| 21 | eval* functions store the result of the parsed subexpression
|
---|
| 22 | and return a pointer to the next non-space character.
|
---|
| 23 | */
|
---|
| 24 |
|
---|
| 25 | struct st {
|
---|
| 26 | unsigned long r;
|
---|
| 27 | unsigned long n;
|
---|
| 28 | int op;
|
---|
| 29 | };
|
---|
| 30 |
|
---|
| 31 | static const char *skipspace(const char *s)
|
---|
| 32 | {
|
---|
| 33 | while (isspace(*s)) s++;
|
---|
| 34 | return s;
|
---|
| 35 | }
|
---|
| 36 |
|
---|
| 37 | static const char *evalexpr(struct st *st, const char *s, int d);
|
---|
| 38 |
|
---|
| 39 | static const char *evalprim(struct st *st, const char *s, int d)
|
---|
| 40 | {
|
---|
| 41 | char *e;
|
---|
| 42 | if (--d < 0) return "";
|
---|
| 43 | s = skipspace(s);
|
---|
| 44 | if (isdigit(*s)) {
|
---|
| 45 | st->r = strtoul(s, &e, 10);
|
---|
| 46 | if (e == s || st->r == -1) return "";
|
---|
| 47 | return skipspace(e);
|
---|
| 48 | }
|
---|
| 49 | if (*s == 'n') {
|
---|
| 50 | st->r = st->n;
|
---|
| 51 | return skipspace(s+1);
|
---|
| 52 | }
|
---|
| 53 | if (*s == '(') {
|
---|
| 54 | s = evalexpr(st, s+1, d);
|
---|
| 55 | if (*s != ')') return "";
|
---|
| 56 | return skipspace(s+1);
|
---|
| 57 | }
|
---|
| 58 | if (*s == '!') {
|
---|
| 59 | s = evalprim(st, s+1, d);
|
---|
| 60 | st->r = !st->r;
|
---|
| 61 | return s;
|
---|
| 62 | }
|
---|
| 63 | return "";
|
---|
| 64 | }
|
---|
| 65 |
|
---|
| 66 | static int binop(struct st *st, int op, unsigned long left)
|
---|
| 67 | {
|
---|
| 68 | unsigned long a = left, b = st->r;
|
---|
| 69 | switch (op) {
|
---|
| 70 | case 0: st->r = a||b; return 0;
|
---|
| 71 | case 1: st->r = a&&b; return 0;
|
---|
| 72 | case 2: st->r = a==b; return 0;
|
---|
| 73 | case 3: st->r = a!=b; return 0;
|
---|
| 74 | case 4: st->r = a>=b; return 0;
|
---|
| 75 | case 5: st->r = a<=b; return 0;
|
---|
| 76 | case 6: st->r = a>b; return 0;
|
---|
| 77 | case 7: st->r = a<b; return 0;
|
---|
| 78 | case 8: st->r = a+b; return 0;
|
---|
| 79 | case 9: st->r = a-b; return 0;
|
---|
| 80 | case 10: st->r = a*b; return 0;
|
---|
| 81 | case 11: if (b) {st->r = a%b; return 0;} return 1;
|
---|
| 82 | case 12: if (b) {st->r = a/b; return 0;} return 1;
|
---|
| 83 | }
|
---|
| 84 | return 1;
|
---|
| 85 | }
|
---|
| 86 |
|
---|
| 87 | static const char *parseop(struct st *st, const char *s)
|
---|
| 88 | {
|
---|
| 89 | static const char opch[11] = "|&=!><+-*%/";
|
---|
| 90 | static const char opch2[6] = "|&====";
|
---|
| 91 | int i;
|
---|
| 92 | for (i=0; i<11; i++)
|
---|
| 93 | if (*s == opch[i]) {
|
---|
| 94 | /* note: >,< are accepted with or without = */
|
---|
| 95 | if (i<6 && s[1] == opch2[i]) {
|
---|
| 96 | st->op = i;
|
---|
| 97 | return s+2;
|
---|
| 98 | }
|
---|
| 99 | if (i>=4) {
|
---|
| 100 | st->op = i+2;
|
---|
| 101 | return s+1;
|
---|
| 102 | }
|
---|
| 103 | break;
|
---|
| 104 | }
|
---|
| 105 | st->op = 13;
|
---|
| 106 | return s;
|
---|
| 107 | }
|
---|
| 108 |
|
---|
| 109 | static const char *evalbinop(struct st *st, const char *s, int minprec, int d)
|
---|
| 110 | {
|
---|
| 111 | static const char prec[14] = {1,2,3,3,4,4,4,4,5,5,6,6,6,0};
|
---|
| 112 | unsigned long left;
|
---|
| 113 | int op;
|
---|
| 114 | d--;
|
---|
| 115 | s = evalprim(st, s, d);
|
---|
| 116 | s = parseop(st, s);
|
---|
| 117 | for (;;) {
|
---|
| 118 | /*
|
---|
| 119 | st->r (left hand side value) and st->op are now set,
|
---|
| 120 | get the right hand side or back out if op has low prec,
|
---|
| 121 | if op was missing then prec[op]==0
|
---|
| 122 | */
|
---|
| 123 | op = st->op;
|
---|
| 124 | if (prec[op] <= minprec)
|
---|
| 125 | return s;
|
---|
| 126 | left = st->r;
|
---|
| 127 | s = evalbinop(st, s, prec[op], d);
|
---|
| 128 | if (binop(st, op, left))
|
---|
| 129 | return "";
|
---|
| 130 | }
|
---|
| 131 | }
|
---|
| 132 |
|
---|
| 133 | static const char *evalexpr(struct st *st, const char *s, int d)
|
---|
| 134 | {
|
---|
| 135 | unsigned long a, b;
|
---|
| 136 | if (--d < 0)
|
---|
| 137 | return "";
|
---|
| 138 | s = evalbinop(st, s, 0, d);
|
---|
| 139 | if (*s != '?')
|
---|
| 140 | return s;
|
---|
| 141 | a = st->r;
|
---|
| 142 | s = evalexpr(st, s+1, d);
|
---|
| 143 | if (*s != ':')
|
---|
| 144 | return "";
|
---|
| 145 | b = st->r;
|
---|
| 146 | s = evalexpr(st, s+1, d);
|
---|
| 147 | st->r = a ? b : st->r;
|
---|
| 148 | return s;
|
---|
| 149 | }
|
---|
| 150 |
|
---|
| 151 | unsigned long __pleval(const char *s, unsigned long n)
|
---|
| 152 | {
|
---|
| 153 | struct st st;
|
---|
| 154 | st.n = n;
|
---|
| 155 | s = evalexpr(&st, s, 100);
|
---|
| 156 | return *s == ';' ? st.r : -1;
|
---|
| 157 | }
|
---|