#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <signal.h>

#define True 1
#define False 0
#define MaxParam 150

char gError;

//The dynamic data structure
struct Nums{
	double Num;
	Nums *Next;
};
Nums *Head;     //Pointer to the first element in the dynamic data structure

//A routine that handles mathematical errors
int matherr(struct exception *a){
	gError = True;
	a->retval = 0.0;
	return 1;
}

//A routine that handles division by zero
void Trap(int sType){
	gError = True;
	signal(SIGFPE, Trap);
}

//Main interpreter
double Interpret (char *Formula){
	register int i;             //Counter
	register char Orden = 0;    //Parentheses level
	double Type1;               //The number being handled (converted from string)
	Nums *Numbers = Head;

	struct{
		double Sum;
		double Overfac;
		double Exp2;
	}Level[MaxParam];

	signal(SIGFPE,Trap);    //Install div/0 error handler

	//Initialize
	Level[0].Overfac = 1.0;
	Level[0].Exp2 = Level[0].Sum = 0.0;


	//Mail loop (the string is being prosessed from the end)
	for(i=strlen(Formula)-1; i>=0; i--){

		//Find which operation to perform
		switch(Formula[i]){
			//Retrieve numbers from the dynamic data structure
			case '#':
				Type1 = Numbers->Num;
				Numbers = Numbers->Next;
				break;

			case '*':
				Level[Orden].Overfac *= pow(Type1, Level[Orden].Exp2 + 1.0);
				Type1 = Level[Orden].Exp2 = 0.0;
				break;

			case '/':
				Level[Orden].Overfac /= pow(Type1, Level[Orden].Exp2 + 1.0);
				Type1 = Level[Orden].Exp2 = 0.0;
				break;

			case '+':
				Level[Orden].Sum += pow(Type1, Level[Orden].Exp2 + 1.0) * Level[Orden].Overfac;
				Level[Orden].Overfac = 1.0;
				Type1 = Level[Orden].Exp2 = 0.0;
				break;

			case '-':
				if((Formula[i-1] != 'E') || (i == 0)){
					Level[Orden].Sum -= pow(Type1, Level[Orden].Exp2 + 1.0) * Level[Orden].Overfac;
					Level[Orden].Overfac = 1.0;
					Type1 = Level[Orden].Exp2 = 0.0;
				}
				break;

			//Return to previous level
			case '(':
				Type1 = Level[Orden--].Sum + pow(Type1, Level[Orden].Exp2 + 1.0) * Level[Orden].Overfac;
				break;

			//Jump to next level (the string is being prosessed from the end)
			case ')':
				Level[++Orden].Overfac = 1.0;
				Level[Orden].Exp2 = Level[Orden].Sum = 0.0;
				break;

			case '^':
				Level[Orden].Exp2 = Type1 - 1.0;
				Type1 = 0.0;
				break;

			case 'e':
				Type1 = exp(Type1);
				break;

			case 'C':
			case 'c':
				Type1 = cos(Type1);
				break;

			case 'S':
			case 's':
				Type1 = sin(Type1);
				break;

			case 'T':
			case 't':
				Type1 = tan(Type1);
				break;

			case 'N':
			case 'n':
				Type1 = atan(Type1);
				break;

			case 'L':
			case 'l':
				Type1 = log(Type1);
				break;

			case 'A':
			case 'a':
				Type1 = abs(Type1);
				break;

			case 'R':
			case 'r':
				Type1 = sqrt(Type1);
				break;

			case 'P':
			case 'p':
				Type1 = M_PI;
				break;
		}
	}


	//The final calculation
	Level[0].Sum += pow(Type1, (Level[0].Exp2 + 1.0)) * Level[0].Overfac;

	//If any kind of error occured during calculation, return 0
	if(gError != 0) Level[0].Sum=0.0;

	return(Level[0].Sum);
} /* Interpret */


int ParseExp(char *Expr){
	// Expression verifyer - Checks the expression before passing it to Interpret(char *Formula)

	int i = 0, a = 0;                   //Counters
	char *Str = new char[strlen(Expr)]; //Copy of Expr
	char *InStr, *Temp;                 //Pointers to SubStrings
	char f;                             //Var for last character
	int ParCount = 0;                   //Parenthesis counter

	char *Find[] = {"sin", "cos", "tan", "atan", "atn", "exp", "abs", "sqrt", "sqr", "pi", "log", " ", "(#)"};
	char *Repl[] = {"s", "c", "t", "n", "n", "e", "a", "r", "r", "p", "l", "", "#"};

	//Replace each number with #, and store numbers into a dynamic data structure
	int Empty;
	int NumLen = 0;
	char Tmp;
	Nums *Numbers = new Nums;

	Numbers->Next = NULL;
	Head = Numbers;

	for(i=strlen(Expr)-1; i>=0; i--){
		Empty=True;
		//Find the length of a number to work on
		if(((Expr[i] >= '0') && (Expr[i] <= '9')) || (Expr[i] == '.') || (Expr[i] == 'E') || ((Expr[i] == '-') && (Expr[i-1] == 'E') && (i > 0))){
			NumLen++;
			Empty = False;          //The number has not yet been found
		}

		//if the number is found, convert it to double and store in Type1
		//The algorithm works directly on the main string (Formula[])
		if(Empty && (NumLen > 0)){
			Tmp = Expr[i+ ++NumLen];    //Save a letter from the string
			Expr[i + NumLen] = '\0';    //Set temporary end marker
			Numbers->Num = strtod(&Expr[i + 1], NULL);  //Convert
			Expr[i + NumLen] = Tmp;     //Restore the string

			Expr[i+1] = '#';
			strcpy(&Expr[i+2], &Expr[i + NumLen]);

			Numbers->Next = new Nums;
			Numbers = Numbers->Next;
			Numbers->Next = NULL;

			NumLen = 0;                 //Ready to read next number
		}
	}

	//Work with the last number
	if(!Empty){
		Tmp = Expr[i+ ++NumLen];        //Save a letter from the string
		Expr[i + NumLen] = '\0';        //Set temporary end marker
		Numbers->Num = strtod(&Expr[i + 1], NULL);  //Convert
		Numbers->Next = NULL;
		Expr[i + NumLen] = Tmp;         //Restore the string

		Expr[i+1] = '#';
		strcpy(&Expr[i+2], &Expr[i + NumLen]);
	}


	//Copy to Str and convert to lower case for comparasion
	strcpy(Str, Expr);
	strlwr(Str);

	//Compare
	for(i=0; i<=12; i++){
		//Find Find[i] inside Str
		InStr = strstr(Str, Find[i]);
		if(InStr != NULL){ //if found . . .
			//Update 'lowercased' Str
			strcpy(InStr, Repl[i]);
			strcpy(InStr + strlen(Repl[i]), InStr + strlen(Find[i]));

			//Find offset, where the change would take place
			a = 0;
			for(Temp = InStr; Temp > Str; Temp--, a++); //a will contain InStr's offset

			//Redirect InStr to work on original Expr string
			InStr = &Expr[a];

			//Update original Expr
			strcpy(InStr, Repl[i]);
			strcpy(InStr + strlen(Repl[i]), InStr + strlen(Find[i]));
			i--;       //A case of Find[i] has been found - try another search until no more cases found
		}
	}

	//Check if the amount of opening and closing parenthesis coinside . . .
	for(i=0; i<=strlen(Expr); i++){
		if(Expr[i] == '(') ParCount++;
		if(Expr[i] == ')') ParCount--;
	}

	// . . . If not, abort calculation
	if(ParCount != 0){
		strcpy(Expr, "Parenthesis count mismatch!\0");
		return 0;
	}

	//Check the last symbol in the expression
	f = Expr[strlen(Expr)-1];
	if((f == '#') || (f == 'p') || (f == ')')) {}
	else{
		strcpy(Expr, "Last symbol in the expression is illigal!\0");
		return 0;
	}

	return 1;

} /* ParseExp */

void DestroyNums(void){
	Nums *Numbers;

	//Destroy the dynamic data structure
	Numbers = Head;
	while(Numbers->Next != NULL){
		Head = Numbers->Next;
		delete Numbers;
		Numbers = Head;
	}
	delete Head;
} /* DestroyMuns */

void main(int argc, char *argv[]){
	double x;
	char *t = new char[255];

	//Read parameters
	if(argv[1] != NULL){
		strcpy(t, argv[1]);

		printf("%s",t);
		if(!ParseExp(t)){
			printf(" = %s\n",t);
			return;
		}
		x = Interpret(t);
		if (!gError)
			printf(" = %18.18g\n",x);
		else
			printf(" = Illigal operation!\n");

		DestroyNums();
	}else{
		printf("\nEnter an arithmetic expression (empty line terminates, ? = help)\n");
		do{
			printf("->");
			t[0] = 255;
			cgets(t);

			if(t[1] == '\0') break; //while

			if(t[2] == '?'){
				printf("\nThe following trigonometric and math. functions are supported:\n");
				printf("  SIN or S - sine, COS or C - cosine, TAN or T - tangent, ANAT, ATN or N -\n");
				printf("  arc tangent, SQRT, SQR or R - Root, LOG or L - nLogarithm,\n");
				printf("  EXP or e - exponent, ABS or A - absolute, PI or P - number pi.\n");

				printf("\nYou can use up to 150 nested parenthesis. Unrecognised characters and spaces\n");
				printf("will be ignored. Negative numbers should be entered in parenthesis: (-85)\n");

				printf("\n  Example: S5+(4*7E-4)-T(6^2) = SIN(5) + (4 * 0.0007) - TAN(6 ^ 2)\n");

				printf("\nNumbers in scientific format are entered in the following fashion (the\n");
				printf("algorithm is case sensitive):\n");
				printf("  [+/-]12345E[+/-]123  |  (-0.007) = (-7E-3)  |  7000000 = 7E6\n");

				printf("\nTrigonometric functions use radians. To convert degrees to radians,\n");
				printf("multiply the degrees by PI/180. To convert from radians to degrees,\n");
				printf("multiply the radians by 180/PI\n");

				printf("\n  Algorithm by Steinar Foss.\n");
				printf("  Converted to C++ and optimized by Stanislav Sokolov.\n");

				printf("\nEnter an arithmetic expression (empty line terminates, ? = help)\n");
			}else{
				if(!ParseExp(&t[2])){
					printf(" = %s\n",&t[2]);
				}else{
					x = Interpret(&t[2]);
					if (!gError)
						printf(" = %18.18g\n",x);
					else{
						printf(" = Illigal operation!\n");
						gError = False;
					}
				} /* if ParseExp */

				DestroyNums();
			} /* if == ? */
		}while (1 == 1);  //Always true, loop until break; after empty line entered!
	}/* if argv[1] != null */
	delete [] t;
} /* Main */