//
// 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';
}