/************************************************************************
integer arithmetic expression evaluater

$ ./evaluate "4+4/2"
[4+4/2] = 6

$ ./evaluate "(4+4)/2"
[(4+4)/2] = 4

$ ./evaluate "(4+4)/2 < 100"
[(4+4)/2 < 100] = 1

$ ./evaluate "(4+4)/2 > 100"
[(4+4)/2 > 100] = 0

$ ./evaluate "x = abs(\$SEVEN - 9 ^ 2); z = x / 2 - 1; z > 35 && z < 37"
[x = abs($SEVEN - 9 ^ 2); z = x / 2 - 1; z > 35 && z < 37] = 1

$ ./evaluate "x=abs(\$SEVEN-9^2);z=x/2-1;z>35&&z<37"
[x=abs($SEVEN-9^2);z=x/2-1;z>35&&z<37] = 1

The bitwise or and bitwise and aren't actually implemented, but the logical
&& and || are.  Bitwise or and and should probably be done as having higher
precedence than equality/inequality, unlike C, which always requires
parenthesis to do what you want it to do.
************************************************************************/
#include <stdio.h>
#include <string.h>
#include <math.h>

#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif

#define TOKEN_FAIL           -1
#define TOKEN_DONE           1
#define TOKEN_NEG            2
#define TOKEN_NOT            3
#define TOKEN_POWER          4
#define TOKEN_MULTIPLY       5
#define TOKEN_DIVIDE         6
#define TOKEN_ADD            7
#define TOKEN_SUBTRACT       8
#define TOKEN_EQUALITY       9
#define TOKEN_INEQUALITY     10
#define TOKEN_LESSTHAN       11
#define TOKEN_GREATERTHAN    12
#define TOKEN_LESSTHANEQ     13
#define TOKEN_GREATERTHANEQ  14
#define TOKEN_BITOR          15
#define TOKEN_BITAND         16
#define TOKEN_AND            17
#define TOKEN_OR             18
#define TOKEN_VALUE          19
#define TOKEN_ASSIGN         20
#define TOKEN_EXPRESSION     21
#define TOKEN_ENDEXPRESSION  22
#define TOKEN_ABS            23

typedef struct tagEXPRESSION {
   char *   pos;
   int      value;
   int      token;
   int      stackptr;
   int      stack[64];
   int      lastvar;
   int      uservar[26]; /* stores a-z = assignments */
} EXPRESSION;

void do_logical_ors(EXPRESSION * xpr);

/************************************************************************
 * BEWARE a correspondence between the order of these $-prefixed things
 * (these could be used to hook the evaluator up to other systems)
 * and the order of the switch cases in the parse_variable function.
 * If anything is changed here, the switch statement in parse_variable
 * must also be changed to match.
 ***********************************************************************/
char * variable_names[] = {
   "SEVEN",                   /* Support "$SEVEN" in expressions */
   NULL
};

/************************************************************************
 * Case insensitive string search (haystack, needle)
 * All of str2 must be found within str1 to succeed
 ***********************************************************************/
int instr3(unsigned char * str1, unsigned char * str2) {
   while (*str2) {
      if (tolower(*str1) != tolower(*str2)) {
         return FALSE;
      }
      str1++;
      str2++;
   }
   return TRUE;	/* we matched all the way to the end */
}

/************************************************************************
 * intpow()
 * Use math.c pow() if converting to floats.
 ***********************************************************************/
int intpow(int base, int expo) {
 int result = 1;
   while (expo--) {
      result = result * base;
   }
   return result;
}

/************************************************************************
 * A special '$'-prefixed variable has been encountered in the expression.
 * We'll replace it with something else by setting xpr->token to VALUE,
 * advancing xpr->pos past the variable name, and setting xpr->value to
 * what we're replacing it with.
 ***********************************************************************/
void parse_variable(EXPRESSION * xpr) {
 int done = FALSE;
 int i;

   i = 0;
   while (!done) {
      if (variable_names[i]) {
         if (instr3(xpr->pos, variable_names[i])) {
            xpr->pos += strlen(variable_names[i]);
            xpr->token = TOKEN_VALUE;
            switch (i) {
             case 0: /* SEVEN */
               xpr->value = 7; // we could support dice like $1D6
               break;
             default:
               xpr->value = 0;
               break;
            }
            done = TRUE;
         } else {
            i++;
         }
      } else {
         done = TRUE;
         xpr->token = TOKEN_FAIL;
      }
   }
   return;
}

/************************************************************************
 * Skip whitespace, identify token, extract constant, advance position.
 ***********************************************************************/
void scan(EXPRESSION * xpr) {
 int i, j;
 char * num;
 char c;

   /* skip whitespace */
   while (*xpr->pos && *xpr->pos == ' ') {
      xpr->pos++;
   }
   switch (*xpr->pos) {
    case 0:   xpr->token = TOKEN_DONE; break;
    case ';': xpr->token = TOKEN_DONE; xpr->pos++; break;
    case '~': xpr->token = TOKEN_NEG; xpr->pos++; break;
    case '!': xpr->token = TOKEN_NOT; xpr->pos++;
              if (*xpr->pos == '=') {
                 xpr->token = TOKEN_INEQUALITY; xpr->pos++;
              }
              break;
    case '+': xpr->token = TOKEN_ADD; xpr->pos++; break;
    case '-': xpr->token = TOKEN_SUBTRACT; xpr->pos++; break;
    case '*': xpr->token = TOKEN_MULTIPLY; xpr->pos++; break;
    case '/': xpr->token = TOKEN_DIVIDE; xpr->pos++; break;
    case '^': xpr->token = TOKEN_POWER; xpr->pos++; break;
    case '(': xpr->token = TOKEN_EXPRESSION; xpr->pos++; break;
    case ')': xpr->token = TOKEN_ENDEXPRESSION; xpr->pos++; break;
    case '|': xpr->token = TOKEN_BITOR; xpr->pos++;
              if (*xpr->pos == '|') {
                 xpr->token = TOKEN_OR; xpr->pos++;
              }
              break;
    case '&': xpr->token = TOKEN_BITAND; xpr->pos++;
              if (*xpr->pos == '&') {
                 xpr->token = TOKEN_AND; xpr->pos++;
              }
              break;
    case '=': xpr->token = TOKEN_ASSIGN; xpr->pos++;
              if (*xpr->pos == '=') {
                 xpr->token = TOKEN_EQUALITY; xpr->pos++;
              } else
              if (*xpr->pos == '<') {
                 xpr->token = TOKEN_LESSTHANEQ; xpr->pos++;
              } else
              if (*xpr->pos == '>') {
                 xpr->token = TOKEN_GREATERTHANEQ; xpr->pos++;
              }
              break;
    case '<': xpr->token = TOKEN_LESSTHAN; xpr->pos++;
              if (*xpr->pos == '=') {
                 xpr->token = TOKEN_LESSTHANEQ; xpr->pos++;
              } else
              if (*xpr->pos == '>') {
                 xpr->token = TOKEN_INEQUALITY; xpr->pos++;
              }
              break;
    case '>': xpr->token = TOKEN_GREATERTHAN; xpr->pos++;
              if (*xpr->pos == '=') {
                 xpr->token = TOKEN_GREATERTHANEQ; xpr->pos++;
              } else
              if (*xpr->pos == '<') {
                 xpr->token = TOKEN_INEQUALITY; xpr->pos++;
              }
              break;
    case '$': xpr->pos++; parse_variable(xpr); break;
    default:
      /*
       * test for constant, previously defined variable, or
       * functions such as sqrt()
       */
      if (*xpr->pos >= '0' && *xpr->pos <= '9') {
         /* determine length of numeric constant */
         i = 0;
         num = xpr->pos;
         while (*num >= '0' && *num <= '9') {
            i++;
            num++;
         }
         num = (char *)malloc(i+1);
         /* copy constant and advance xpr->pos */
         j = 0;
         while (j < i) {
            num[j++] = *xpr->pos++;
         }
         num[j] = 0;
         sscanf(num, "%d", &xpr->value);
         xpr->token = TOKEN_VALUE;
         free(num);
      } else {
         if (instr3(xpr->pos, "abs")) {
            xpr->token = TOKEN_ABS;
            xpr->pos += 3;
         } else {
            c = tolower(*xpr->pos);
            if (c >= 'a' && c <= 'z') {
               i = c - 'a';
               /* Remember variable in case '=' follows */
               xpr->lastvar = i;
               xpr->value = xpr->uservar[i];
               xpr->pos++;
               xpr->token = TOKEN_VALUE;
            } else {
               xpr->token = TOKEN_FAIL;
            }
         }		
      }
      break;
   }
   return;
}

/************************************************************************
 ***********************************************************************/
int pop_stack(EXPRESSION * xpr) {
 int result = xpr->stackptr;
   xpr->stackptr--;
   return result;
}

/************************************************************************
 ***********************************************************************/
void do_powers(EXPRESSION * xpr) {
   if (xpr->token == TOKEN_VALUE) {
      /* push value on stack */
      xpr->stack[++xpr->stackptr] = xpr->value;
      scan(xpr);
      /* handle special case of assignment */
      if (xpr->token == TOKEN_ASSIGN) {
         pop_stack(xpr);
         if (xpr->lastvar != -1) {
          int thisvar = xpr->lastvar;
            xpr->lastvar = -1;
            scan(xpr);
            do_logical_ors(xpr);
            xpr->uservar[thisvar] = xpr->stack[xpr->stackptr];
         } else {
            xpr->token = TOKEN_FAIL;
         }
      } else {
         xpr->lastvar = -1;
      }
   } else if (xpr->token == TOKEN_NOT) {
      scan(xpr);
      do_powers(xpr);
      if (xpr->stack[xpr->stackptr]) {
         xpr->stack[xpr->stackptr] = FALSE;
      } else {
         xpr->stack[xpr->stackptr] = TRUE;
      }
   } else if (xpr->token == TOKEN_NEG) {
      scan(xpr);
      do_powers(xpr);
      xpr->stack[xpr->stackptr] = ~ xpr->stack[xpr->stackptr];
   } else if (xpr->token == TOKEN_SUBTRACT) {
      scan(xpr);
      do_powers(xpr);
      xpr->stack[xpr->stackptr] = -1 * xpr->stack[xpr->stackptr];
   } else if (xpr->token == TOKEN_EXPRESSION) {
      /* evaluate nested expression */
      scan(xpr);
      do_logical_ors(xpr);
      if (xpr->token == TOKEN_ENDEXPRESSION) {
         scan(xpr);
      } else {
         xpr->token = TOKEN_FAIL;
      }
   } else if (xpr->token == TOKEN_ABS) {
    int token = xpr->token;
      scan(xpr);
      if (xpr->token == TOKEN_EXPRESSION) {
         scan(xpr);
         do_logical_ors(xpr);
         if (xpr->token == TOKEN_ENDEXPRESSION) {
            xpr->stack[xpr->stackptr] = abs(xpr->stack[xpr->stackptr]);
            scan(xpr);
         } else {
            xpr->token = TOKEN_FAIL;
         }
      } else {
         xpr->token = TOKEN_FAIL;
      }
   } else {
      if (xpr->token != TOKEN_DONE) {
         xpr->token = TOKEN_FAIL;
      }
   }
   return;
}

/************************************************************************
 ***********************************************************************/
void do_factors(EXPRESSION * xpr) {
   do_powers(xpr);

   while (xpr->token == TOKEN_POWER) {
    int oldptr;
      scan(xpr);
      do_powers(xpr);
      oldptr = pop_stack(xpr);
      xpr->stack[xpr->stackptr] = intpow(xpr->stack[xpr->stackptr], xpr->stack[oldptr]);
   }
   return;
}

/************************************************************************
 ***********************************************************************/
void do_terms(EXPRESSION * xpr) {
   do_factors(xpr);

   while (xpr->token == TOKEN_MULTIPLY	|| xpr->token == TOKEN_DIVIDE) {
    int oldptr, token;

      token = xpr->token;
      scan(xpr);
      do_factors(xpr);
      oldptr = pop_stack(xpr);

      switch (token) {
       case TOKEN_MULTIPLY:
        xpr->stack[xpr->stackptr] *= xpr->stack[oldptr];
        break;
       case TOKEN_DIVIDE:
        if (xpr->stack[oldptr] == 0) {
           xpr->stack[xpr->stackptr] = ~0; /* hmm.. / 0 error */
        } else {
           xpr->stack[xpr->stackptr] /= xpr->stack[oldptr];
        }
        break;
      }
   }
   return;
}

/************************************************************************
 ***********************************************************************/
void do_expression(EXPRESSION * xpr) {
   do_terms(xpr);

   while (xpr->token == TOKEN_ADD || xpr->token == TOKEN_SUBTRACT) {
    int oldptr, token;

      token = xpr->token;
      scan(xpr);
      do_terms(xpr);
      oldptr = pop_stack(xpr);

      switch (token) {
       case TOKEN_ADD:
         xpr->stack[xpr->stackptr] += xpr->stack[oldptr];
         break;
       case TOKEN_SUBTRACT:
         xpr->stack[xpr->stackptr] -= xpr->stack[oldptr];
         break;
      }
   }
   return;
}

/************************************************************************
 ***********************************************************************/
void do_condition(EXPRESSION * xpr) {
   do_expression(xpr);
   while (xpr->token == TOKEN_EQUALITY ||
          xpr->token == TOKEN_INEQUALITY ||
          xpr->token == TOKEN_LESSTHAN ||
          xpr->token == TOKEN_GREATERTHAN ||
          xpr->token == TOKEN_LESSTHANEQ ||
          xpr->token == TOKEN_GREATERTHANEQ) {
    int oldptr, token;

      token = xpr->token;
      scan(xpr);
      do_expression(xpr);
      oldptr = pop_stack(xpr);

      switch (token) {
       case TOKEN_EQUALITY:
         if (xpr->stack[xpr->stackptr] == xpr->stack[oldptr]) {
            xpr->stack[xpr->stackptr] = 1;
         } else {
            xpr->stack[xpr->stackptr] = 0;
         }
         break;
       case TOKEN_INEQUALITY:
         if (xpr->stack[xpr->stackptr] != xpr->stack[oldptr]) {
            xpr->stack[xpr->stackptr] = 1;
         } else {
            xpr->stack[xpr->stackptr] = 0;
         }
         break;
       case TOKEN_LESSTHAN:
         if (xpr->stack[xpr->stackptr] < xpr->stack[oldptr]) {
            xpr->stack[xpr->stackptr] = 1;
         } else {
            xpr->stack[xpr->stackptr] = 0;
         }
         break;
       case TOKEN_GREATERTHAN:
         if (xpr->stack[xpr->stackptr] > xpr->stack[oldptr]) {
            xpr->stack[xpr->stackptr] = 1;
         } else {
            xpr->stack[xpr->stackptr] = 0;
         }
         break;
       case TOKEN_LESSTHANEQ:
         if (xpr->stack[xpr->stackptr] <= xpr->stack[oldptr]) {
            xpr->stack[xpr->stackptr] = 1;
         } else {
            xpr->stack[xpr->stackptr] = 0;
         }
         break;
       case TOKEN_GREATERTHANEQ:
         if (xpr->stack[xpr->stackptr] >= xpr->stack[oldptr]) {
            xpr->stack[xpr->stackptr] = 1;
         } else {
            xpr->stack[xpr->stackptr] = 0;
         }
         break;
      }
   }
}

/************************************************************************
 ***********************************************************************/
void do_logical_ands(EXPRESSION * xpr) {
   do_condition(xpr);
   while (xpr->token == TOKEN_AND) {
    int oldptr;
      scan(xpr);
      do_condition(xpr);
      oldptr = pop_stack(xpr);
      if (!(xpr->stack[xpr->stackptr] && xpr->stack[oldptr])) {
         xpr->stack[xpr->stackptr] = 0;
      }
   }
   return;
}

/************************************************************************
 ***********************************************************************/
void do_logical_ors(EXPRESSION * xpr) {
   do_logical_ands(xpr);
   while (xpr->token == TOKEN_OR) {
    int oldptr;
      scan(xpr);
      do_logical_ands(xpr);
      oldptr = pop_stack(xpr);
      if (!xpr->stack[xpr->stackptr]) {
         xpr->stack[xpr->stackptr] = xpr->stack[oldptr];
      }
   }
   return;
}

/************************************************************************
 * evaluate_expression()
 ***********************************************************************/
int evaluate_expression(char * expression) {
 EXPRESSION * xpr;
 int result = 0;
   xpr = (EXPRESSION *)malloc(sizeof(EXPRESSION));
   if (xpr) {
      memset(xpr, 0, sizeof(EXPRESSION));
      xpr->lastvar = -1;
      xpr->pos = expression;
      while (*xpr->pos) { /* process all ; delimited expressions */
         xpr->stackptr = 0;
         scan(xpr);
         do_logical_ors(xpr);
      }
      result = xpr->stack[1];
      free(xpr);
   }
   return result;
}

int main(int argc, char *argv[]) {
 int result;
   result = evaluate_expression(argv[1]);
   printf("[%s] = %d\n", argv[1], result);
   return 1;
}