/*
 * Written by nitrous <nitrous .at. vulnfact .dot. com>
 * 21/Feb/2oo6
 *
 * EVALUADOR DE EXPRESIONES
 * 1.-argv[1] pasa a lexico() y si en este encuentra un error... exit().
 * 2.-Las estructuras de posfijo pasan a ser evaluadas.
 * 3.-Se imprime el resultado.
 *
 * *NIX: $gcc expr_eval.c -o expr_eval -lm
 * 
*/

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
#include<errno.h>
#include<math.h>

#define ESTADOS 21	/* estados en el automata */
#define CODIGOS 16	/* diferentes codigos de entrada */
#define VAL_LEN	16	/* maxima longitud de valor de un token (numero de VAL_LEN digitos) */
#define NTOKENS 30	/* maximo de tokens a poder analizar */

struct token{
	/* El tipo del token, 'D'=Decimales; 'F'=Flotantes; 'E'=Exponencial y los demas son entendibles */
	unsigned char tipo;
	/* Si el tipo es 'D' o 'F' o 'E', aqui va el numero en si */
	char valor[VAL_LEN];
};

struct pila_token{
	struct token pila[NTOKENS];
	int tope;
};

struct pila_float{
	float pila[NTOKENS];
	int tope;
};

unsigned char valtoken[VAL_LEN]; /* Se usa para ir recopilando un numero mientras se va analizando */
unsigned int val_index; /* es el indice actual del arreglo de caracteres 'valtoken' */
unsigned int tokens_totales = 0; /* el numero de tokens que hay en una expresion, actualizada por la funcion get_tokens() */

/******* PROTOTIPOS DE FUNCIONES *******/
void get_tokens(char *, struct token *);
int filtro(int, unsigned char);
int lexico();
void posfija(struct token *, struct token *);
float evaluacion(struct token *);
void iniciar_pila_token(struct pila_token *);
void meter_pila_token(struct pila_token *, struct token);
struct token sacar_pila_token(struct pila_token *);
int pila_vacia_token(struct pila_token *);
void iniciar_pila_float(struct pila_float *);
void meter_pila_float(struct pila_float *, float);
float sacar_pila_float(struct pila_float *);
int asignar_prioridad(unsigned char);
/******* PROTOTIPOS DE FUNCIONES *******/

int main(int argc, char **argv)
{
	struct token *tokens, *tokens_posfija;
	tokens = (struct token *) malloc(sizeof(struct token) * NTOKENS);
	tokens_posfija = (struct token *) malloc(sizeof(struct token) * NTOKENS);
	int k = 0;

	if(argc != 2){
		fprintf(stderr, "Uso: %s <expresion>\n", argv[0]);
		return -1;
	}

	/* Se llena la variable tokens que es un apuntador a estructuras de tipo 'struct token'
	 * el cual contiene 'tokens_totales' elementos y cada uno con su correspondiente tipo
	 * y valor. La cadena de entrada se da como primer argumento, y si algo falla en el
	 * proceso de lexico el programa saldra inmediatamente */
	get_tokens(argv[1], tokens);

	/* Llena la variable 'tokens_posfija' que es un apuntador a estructuras de tipo 'struct token'
	 * la cual esta ordenada por el metodo de 'posfijo' */
	posfija(tokens, tokens_posfija);

	/* Impresion en pantalla de la cadena posfija */
	printf("POSFIJA:\t");
	while(tokens_posfija[k].tipo != '0'){
		switch(tokens_posfija[k].tipo){
			case 'D':
			case 'F':
			case 'E':
				printf("%s,", tokens_posfija[k].valor);
				break;
			case '<':
				printf("<<,");
				break;
			case '>':
				printf(">>,");
				break;
			default:
				printf("%c,", tokens_posfija[k].tipo);
		}
		k++;
	}

	printf("\n\nEVALUACION:\t%.6f\n", evaluacion(tokens_posfija));
	
	return 0;
}

void get_tokens(char *entrada, struct token *tokens)
{
	int token_tmp;

	while(*entrada != '\0'){
		if(tokens_totales >= NTOKENS){
			fprintf(stderr, "Capacidad de procesamiento: Maximo %d Tokens...Saliendo\n", NTOKENS);
			exit(-1);
		}

		token_tmp = lexico(entrada);
		memset(&tokens[tokens_totales], 0x00, sizeof(struct token));
		switch(token_tmp){
			case 1:
				tokens[tokens_totales].tipo = '+';
				break;
			case 2:
				tokens[tokens_totales].tipo = '-';
				break;
			case 3:
				tokens[tokens_totales].tipo = '*';
				break;
			case 4:
				tokens[tokens_totales].tipo = '/';
				break;
			case 5:
				tokens[tokens_totales].tipo = 'S';
				break;
			case 6:
				tokens[tokens_totales].tipo = 'C';
				break;
			case 7:
				printf("FALTA <\n");
				exit(-1);
			case 8:
				tokens[tokens_totales].tipo = '<';
				entrada++;	/* se salta el siguiente '<' */
				break;
			case 9:
				printf("FALTA >\n");
				exit(-1);
			case 10:
				tokens[tokens_totales].tipo = '>';
				entrada++;	/* se salta el siguiente '>' */
				break;
			case 11:
				tokens[tokens_totales].tipo = '^';
				break;
			case 12:
				tokens[tokens_totales].tipo = 'D';
				valtoken[val_index] = '\0';
				strcpy(tokens[tokens_totales].valor, valtoken);
				entrada = entrada + strlen(valtoken) - 1;
				break;
			case 13:
				printf("FALTA DIGITO\n");
				exit(-1);
			case 14:
				tokens[tokens_totales].tipo = 'F';
				valtoken[val_index] = '\0';
				strcpy(tokens[tokens_totales].valor, valtoken);
				entrada = entrada + strlen(valtoken) - 1;
				break;
			case 15:
				printf("FALTA (+|-) O DIGITO\n");
				exit(-1);
			case 16:
				printf("FALTA DIGITO\n");
				exit(-1);
			case 17:
				tokens[tokens_totales].tipo = 'E';
				valtoken[val_index] = '\0';
				strcpy(tokens[tokens_totales].valor, valtoken);
				entrada = entrada + strlen(valtoken) - 1;
				break;
			case 18:
				tokens[tokens_totales].tipo = '(';
				break;
			case 19:
				tokens[tokens_totales].tipo = ')';
				break;
			case 20:
				printf("TOKEN DESCONOCIDO...Saliendo\n");
				exit(-1);
		}
		entrada++;
		tokens_totales++;
		memset(valtoken, 0x00, sizeof(valtoken)); /* Se vacia valtoken para que pueda volver a ser usada */
		val_index = 0;	/* Se pone nuevamente en 0 el indice de valtoken */
	}
}

int lexico(char *entrada)
{
	unsigned int codigo, salida = 0, estado = 0;
	unsigned char caracter_actual;

	/*** TABLA DE TRANSICION ***/
	static unsigned int matriz_transicion[ESTADOS][CODIGOS] = {
	/* +   -   *   /   S   C   <   >   ^   D   .   E   e   (   ) otro */
	   1,  2,  3,  4,  5,  6,  7,  9, 11, 12,  0,  0,  0, 18, 19, 20, /* q0 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /* q1 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /* q2 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /* q3 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /* q4 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /* q5 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /* q6 */
	   0,  0,  0,  0,  0,  0,  8,  0,  0,  0,  0,  0,  0,  0,  0,  0, /* q7 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /* q8 */
	   0,  0,  0,  0,  0,  0,  0, 10,  0,  0,  0,  0,  0,  0,  0,  0, /* q9 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /* q10 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /* q11 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0, 12, 13, 15, 15,  0,  0,  0, /* q12 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0, 14,  0,  0,  0,  0,  0,  0, /* q13 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0, 14,  0, 15, 15,  0,  0,  0, /* q14 */
	  16, 16,  0,  0,  0,  0,  0,  0,  0, 17,  0,  0,  0,  0,  0,  0, /* q15 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0, 17,  0,  0,  0,  0,  0,  0, /* q16 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0, 17,  0,  0,  0,  0,  0,  0, /* q17 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /* q18 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /* q19 */
	   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /* q20 */
	};

	/*** TABLA DE SALIDA ***/
	static unsigned int matriz_salida[ESTADOS][CODIGOS] = {
	/* +   -   *   /   S   C   <   >   ^   D   .   E   e   (   ) otro */
	   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /* q0 */
	   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, /* q1 */
	   2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2, /* q2 */
	   3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3, /* q3 */
	   4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4, /* q4 */
	   5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5, /* q5 */
	   6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6, /* q6 */
	   7,  7,  7,  7,  7,  7,  0,  7,  7,  7,  7,  7,  7,  7,  7,  7, /* q7 */
	   8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8, /* q8 */
	   9,  9,  9,  9,  9,  9,  9,  0,  9,  9,  9,  9,  9,  9,  9,  9, /* q9 */
	  10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, /* q10 */
	  11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, /* q11 */
	  12, 12, 12, 12, 12, 12, 12, 12, 12,  0,  0,  0,  0, 12, 12, 12, /* q12 */
	  13, 13, 13, 13, 13, 13, 13, 13, 13,  0, 13, 13, 13, 13, 13, 13, /* q13 */
	  14, 14, 14, 14, 14, 14, 14, 14, 14,  0, 14,  0,  0, 14, 14, 14, /* q14 */
	   0,  0, 15, 15, 15, 15, 15, 15, 15,  0, 15, 15, 15, 15, 15, 15, /* q15 */
	  16, 16, 16, 16, 16, 16, 16, 16, 16,  0, 16, 16, 16, 16, 16, 16, /* q16 */
	  17, 17, 17, 17, 17, 17, 17, 17, 17,  0, 17, 17, 17, 17, 17, 17, /* q17 */
	  18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, /* q18 */
	  19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, /* q19 */
	  20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, /* q20 */
	};

	while(salida == 0){
		caracter_actual = *entrada;
		codigo = filtro(estado, caracter_actual);
		salida = matriz_salida[estado][codigo];
		estado = matriz_transicion[estado][codigo];

		entrada++;
	}

	return salida;
}

/*** Convierte el simbolo de entrada en la columna de la matriz ***/
int filtro(int estado, unsigned char caracter_actual)
{
	if(isalpha(caracter_actual)){
		if(estado == 12 || estado == 14){ /* Estados 12 o 14, contexto notacion cientifica */
			if(caracter_actual == 'E'){
				if(val_index >= VAL_LEN){
					fprintf(stderr, "Capacidad de procesamiento: Maximo %d digitos por numero...Saliendo\n", VAL_LEN);
					exit(-1);
				}

				valtoken[val_index++] = caracter_actual;
				return 11;
			}
			if(caracter_actual == 'e'){
				if(val_index >= VAL_LEN){
					fprintf(stderr, "Capacidad de procesamiento: Maximo %d digitos por numero...Saliendo\n", VAL_LEN);
					exit(-1);
				}

				valtoken[val_index++] = caracter_actual;
				return 12;
			}
		}
	}

	if(isdigit(caracter_actual)){
		if(val_index >= VAL_LEN){
			fprintf(stderr, "Capacidad de procesamiento: Maximo %d digitos por numero...Saliendo\n", VAL_LEN);
			exit(-1);
		}

		valtoken[val_index++] = caracter_actual;
		return 9;
	}

	switch(caracter_actual){
		case '+':
			if(estado == 15){
				if(val_index >= VAL_LEN){
					fprintf(stderr, "Capacidad de procesamiento: Maximo %d digitos por numero...Saliendo\n", VAL_LEN);
					exit(-1);
				}

				valtoken[val_index++] = '+';
			}
				return 0;
		case '-':
			if(estado == 15){
				if(val_index >= VAL_LEN){
					fprintf(stderr, "Capacidad de procesamiento: Maximo %d digitos por numero...Saliendo\n", VAL_LEN);
					exit(-1);
				}

				valtoken[val_index++] = '-';
			}
				return 1;
		case '*':	return 2;
		case '/':	return 3;
		case 'S':
		case 's':	return 4;
		case 'C':
		case 'c':	return 5;
		case '<':	return 6;
		case '>':	return 7;
		case '^':	return 8;
		case '.':
			if(val_index >= VAL_LEN){
				fprintf(stderr, "Capacidad de procesamiento: Maximo %d digitos por numero...Saliendo\n", VAL_LEN);
				exit(-1);
			}

			valtoken[val_index++] = caracter_actual;
				return 10;
		case '(':	return 13;
		case ')':	return 14;
		default:	return 15; /* otro */
	}
}

void posfija(struct token *tokens, struct token *salida)
{
	struct pila_token pila;
	struct token simbolo;
	int prioridad_entrada, prioridad_pila, k, m = 0;

	iniciar_pila_token(&pila);

	for(k = 0; k < tokens_totales; k++)
		switch(tokens[k].tipo){
			case 'D':
			case 'F':
			case 'E':
				salida[m++] = tokens[k];
				break;
			case '(':
				meter_pila_token(&pila, tokens[k]);
				break;
			case ')':
				simbolo = sacar_pila_token(&pila);
				while(simbolo.tipo != '('){
					salida[m] = simbolo;
					m++;
					simbolo = sacar_pila_token(&pila);
				}
				break;
			case '+':
			case '-':
			case '<':
			case '>':
			case '*':
			case '/':
			case 'S':
			case 'C':
			case '^':
				if(pila_vacia_token(&pila)){
					meter_pila_token(&pila, tokens[k]);
					break;
				}

				simbolo = sacar_pila_token(&pila);

				if(simbolo.tipo == '('){
					meter_pila_token(&pila, simbolo);
					meter_pila_token(&pila, tokens[k]);
					break;
				}

				prioridad_entrada = asignar_prioridad(tokens[k].tipo);
				prioridad_pila = asignar_prioridad(simbolo.tipo);

				if(prioridad_entrada >= prioridad_pila){
					salida[m++] = simbolo;
					k--;
				}
				else{
					meter_pila_token(&pila, simbolo);
					meter_pila_token(&pila, tokens[k]);
				}
				break;
		}

	while(!pila_vacia_token(&pila))
		salida[m++] = sacar_pila_token(&pila);

	salida[m].tipo = '0';
}

float evaluacion(struct token *tokens)
{
	float operando_izquierdo, operando_derecho, operando_unico, resultado;
	struct pila_float pila;
	int k = 0;

	iniciar_pila_float(&pila);

	while(tokens[k].tipo != '0'){
		switch(tokens[k].tipo){
			case 'D':
			case 'F':
			case 'E':
				meter_pila_float(&pila, (float) strtod(tokens[k].valor, NULL));
				break;
			case '+':
			case '-':
			case '*':
			case '/':
			case '<':
			case '>':
			case '^':
				operando_derecho = sacar_pila_float(&pila);
				operando_izquierdo = sacar_pila_float(&pila);
				switch(tokens[k].tipo){
					case '+':
						resultado = operando_izquierdo + operando_derecho;
						break;
					case '-':
						resultado = operando_izquierdo - operando_derecho;
						break;
					case '*':
						resultado = operando_izquierdo * operando_derecho;
						break;
					case '/':
						resultado = operando_izquierdo / operando_derecho;
						break;
					case '<':
						resultado = (int) operando_izquierdo << (int) operando_derecho;
						break;
					case '>':
						resultado = (int) operando_izquierdo >> (int) operando_derecho;
						break;
					case '^':
						resultado = pow((double) operando_izquierdo, (double) operando_derecho);
						break;
				}
				meter_pila_float(&pila, resultado);
				break;
			case 'S':
				operando_unico = sacar_pila_float(&pila);
				resultado = sin(3.14159 * operando_unico / 180);
				meter_pila_float(&pila, resultado);
				break;
			case 'C':
				operando_unico = sacar_pila_float(&pila);
				resultado = cos(3.14159 * operando_unico / 180);
				meter_pila_float(&pila, resultado);
				break;
		}
		k++;
	}

	return sacar_pila_float(&pila);
}

/*******************************************
******** FUNCIONES PARA pila_token *********
*******************************************/
void iniciar_pila_token(struct pila_token *a)
{
	memset(a, 0x00, sizeof(struct token));
	a->tope = -1;
}

void meter_pila_token(struct pila_token *a, struct token b)
{
	a->tope++;
	a->pila[a->tope] = b;
}

struct token sacar_pila_token(struct pila_token *a)
{
	struct token tokn = a->pila[a->tope];

	a->tope--;

	return tokn;
}

int pila_vacia_token(struct pila_token *a)
{
	if(a->tope == -1)
		return 1;

	return 0;
}
/*******************************************/

/********************************************
******** FUNCIONES PARA pila_float **********
********************************************/
void iniciar_pila_float(struct pila_float *a)
{
	memset(a, 0x00, sizeof(struct pila_float));
	a->tope = -1;
}

void meter_pila_float(struct pila_float *a, float b)
{
	a->tope++;
	a->pila[a->tope] = b;
}

float sacar_pila_float(struct pila_float *a)
{
	float simbolo = a->pila[a->tope];

	a->tope--;

	return simbolo;
}
/******************************************/

int asignar_prioridad(unsigned char a)
{
	if(a == '^')
		return 1;
	if(a == 'S' || a == 'C')
		return 2;
	if(a == '*' || a == '/')
		return 3;
	if(a == '<' || a == '>')
		return 4;
	if(a == '+' || a == '-')
		return 5;
}