//
// parser.cpp
//
//  The purpose of this program is to convert an equation or expression in standard
//algebraic form into Reversed Polish Notation RPN. Once in RPN, the expression is
//evaluated and can be reevaluated many times.
//
//  The software may freely be used. If you find any bugs, or have suggestions then email
//me at:   sdattalo@interstice.com
//
//  More information about the program may be found on my web page:
//
//  http://www.dattalo.com
//
// TSD  09JUL95  REV1 is Finally working
// TSD  06APR96  Added some comments and documentation 

// Known problems
//   1) There is no index out of range checks for any of the arrays. Probably should
//      encapsulate the indexing within a class.
//   2) There is no protection against math errors like division by zero.
//      I added a 'signal()' routine to catch Floating Point Errors, but nothing but exiting
//      the program is done.
//   3) The exponentiation operator '^' has the same priority as '*' and '/'. May not
//      be a problem.
//   4) Undefined varaibles are not flagged as such. Consequently, when the parser first
//      encounters a variable that has not been defined, it defines the variable and
//      initializes it to zero. Definitely a 'C' no-no.


//#include <assoc.h>
//#include <dict.h>
#include <iostream.h>
#include <string.h>
#include<ctype.h>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<signal.h>
#include "parser.h"

#define LF 0x0a

// Various trial cases. Note that some of these will cause floating point exceptions.
//This is no bug with the program; it's simply because some of the variables have not
//been defined.

static char fpin[] = "1+sin(-cos(1-(-2)))-3";
//char *fpin = "ln(2*x*cos(w * t + phi) / ( 7.2e-3 - 3*sqrt(4 * a *(c + 9.1e+7)) ) )";
//char *fpin = "cosh(2*x*cos(w * t + phi) + 5 / (1 + sqrt(4.9)))";
//char *fpin = "((-2/7)+(5)*1)";
//char *fpin = "cos(1)+(2*3)-(4)";
//char *fpin = "6-(1-2)/3*4+5";
//char *fpin = "log10(PI^2)";

int lines = 0, _index = 0;
char var[30],ch;

/*------------------------------------------------------------*/
//db_error
//
// This function is a make-shift error printer. Given an error number, it will
//initialize the global variable *str to point to some constant string that describes
//the error.
//
void db_error(int err_no)
{
  char *str;

  switch(err_no) {
    case 1:
      str = "Missing '{' after key word";
      break;

    case 2:
      str = "Illegal keyword";
      break;
    case 3:
      str = "Missing '}'";
      break;

    case 4:
      str = "Parenthesis mismatch";
      break;

    case 5:
      str = "Operator syntax";
      break;

    case 6:
      str = "Misplaced ')'";
      break;

    default:
      str = "Unknown";
  }
  printf("\nERROR: %d   Line # %d\n%s\n", err_no, lines, str);
  /*fclose(fpin);*/
  exit(1);
}
/*-----------------------------------------------*/
//my_getc
//
// This routine returns the next non-white space character in the input stream.
//Note that the global variable "index" keeps track of where we are in the stream.
//2nd Note, The stream for now is a string.
//
int my_getc(char *fpin)
{
char ch;

  while ( isspace(ch =fpin[_index]))   /* Remove any spaces */
    _index++;


  if (ch)  _index++;                   /* If not the end of line, advance index */

  return(ch);
}
/*-----------------------------------------------*/
//my_ungetc
//
void my_ungetc(char c, char *fpin)
{
  fpin[--_index] = c;
}

/*-----------------------------------------------*/
//comment
//
//Not used here. However, if you wish to parse a file with comments, then you can suit
//this function to your needs.
//
int comment(char c)
{

  if (c == '#') {
    while( (c = my_getc(fpin)) != '#' && c != 0) ;
    return c=='#';
  }

  return(0);
}
/*-----------------------------------------------*/
//skipbl
//
//Skipbl is an abbreviation for skip blanks. This function is primarily used with
//file inputs.
void skipbl(void)
{
  char ch;
  do 
    if ((ch= my_getc(fpin))==LF) lines++;
  while(isspace(ch) || comment(ch));
  my_ungetc(ch,fpin);
}
/*-----------------------------------------------*/
int is_letter( char c)
{
  c &= 0x5f;    /* convert lower case to upper case */
  return( (c>='A')  &&  (c<='Z') );
}

/*-----------------------------------------------*/
// Note that braces and brackets are equivalent. Consequently, something like
// (a+b] while looking stupid is o.k.
int is_openparen( char c)
{
  return( (c=='[') || (c=='(') );
}

/*-----------------------------------------------*/
int is_closedparen( char c)
{
  return( (c==']') || (c==')') );
}

/*-----------------------------------------------*/
int is_number( char c)
{
  return( ( (c>='0') && (c<='9') ) || (c=='.') );
}

/*------------------------------------------------------------*/
//read_substring
//
//  The purpose of this function is to read a string from fpin. A string
//in this case is defined to be same as a legal C name, i.e. the first character
//must be a letter, the remaining characters can be letters or numbers.
//  
void read_substring(char *variable)
{
  char ch;

  skipbl();
  ch=my_getc(fpin);
  if(is_letter(ch))                // The First character must be a letter
  {
    *variable++=ch;
    do {
      ch = my_getc(fpin);
      *variable++ = ch;            // The other characters can be alphanumeric
    } while(is_letter(ch)|| ( (ch>='0') && (ch<='9') ) );
  }
  my_ungetc(ch,fpin);
  *--variable = 0;

}
/*------------------------------------------------------------*/
void add_variable(token *new_variable)
{
  variable_list[number_of_variables++] = new_variable;
}
/*------------------------------------------------------------*/
// search_var_and_func
//
//  This function will take the input string "function" and see if it exists in either
//the function list or the variable list. If it is found in either one, then the pointer
//to the list element is returned. Otherwise, a new variable is created and added to the
//variable list.
token * search_var_and_func(char *function)
{
  int i;

  skipbl();

  for(i=0; i<number_of_functions; ++i)
  {
    if(strcmp(function_list[i]->nameOf(), function) == 0) return(function_list[i]);
  }

  for(i=0; i<number_of_variables; ++i)
    if(strcmp(variable_list[i]->nameOf(), function) == 0) return(variable_list[i]);

  variable *t = new variable(function);
  add_variable(t );
  return(t);

}

/*-----------------------------------------------*/
variable::variable(char * new_variable)
{
  value = 0;
  length = strlen(new_variable);
  name_ptr = new char [length];
  strcpy(name_ptr, new_variable);
  type = TT_operand;
}

/*-----------------------------------------------*/


FOP::FOP(char* string)
{

  char *end_ptr;

  end_ptr = NULL;
  if(*string)
  {
    t = strtod(&string[_index], &end_ptr);
    _index += (strlen (&string[_index]) - strlen(end_ptr));
  }
  else
    t=0.0;
  type = TT_operand;
}

/*-----------------------------------------------*/

class BOPL_plus : public BOPL
{
public:
  virtual void execute(void) { numeric_push(numeric_pop() + numeric_pop());}
  virtual char get_ASCII(void) const { return '+';}
};

class BOPL_minus : public BOPL
{
public:
  virtual void execute(void) { numeric_push(-numeric_pop() + numeric_pop());}
  virtual char get_ASCII(void) const { return '-';}
};

/*-----------------------------------------------*/
class BOPH_times : public BOPH
{
public:
  virtual void execute(void) { numeric_push(numeric_pop() * numeric_pop());}
  virtual char get_ASCII(void) const { return '*';}
};

class BOPH_divide : public BOPH
{
public:
  virtual void execute(void)
  { double t=numeric_pop();  numeric_push(numeric_pop() /t );}
  virtual char get_ASCII(void) const { return '/';}
};

class BOPH_exponentiate : public BOPH
{
public:
  virtual void execute(void)
  { double t=numeric_pop();  numeric_push(pow(numeric_pop(),t) );}
  virtual char get_ASCII(void) const { return '^';}
};

/*-----------------------------------------------*/
class UOP_minus : public UOP
{
public:
  virtual void execute(void) { numeric_push(-numeric_pop());}
  virtual char get_ASCII(void) const { return '-';}
};
/*-----------------------------------------------*/
//
// Trig Functions
//
class function_cos : public function
{
public:
  virtual void execute(void) { numeric_push(cos(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "cos";}
};

class function_sin : public function
{
public:
  virtual void execute(void) { numeric_push(sin(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "sin";}
};

class function_tan : public function
{
public:
  virtual void execute(void) { numeric_push(tan(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "tan";}
};

class function_sec : public function
{
public:
  virtual void execute(void) { numeric_push(1/cos(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "sec";}
};

class function_csc : public function
{
public:
  virtual void execute(void) { numeric_push(1/sin(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "csc";}
};

class function_cot : public function
{
public:
  virtual void execute(void) { numeric_push(1/tan(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "cot";}
};

/*-----------------------------------------------*/
//
// Inverse Trig Functions
//
class function_acos : public function
{
public:
  virtual void execute(void) { numeric_push(acos(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "acos";}
};

class function_asin : public function
{
public:
  virtual void execute(void) { numeric_push(asin(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "asin";}
};

class function_atan : public function
{
public:
  virtual void execute(void) { numeric_push(atan(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "atan";}
};

class function_asec : public function
{
public:
  virtual void execute(void) { numeric_push(acos(1/numeric_pop()));}
  virtual Pchar nameOf(void) const { return "asec";}
};

class function_acsc : public function
{
public:
  virtual void execute(void) { numeric_push(asin(1/numeric_pop()));}
  virtual Pchar nameOf(void) const { return "acsc";}
};

class function_acot : public function
{
public:
  virtual void execute(void) { numeric_push(3.141592653/2-atan(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "acot";}
};

/*-----------------------------------------------*/
class function_cosh : public function
{
public:
  virtual void execute(void) { numeric_push(cosh(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "cosh";}
};

class function_sinh : public function
{
public:
  virtual void execute(void) { numeric_push(sinh(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "sinh";}
};

class function_tanh : public function
{
public:
  virtual void execute(void) { numeric_push(tanh(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "tanh";}
};

class function_sech : public function
{
public:
  virtual void execute(void) { numeric_push(1/cosh(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "sech";}
};

class function_csch : public function
{
public:
  virtual void execute(void) { numeric_push(1/sinh(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "csch";}
};

class function_coth : public function
{
public:
  virtual void execute(void) { numeric_push(1/tanh(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "coth";}
};

class function_ln : public function
{
public:
  virtual void execute(void) { numeric_push(log(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "ln";}
};

class function_log : public function    // Identical to "ln"
{
public:
  virtual void execute(void) { numeric_push(log(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "log";}
};

class function_log10 : public function
{
public:
  virtual void execute(void) { numeric_push(log10(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "log10";}
};

class function_exp : public function
{
public:
  virtual void execute(void) { numeric_push(exp(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "exp";}
};


class function_sqrt : public function
{
public:
  virtual void execute(void) { numeric_push(sqrt(numeric_pop()));}
  virtual Pchar nameOf(void) const { return "sqrt";}
};

/*-----------------------------------------------*/
void tokenize(void)
{

int have_left_operand=0;

int temp;
  do
  {
    ch = my_getc(fpin);

    switch(ch)
    {
      case '+':
	if(have_left_operand)  the_array[token_index++] = new BOPL_plus();
	break;
      case '-':
	if(have_left_operand)
	  the_array[token_index++] = new BOPL_minus();
	else
	  the_array[token_index++] = new UOP_minus();
        break;

      case '(':
        level++;
        have_left_operand=0;
	the_array[token_index++] = new open_parenthesis('(');
	break;

      case ')':
        level--;
        have_left_operand=1;
	the_array[token_index++] = new closed_parenthesis(ch);
	break;

      case '*':
	the_array[token_index++] = new BOPH_times();   break;
      case '/':
	the_array[token_index++] = new BOPH_divide();   break;
      case '^':
        the_array[token_index++] = new BOPH_exponentiate(); break;
      case '%':
      case '&':

       //	the_array[token_index++] = new BOPH(ch);
        break;

      default:
        if(is_letter(ch))
        {
          have_left_operand =1;
          my_ungetc(ch, fpin);
	  read_substring(var);
	  the_array[token_index++] = search_var_and_func(var);
	}


       if( is_number(ch))
       {
         have_left_operand =1;
         my_ungetc(ch, fpin);
         the_array[token_index++] = new FOP(fpin);
       }


    }
  } while(ch);

  null_token *f = new null_token;
  the_array[token_index++] = f;

}

/*-----------------------------------------------*/
void push(int _index)
{
  the_stack[stack_index++] = the_array[_index];
}

/*-----------------------------------------------*/
PS_state parse(PS_state state)
{

  do
  {
    state = the_array[t1++]->a_search(state);
    // state=search(state);
  } while( (state!=PS_search_end)&&(state!=PS_search_closed));

  return(state);
}

void  init_function_list(void)
{
  number_of_functions = 0;

  function_list[number_of_functions++]= new function_cos();
  function_list[number_of_functions++]= new function_sin();
  function_list[number_of_functions++]= new function_tan();
  function_list[number_of_functions++]= new function_sec();
  function_list[number_of_functions++]= new function_csc();
  function_list[number_of_functions++]= new function_cot();
  function_list[number_of_functions++]= new function_acos();
  function_list[number_of_functions++]= new function_asin();
  function_list[number_of_functions++]= new function_atan();
  function_list[number_of_functions++]= new function_asec();
  function_list[number_of_functions++]= new function_acsc();
  function_list[number_of_functions++]= new function_acot();
  function_list[number_of_functions++]= new function_cosh();
  function_list[number_of_functions++]= new function_sinh();
  function_list[number_of_functions++]= new function_tanh();
  function_list[number_of_functions++]= new function_sech();
  function_list[number_of_functions++]= new function_csch();
  function_list[number_of_functions++]= new function_coth();
  function_list[number_of_functions++]= new function_exp();
  function_list[number_of_functions++]= new function_ln();
  function_list[number_of_functions++]= new function_log();
  function_list[number_of_functions++]= new function_log10();
  function_list[number_of_functions++]= new function_sqrt();
}
/*-----------------------------------------------*/
void init_variable_list(void)
{
  number_of_variables = 0;

  variable *v = new variable("ONE");
  v->value = 1;
  variable_list[number_of_variables++] = v;

  v = new variable("ZERO");
  v->value = 0;
  variable_list[number_of_variables++] = v;

  v = new variable("PI");
  v->value = 3.141592653;
  variable_list[number_of_variables++] = v;

}

typedef void (*fptr)(int);

void Catcher(int *reglist)
{

  cout << "Floating Point Error";
  exit(1);
}

/*-----------------------------------------------*/
void main(void)
{
  int i;

  signal(SIGFPE,  (fptr)Catcher );       //Define catcher for floating point errors.

  init_function_list();                  //Initialize the user defineable function list
  init_variable_list();                  //    "            "      "      variable list                                                                 

  printf("\n%s\n", fpin);                //
  tokenize();
  if(level) db_error(4);

  for( i=0; i<token_index; i++)
    the_array[i]->printOn();
  cout << "\nParsed Results\n";
  t1=0;

  parse(PS_null);

  cout << '\n';
  for(i=0; i<stack_index; i++)
  {
    the_stack[i]->printOn();
    cout << ' ';
  }
  if(level) db_error(4);

  for(i=0; i<stack_index; i++)
  {
    the_stack[i]->execute();
  }

  cout << '\n' << numeric_stack[0] << '\n';

}