/* evalf.c (yukino.c) - Don Yang (uguu.org)
   Original source

   eval is a command line integer expression evaluator.

   Usage:
      Input literals are real floating point numbers of double precision.
      WinNT4 / UNIX users may need to enclose expression in quotes.

   Operator precedence (top executed first):
      Level 6: ( ) pi e literals
      Level 5: ^
      Level 4: sin cos tan asin acos atan ln log exp
      Level 3: - (unary)
      Level 2: * / %
      Level 1: + - (binary)

   Compiles and runs with:
      MSC 6.0
      MSVC++ 6.0
      TC 3.0
      DJGPP 2.8.1

   Notes:
      Order of operation may not be obvious with transcendental operators.
      For clarity, please group operations with parenthesis (since this
      program will not insert them for you).

   11/05/99
                                                                           */

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

/* Macros */
#define isdigit0(x)              (((x) >= '0' && (x) <= '9') || (x) == '.')

/* Constants */
#define MAX_EXPRESSION_LENGTH    2048
#define MAX_TREE_SIZE            2048

#define TOKEN_OPERATOR           0
#define TOKEN_LITERAL            1

#define OPERATOR_LITERAL         0x136
#define OPERATOR_PI              0x126
#define OPERATOR_E               0x116
#define OPERATOR_OPEN_PAREN      0x106
#define OPERATOR_POW             0x0f5
#define OPERATOR_SIN             0x0e4
#define OPERATOR_COS             0x0d4
#define OPERATOR_TAN             0x0c4
#define OPERATOR_ASIN            0x0b4
#define OPERATOR_ACOS            0x0a4
#define OPERATOR_ATAN            0x094
#define OPERATOR_LOG             0x084
#define OPERATOR_LN              0x074
#define OPERATOR_EXP             0x064
#define OPERATOR_NEG             0x053
#define OPERATOR_MUL             0x042
#define OPERATOR_DIV             0x032
#define OPERATOR_MOD             0x022
#define OPERATOR_ADD             0x011
#define OPERATOR_SUB             0x001

#define LABEL_SIN                (OPERATOR_SIN >> 4)
#define LABEL_COS                (OPERATOR_COS >> 4)
#define LABEL_TAN                (OPERATOR_TAN >> 4)
#define LABEL_LOG                (OPERATOR_LOG >> 4)
#define LABEL_EXP                (OPERATOR_EXP >> 4)

/* Operator names */
char *label[19] = {
   "-", "+", "%", "/", "*", "-", "exp", "ln", "log",
   "atan", "acos", "asin", "tan", "cos", "sin", "^", "(", "e", "PI"};

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

/* Expression tree */
double 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.                                               */
double evaluate(int node, int level)
{
   for(i = 0; i < level; i++)
      printf(".  ");

   switch( operator[node] )
   {
      case OPERATOR_PI:
         printf("atan2(0, -1)\n");
         return atan2(0, -1);
      case OPERATOR_E:
         printf("exp(1)\n");
         return exp(1);
      case OPERATOR_OPEN_PAREN:
         printf("(\n");
         return evaluate(right[node], level + 1);
      case OPERATOR_POW:
         printf("^ (reverse order)\n");
         return pow(evaluate(left[node], level + 1), evaluate(right[node], level + 1));
      case OPERATOR_SIN:
         printf("sin\n");
         return sin(evaluate(right[node], level + 1));
      case OPERATOR_COS:
         printf("cos\n");
         return cos(evaluate(right[node], level + 1));
      case OPERATOR_TAN:
         printf("tan\n");
         return tan(evaluate(right[node], level + 1));
      case OPERATOR_ASIN:
         printf("arcsin\n");
         return asin(evaluate(right[node], level + 1));
      case OPERATOR_ACOS:
         printf("arccos\n");
         return acos(evaluate(right[node], level + 1));
      case OPERATOR_ATAN:
         printf("arctan\n");
         return atan(evaluate(right[node], level + 1));
      case OPERATOR_LOG:
         printf("log\n");
         return log10(evaluate(right[node], level + 1));
      case OPERATOR_LN:
         printf("ln\n");
         return log(evaluate(right[node], level + 1));
      case OPERATOR_EXP:
         printf("exp\n");
         return exp(evaluate(right[node], level + 1));
      case OPERATOR_NEG:
         printf("- (unary)\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("/\n");
         return evaluate(left[node], level + 1) / evaluate(right[node], level + 1);
      case OPERATOR_MOD:
         printf("%% (reverse order)\n");
         return fmod(evaluate(left[node], level + 1), evaluate(right[node], level + 1));
      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);
      default:
         /* Unrecognized operator, must be literal */
         printf("%lf\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("%s ", label[op >> 4]);

   /* 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;
   lastop = 0;

} /* 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( lasttoken == TOKEN_LITERAL )
      insertbop(OPERATOR_MUL);
   if( op == OPERATOR_LITERAL )
   {
      printf("%lG ", lit);
      lasttoken = TOKEN_LITERAL;
   }
   else if( op == OPERATOR_PI || op == OPERATOR_E )
   {
      printf("%s ", label[op >> 4]);
      lasttoken = TOKEN_LITERAL;
   }
   else
   {
      if( op == OPERATOR_OPEN_PAREN )
      {
         nestlevel++;
         if( lastop )
            putchar('\b');
      }
      printf("%s", label[op >> 4]);
      lasttoken = TOKEN_OPERATOR;
   }
   lastop = 0;
   if( op >= OPERATOR_EXP && op <= OPERATOR_SIN )
   {
      putchar(' ');
      lastop = 1;
   }

   /* 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: evalf <expression>");
      return 0;
   }

   /* Get expression string */
   expindex = 0;
   strcpy(expression, argv[1]);
   for(i = 2; i < argc; i++)
      strcat(expression, argv[i]);
   strlwr(expression);


   /* 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 */
         sscanf(expression + expindex, "%lf", &lit);

         insertuop(OPERATOR_LITERAL);

         /* Increment read pointer */
         for(; isdigit0(expression[expindex]); expindex++);
         if( expression[expindex] == 'e' )
         {
            if( expression[expindex + 1] == '+' || expression[expindex + 1] == '-' )
               expindex++;

            for(expindex++;
                expression[expindex] >= '0' && expression[expindex] <= '9';
                expindex++);
         }
      }
      else if( expression[expindex] > 'a' && expression[expindex] <= 't' )
      {
         /** Transcendental functions **/

         if( !memcmp(expression + expindex, label[LABEL_SIN], 3) )      insertuop(OPERATOR_SIN);
         else if( !memcmp(expression + expindex, label[LABEL_COS], 3) ) insertuop(OPERATOR_COS);
         else if( !memcmp(expression + expindex, label[LABEL_TAN], 3) ) insertuop(OPERATOR_TAN);
         else if( !memcmp(expression + expindex, label[LABEL_EXP], 3) ) insertuop(OPERATOR_EXP);
         else if( !memcmp(expression + expindex, label[LABEL_LOG], 3) ) insertuop(OPERATOR_LOG);
         else
         {
            if( !memcmp(expression + expindex, "pi", 2) )      insertuop(OPERATOR_PI);
            else if( !memcmp(expression + expindex, "ln", 2) ) insertuop(OPERATOR_LN);
            else
            {
               if( expression[expindex] == 'e' )
                  insertuop(OPERATOR_E);
               expindex--;
            }
            expindex--;
         }
         expindex += 3;
      }
      else if( expression[expindex] == 'a' )
      {
         /** Inverse functions **/

         if( !memcmp(expression + expindex + 1, label[LABEL_SIN], 3) )        insertuop(OPERATOR_ASIN);
         else if( !memcmp(expression + expindex + 1, label[LABEL_COS], 3) )   insertuop(OPERATOR_ACOS);
         else if( !memcmp(expression + expindex + 1, label[LABEL_TAN], 3) )   insertuop(OPERATOR_ATAN);
         else expindex -= 3;
         expindex += 4;
      }
      else
      {
         /** Operators **/

         i = expression[expindex++];
         if( lasttoken == TOKEN_LITERAL )
         {
            if( i == '(' )
            {
               /* Open parenthesis (implied multiply) */
               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_POW);
            }
         }
         else
         {
            /* Unary operators */
            if( i == '(' )       insertuop(OPERATOR_OPEN_PAREN);
            else if( i == '-' )  insertuop(OPERATOR_NEG);
         }
      }
   }

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


   /* Evaluate expression */
   putchar('\n');
   printf("\n= %.16lG\n", evaluate(0, 0));

   return 0;

} /* main() */