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