blob: 04da1c45e85989c831d1e5deb84055498e0e42b9 [file] [log] [blame]
#include <stdlib.h>
#include <ctype.h>
#include "pleval.h"
/*
grammar:
Start = Expr ';'
Expr = Or | Or '?' Expr ':' Expr
Or = And | Or '||' And
And = Eq | And '&&' Eq
Eq = Rel | Eq '==' Rel | Eq '!=' Rel
Rel = Add | Rel '<=' Add | Rel '>=' Add | Rel '<' Add | Rel '>' Add
Add = Mul | Add '+' Mul | Add '-' Mul
Mul = Prim | Mul '*' Prim | Mul '/' Prim | Mul '%' Prim
Prim = '(' Expr ')' | '!' Prim | decimal | 'n'
internals:
recursive descent expression evaluator with stack depth limit.
for binary operators an operator-precedence parser is used.
eval* functions store the result of the parsed subexpression
and return a pointer to the next non-space character.
*/
struct st {
unsigned long r;
unsigned long n;
int op;
};
static const char *skipspace(const char *s)
{
while (isspace(*s)) s++;
return s;
}
static const char *evalexpr(struct st *st, const char *s, int d);
static const char *evalprim(struct st *st, const char *s, int d)
{
char *e;
if (--d < 0) return "";
s = skipspace(s);
if (isdigit(*s)) {
st->r = strtoul(s, &e, 10);
if (e == s || st->r == -1) return "";
return skipspace(e);
}
if (*s == 'n') {
st->r = st->n;
return skipspace(s+1);
}
if (*s == '(') {
s = evalexpr(st, s+1, d);
if (*s != ')') return "";
return skipspace(s+1);
}
if (*s == '!') {
s = evalprim(st, s+1, d);
st->r = !st->r;
return s;
}
return "";
}
static int binop(struct st *st, int op, unsigned long left)
{
unsigned long a = left, b = st->r;
switch (op) {
case 0: st->r = a||b; return 0;
case 1: st->r = a&&b; return 0;
case 2: st->r = a==b; return 0;
case 3: st->r = a!=b; return 0;
case 4: st->r = a>=b; return 0;
case 5: st->r = a<=b; return 0;
case 6: st->r = a>b; return 0;
case 7: st->r = a<b; return 0;
case 8: st->r = a+b; return 0;
case 9: st->r = a-b; return 0;
case 10: st->r = a*b; return 0;
case 11: if (b) {st->r = a%b; return 0;} return 1;
case 12: if (b) {st->r = a/b; return 0;} return 1;
}
return 1;
}
static const char *parseop(struct st *st, const char *s)
{
static const char opch[11] = "|&=!><+-*%/";
static const char opch2[6] = "|&====";
int i;
for (i=0; i<11; i++)
if (*s == opch[i]) {
/* note: >,< are accepted with or without = */
if (i<6 && s[1] == opch2[i]) {
st->op = i;
return s+2;
}
if (i>=4) {
st->op = i+2;
return s+1;
}
break;
}
st->op = 13;
return s;
}
static const char *evalbinop(struct st *st, const char *s, int minprec, int d)
{
static const char prec[14] = {1,2,3,3,4,4,4,4,5,5,6,6,6,0};
unsigned long left;
int op;
d--;
s = evalprim(st, s, d);
s = parseop(st, s);
for (;;) {
/*
st->r (left hand side value) and st->op are now set,
get the right hand side or back out if op has low prec,
if op was missing then prec[op]==0
*/
op = st->op;
if (prec[op] <= minprec)
return s;
left = st->r;
s = evalbinop(st, s, prec[op], d);
if (binop(st, op, left))
return "";
}
}
static const char *evalexpr(struct st *st, const char *s, int d)
{
unsigned long a, b;
if (--d < 0)
return "";
s = evalbinop(st, s, 0, d);
if (*s != '?')
return s;
a = st->r;
s = evalexpr(st, s+1, d);
if (*s != ':')
return "";
b = st->r;
s = evalexpr(st, s+1, d);
st->r = a ? b : st->r;
return s;
}
unsigned long __pleval(const char *s, unsigned long n)
{
struct st st;
st.n = n;
s = evalexpr(&st, s, 100);
return *s == ';' ? st.r : -1;
}