/* eval.c (comment9.c) - Don Yang (uguu.org)
   Original source

   eval is a command line integer expression evaluator.

   Usage:
      Input literals may be decimal, or hexadecimal prefixed with "0x".
      Input must be in entirely lowercase ASCII.
      WinNT4 / UNIX users may need to enclose expression in quotes.

   Operator precedence (top executed first):
      Level 7: ( ) literals
      Level 6: - ~ (unary)
      Level 5: * / %
      Level 4: + - (binary)
      Level 3: &
      Level 2: ^
      Level 1: |

   Compiles and runs with:
      MSVC++ 6.0
      MSC 6.0
      TC++ 3.0
      DJGPP 2.8.1
      gcc 2.8.0 (HPUX)
      gcc 2.8.1 (Sun Solaris)
      (other compilers should work as well)

   Notes:
      The expression printed by eval is the one being evaluated, which may
      not always be same as the one on the command line.

      For some expressions, if you feed them to a C compiler, the resulting
      answer is different from the one calculated by eval.  In most cases,
      eval is correct -- Most compilers shuffle constant expressions and thus
      result in different values.  I hand checked many eval's output, and
      all seem correct to me.

      If result overflows or divide by zero occurs, the output value will
      depend on the compiler used and the compile time options.  All
      compilers I used (listed above) result in their own different unique
      set of values when overflowed :P   eval does not check for overflows so
      you will just have to be careful...

   10/20/99: main
             insertlit
             insertuop
             evaluate
             insertbop
   10/21/99: removed string.h
             removed stdin support (not compatible in UNIX)
             removed insertlit
             fixed double parenthesis problem
   10/22/99: multiple divides bug
                                                                           */

/* Includes */
#include<stdio.h>

/* Macros (ctype.h replacements) */
#define isdigit0(x)     ((x) >= '0' && (x) <= '9')
#define isxdigit0(x)    (isdigit0(x) || ((x) >= 'a' && (x) <= 'f'))

/* Constants */
#define MAX_EXPRESSION_LENGTH    1024
#define MAX_TREE_SIZE            1024

#define TOKEN_OPERATOR           0
#define TOKEN_LITERAL            1

#define OPERATOR_LITERAL         0xc7
#define OPERATOR_OPEN_PAREN      0xb7
#define OPERATOR_NEG             0xa6
#define OPERATOR_NOT             0x96
#define OPERATOR_MUL             0x85
#define OPERATOR_DIV             0x75
#define OPERATOR_MOD             0x65
#define OPERATOR_ADD             0x54
#define OPERATOR_SUB             0x44
#define OPERATOR_AND             0x33
#define OPERATOR_XOR             0x22
#define OPERATOR_OR              0x11

/* Expression string */
char expression[MAX_EXPRESSION_LENGTH + 1];
int expindex, lasttoken, nestlevel;

/* Expression tree */
long operand[MAX_TREE_SIZE], lit;
int operator[MAX_TREE_SIZE];
int left[MAX_TREE_SIZE], right[MAX_TREE_SIZE], parent[MAX_TREE_SIZE];
int newnode, cursor;

/* General globals */
int i;

/****************************************************************** evaluate
   Evaluate expression tree.                                               */
long evaluate(int node, int level)
{
   long tmp;

   for(i = 0; i < level; i++)
      printf(".  ");

   switch( operator[node] )
   {
      case OPERATOR_OPEN_PAREN:
         printf("(\n");
         return evaluate(right[node], level + 1);

      case OPERATOR_NEG:
         printf("- (unary)\n");
         return -evaluate(right[node], level + 1);

      case OPERATOR_NOT:
         printf("~\n");
         return ~evaluate(right[node], level + 1);

      case OPERATOR_MUL:
         printf("*\n");
         return evaluate(left[node], level + 1) * evaluate(right[node], level + 1);

      case OPERATOR_DIV:
         printf("/ (reverse order)\n");
         if( (tmp = evaluate(right[node], level + 1)) == 0 )
         {
            printf("divide by zero\n");
            return 0;
         }
         return evaluate(left[node], level + 1) / tmp;

      case OPERATOR_MOD:
         printf("%% (reverse order)\n");
         if( (tmp = evaluate(right[node], level + 1)) == 0 )
         {
            printf("divide by zero\n");
            return 0;
         }
         return evaluate(left[node], level + 1) % tmp;

      case OPERATOR_ADD:
         printf("+\n");
         return evaluate(left[node], level + 1) + evaluate(right[node], level + 1);

      case OPERATOR_SUB:
         printf("-\n");
         return evaluate(left[node], level + 1) - evaluate(right[node], level + 1);

      case OPERATOR_AND:
         printf("&\n");
         return evaluate(left[node], level + 1) & evaluate(right[node], level + 1);

      case OPERATOR_XOR:
         printf("^\n");
         return evaluate(left[node], level + 1) ^ evaluate(right[node], level + 1);

      case OPERATOR_OR:
         printf("|\n");
         return evaluate(left[node], level + 1) | evaluate(right[node], level + 1);

      default:
         /* Unrecognized operator, must be literal */
         printf("%ld\n", operand[node]);
         return operand[node];
   }

} /* evaluate() */

/***************************************************************** insertbop
   Insert binary operator to expression tree.                              *
                                                                           *
     operator                  operator (parent)                           *
         \                        \                                        *
         ...              ->      ...                                      *
           \                        \                                      *
         literal (cursor)       new operator (cursor)                      *
                                  /     \                                  *
                                ...      \                                 *
                                /         \                                *
                             literal     empty (next literal)              */
void insertbop(int op)
{
   printf("%c ", i);

   /* Find position to insert (after/above operators of higher precedence) */
   for(; operator[parent[cursor]] != OPERATOR_OPEN_PAREN &&
         (operator[parent[cursor]] & 7) >= (op & 7);
         cursor = parent[cursor]);

   /* Set data */
   operator[newnode] = op;

   /* Set links */
   left[newnode] = cursor;             /* newnode->left = cursor */
   parent[newnode] = parent[cursor];   /* newnode->parent = cursor->parent */
   parent[cursor] = newnode;           /* cursor->parent = newnode */
   right[parent[newnode]] = newnode;   /* newnode->parent->right = newnode */
   cursor = newnode;

   newnode++;
   lasttoken = TOKEN_OPERATOR;

} /* insertbop() */

/***************************************************************** insertuop
   Insert unary operator or literal to expression tree.                    *
                                                                           *
   operator (cursor)          operator (parent)                            *
        \                            \                                     *
         \               ->           \                                    *
          \                            \                                   *
         empty                   literal/operator (cursor)                 *
                                         \                                 *
                                          \                                *
                                           \                               *
                                          empty (next literal)             */
void insertuop(int op)
{
   if( op == OPERATOR_LITERAL )
   {
      printf("%ld ", lit);
      lasttoken = TOKEN_LITERAL;
   }
   else
   {
      putchar(i);
      lasttoken = TOKEN_OPERATOR;
      if( op == OPERATOR_OPEN_PAREN )
         nestlevel++;
   }

   /* Set data */
   operator[newnode] = op;
   operand[newnode] = lit;

   /* Set links */
   parent[newnode] = cursor;  /* newnode->parent = cursor */
   right[cursor] = newnode;   /* newnode->parent->right = newnode */
   cursor = newnode;

   newnode++;

} /* insertuop() */

/********************************************************************** main
   Build/parse expression string, build/evaluate expression tree.          */
int main(int argc, char *argv[])
{
   if( argc == 1 )
   {
      puts("Usage: eval <expression>");
      return 0;
   }

   /* Get expression string */
   expindex = 0;
   for(cursor = 1; cursor < argc; cursor++)
   {
      for(i = 0; argv[cursor][i];)
         expression[expindex++] = argv[cursor][i++];
   }
   expression[expindex] = 0;


   /* Reset expression tree */
   operator[cursor = 0] = OPERATOR_OPEN_PAREN;
   newnode = 1;


   /* Parse / evaluate expression (until NULL terminator reached) */
   for(expindex = lasttoken = nestlevel = 0; expression[expindex];)
   {
      if( isdigit0(expression[expindex]) )
      {
         /** Integer literal **/

         /* Load literal */
         if( expression[expindex + 1] == 'x' )
            sscanf(expression + (expindex += 2), "%lx", &lit);
         else
            sscanf(expression + expindex, "%ld", &lit);

         if( lasttoken == TOKEN_LITERAL )
         {
            i = '*';
            insertbop(OPERATOR_MUL);
         }
         insertuop(OPERATOR_LITERAL);

         /* Increment read pointer */
         for(; isxdigit0(expression[expindex]); expindex++);
      }
      else
      {
         /** Operators **/

         i = expression[expindex++];
         if( lasttoken == TOKEN_LITERAL )
         {
            if( i == '(' )
            {
               /* Open parenthesis (implied multiply) */
               i = '*';    insertbop(OPERATOR_MUL);
               i = '(';    insertuop(OPERATOR_OPEN_PAREN);
            }
            else if( i == ')' && nestlevel )
            {
               /* Close parenthesis */
               printf("\b) ");
               for(cursor = parent[cursor]; operator[cursor] != OPERATOR_OPEN_PAREN; cursor = parent[cursor]);
               nestlevel--;
            }
            else
            {
               /* Binary operators */
               if( i == '*' )       insertbop(OPERATOR_MUL);
               else if( i == '/' )  insertbop(OPERATOR_DIV);
               else if( i == '%' )  insertbop(OPERATOR_MOD);
               else if( i == '+' )  insertbop(OPERATOR_ADD);
               else if( i == '-' )  insertbop(OPERATOR_SUB);
               else if( i == '&' )  insertbop(OPERATOR_AND);
               else if( i == '^' )  insertbop(OPERATOR_XOR);
               else if( i == '|' )  insertbop(OPERATOR_OR);
            }
         }
         else
         {
            /* Unary operators */
            if( i == '(' )       insertuop(OPERATOR_OPEN_PAREN);
            else if( i == '-' )  insertuop(OPERATOR_NEG);
            else if( i == '~' )  insertuop(OPERATOR_NOT);
         }
      }
   }

   /* Complete expression tree */
   if( lasttoken == TOKEN_OPERATOR )
   {
      lit = 0;
      insertuop(OPERATOR_LITERAL);
   }
   for(i = !putchar('\b'); i < nestlevel; i++)
      putchar(')');


   /* Evaluate expression */
   putchar('\n');
   lit = evaluate(0, 0);
   printf("\n= %ld (0x%lx)\n", lit, lit);

   return 0;

} /* main() */