/* eval1.c (comment9.c) - Don Yang (uguu.org)
   Preprocess step 1: remove comments / debug output

   10/21/99
                                                                           */

#include<stdio.h>

#define isdigit0(x)     ((x) >= '0' && (x) <= '9')
#define isxdigit0(x)    (isdigit0(x) || ((x) >= 'a' && (x) <= 'f'))

#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

char expression[MAX_EXPRESSION_LENGTH + 1];
int expindex, lasttoken, nestlevel;

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;

int i;

long evaluate(int node, int level)
{
   long tmp;

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

      case OPERATOR_NEG:
         return -evaluate(right[node], level + 1);

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

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

      case OPERATOR_DIV:
         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:
         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:
         return evaluate(left[node], level + 1) + evaluate(right[node], level + 1);

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

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

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

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

      default:
         return operand[node];
   }

}

void insertbop(int op)
{
   printf("%c ", i);

   for(; operator[parent[cursor]] != OPERATOR_OPEN_PAREN &&
         (operator[parent[cursor]] & 7) >= (op & 7);
         cursor = parent[cursor]);

   operator[newnode] = op;

   left[newnode] = cursor;
   parent[newnode] = parent[cursor];
   parent[cursor] = newnode;
   right[parent[newnode]] = newnode;
   cursor = newnode;

   newnode++;
   lasttoken = TOKEN_OPERATOR;

}

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++;
   }

   operator[newnode] = op;
   operand[newnode] = lit;

   parent[newnode] = cursor;
   right[cursor] = newnode;
   cursor = newnode;

   newnode++;

}

int main(int argc, char *argv[])
{
   if( argc == 1 )
   {
      puts("arg: <expression>");
      return 0;
   }

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


   operator[cursor = 0] = OPERATOR_OPEN_PAREN;
   newnode = 1;


   for(expindex = lasttoken = nestlevel = 0; expression[expindex];)
   {
      if( isdigit0(expression[expindex]) )
      {
         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);

         for(; isxdigit0(expression[expindex]); expindex++);
      }
      else
      {
         i = expression[expindex++];
         if( lasttoken == TOKEN_LITERAL )
         {
            if( i == '(' )
            {
               i = '*';    insertbop(OPERATOR_MUL);
               i = '(';    insertuop(OPERATOR_OPEN_PAREN);
            }
            else if( i == ')' && nestlevel )
            {
               printf("\b) ");
               for(cursor = parent[cursor]; operator[cursor] != OPERATOR_OPEN_PAREN; cursor = parent[cursor]);
               nestlevel--;
            }
            else
            {
               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
         {
            if( i == '(' )       insertuop(OPERATOR_OPEN_PAREN);
            else if( i == '-' )  insertuop(OPERATOR_NEG);
            else if( i == '~' )  insertuop(OPERATOR_NOT);
         }
      }
   }

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


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

   return 0;

}