/* eval2.c (comment9.c) - Don Yang (uguu.org)
   Preprocess step 2: optimize code / evaluate macros

   10/21/99
                                                                           */

#include<stdio.h>

#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

long operand[MAX_TREE_SIZE], lit;
char expression[MAX_EXPRESSION_LENGTH + 1], *errtext = "\nbaka.";
int expindex, lasttoken, nestlevel,

    operator[MAX_TREE_SIZE],
    left[MAX_TREE_SIZE], right[MAX_TREE_SIZE], parent[MAX_TREE_SIZE],
    newnode, cursor,

    i;

long evaluate(int node)
{
   long tmp;

   switch( operator[node] )
   {
      case OPERATOR_OPEN_PAREN:
         return evaluate(right[node]);

      case OPERATOR_NEG:
         return -evaluate(right[node]);

      case OPERATOR_NOT:
         return ~evaluate(right[node]);

      case OPERATOR_MUL:
         return evaluate(left[node]) * evaluate(right[node]);

      case OPERATOR_DIV:
         if( (tmp = evaluate(right[node])) == 0 )
            return puts(errtext);
         return evaluate(left[node]) / tmp;

      case OPERATOR_MOD:
         if( (tmp = evaluate(right[node])) == 0 )
            return puts(errtext);
         return evaluate(left[node]) % tmp;

      case OPERATOR_ADD:
         return evaluate(left[node]) + evaluate(right[node]);

      case OPERATOR_SUB:
         return evaluate(left[node]) - evaluate(right[node]);

      case OPERATOR_AND:
         return evaluate(left[node]) & evaluate(right[node]);

      case OPERATOR_XOR:
         return evaluate(left[node]) ^ evaluate(right[node]);

      case OPERATOR_OR:
         return evaluate(left[node]) | evaluate(right[node]);

      default:
         return operand[node];
   }

}

void insertbop(int op)
{
   for(printf("%c ", i);
       operator[parent[cursor]] - OPERATOR_OPEN_PAREN &&
       (operator[parent[cursor]] & 7) >= (op & 7);
       cursor = parent[cursor]);

   operator[newnode] = op;

   parent[newnode] = parent[left[newnode] = cursor];
   right[parent[parent[cursor] = newnode]] = newnode;
   cursor = 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;

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

int main(int argc, char *argv[])
{
   if( argc == 1 )
      return puts(errtext);

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

   for(operator[expindex = lasttoken = nestlevel = cursor = expression[expindex] = 0] = OPERATOR_OPEN_PAREN;
       expression[expindex];)
      if( expression[expindex] >= '0' && expression[expindex] <= '9' )
      {
         if( expression[expindex + 1] == 'x' )
            sscanf(expression + (expindex += 2), "%lx", &lit);
         else
            sscanf(expression + expindex, "%ld", &lit);

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

         for(insertuop(OPERATOR_LITERAL);
             (expression[expindex] >= '0' && expression[expindex] <= '9') ||
             (expression[expindex] >= 'a' && expression[expindex] <= 'f');
             expindex++);
      }
      else
      {
         i = expression[expindex++];
         if( lasttoken )
         {
            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 )
   {
      lit = 0;
      insertuop(OPERATOR_LITERAL);
   }
   for(i = !putchar('\b'); i++ < nestlevel; putchar(')'));

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