1#include <stdlib.h> 2#include <ctype.h> 3 4/* 5grammar: 6 7Start = Expr ';' 8Expr = Or | Or '?' Expr ':' Expr 9Or = And | Or '||' And 10And = Eq | And '&&' Eq 11Eq = Rel | Eq '==' Rel | Eq '!=' Rel 12Rel = Add | Rel '<=' Add | Rel '>=' Add | Rel '<' Add | Rel '>' Add 13Add = Mul | Add '+' Mul | Add '-' Mul 14Mul = Prim | Mul '*' Prim | Mul '/' Prim | Mul '%' Prim 15Prim = '(' Expr ')' | '!' Prim | decimal | 'n' 16 17internals: 18 19recursive descent expression evaluator with stack depth limit. 20for binary operators an operator-precedence parser is used. 21eval* functions store the result of the parsed subexpression 22and return a pointer to the next non-space character. 23*/ 24 25struct st { 26 unsigned long r; 27 unsigned long n; 28 int op; 29}; 30 31static const char *skipspace(const char *s) 32{ 33 while (isspace(*s)) s++; 34 return s; 35} 36 37static const char *evalexpr(struct st *st, const char *s, int d); 38 39static 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 66static 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 87static 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 109static 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 133static 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 151unsigned 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} 158