/* (C) Copyright 2008 Nick Mudge <mudgen@gmail.com>
 * This code can be freely copied and modified.
 */
 
#include "scanner.c"
#include <stdlib.h>

typedef struct node {
	Token token;
	struct node *node_left;
	struct node *node_right;
	struct node *node_parent;
} Node;

static struct {
	Node *node[500];
	int count;
} token_tracker;

extern Symbol_table *symbol_table;

char *input;
char *input_beginning;
Token token;
Token look_ahead_token;

void error(char *message);
Node *new_node(void);
void free_nodes(void);
int precedence(char next, char current);
void parse(Node *current_node);
int node_traverse(Node *current_node, int value);
int apply_traverse_operator(Node *current_node, int total);
int apply_operator(Node *current_node, int total, int value);

int main(int argc, char *argv[]) {	
	int state = 0;	
	Node *current_node;
	Node *temp_node;
	if(argc < 2 || argc > 2) {
		printf("Usage: arith \"EXPRESSION\"\n");
		return(1);
	}	
	input_beginning = malloc(sizeof(char) * strlen(argv[1])+1); 
	input = &input_beginning[strlen(argv[1])-1];
	strcpy(input_beginning, argv[1]);	
	symbol_table = create_symbol_table(5000);
	
	for(la(); token.value != ERROR_TOKEN; la()) {
		if(token.value == TOKEN_END)
			break;
		if(state == 0) {
			if(token.value == ';') {
				state = 1;
			}
			else {
				error("syntax error -- missing ;");
			}
		}
		else if(state == 1) {
			if(token.value == IDENTIFIER || token.value == NUM) {
				state = 2;
				current_node = new_node();
				current_node->node_right = new_node();
				current_node->node_right->token = token;
			}
			else 
				error("syntax error -- missing number");
		}
		else if(state == 2) {
			if(token.value == '+' || token.value == '-' || token.value == '*' || token.value == '/' || token.value == '=') {
				state = 3;
				if(current_node->node_left != NULL) {
					current_node->node_left->token = token;
					current_node = current_node->node_left;
				}
				else {					
					current_node->token = token;
				}
			}			
			else
				error("syntax error -- missing operation");
		}
		else if(state == 3) {
			if(token.value == IDENTIFIER || token.value == NUM) {
				state = 2;
				if(look_ahead_token.value == TOKEN_END) {
					current_node->node_left = new_node();
					current_node->node_left->node_parent = current_node;
					current_node->node_left->token = token;
				}
				else if(precedence(look_ahead_token.value, current_node->token.value) >= 0) {
					current_node->node_left = new_node();
					current_node->node_left->node_parent = current_node;
					current_node->node_left->node_right = new_node();
					current_node->node_left->node_right->token = token;
				}
				else {
					current_node->node_left = new_node();
					current_node->node_left->token = token;
					if(current_node->node_parent != NULL) {
						for(current_node = current_node->node_parent;
							precedence(look_ahead_token.value, current_node->token.value) < 0;
								current_node = current_node->node_parent) {
								if(current_node->node_parent == NULL)
									break;
							}
					}
					temp_node = new_node();
					if(precedence(look_ahead_token.value, current_node->token.value) >= 0) {
						temp_node->node_right = current_node->node_left;
					}
					else {
						temp_node->node_right = current_node;
					}
					current_node = temp_node;
					
				}
			}
			else
				error("syntax error -- missing number");
		}
	}	
	if(token.value == ERROR_TOKEN)
		error("syntax error");
	parse(current_node);
	free_nodes();
	free_symbol_table();
	free(input_beginning);
	return 0;
}


void error(char *message) {
	free_symbol_table();
	printf("Parse Error: %s\n", message);
	exit(1);
}

Node *new_node(void) {	
	Node *node;
	node = malloc(sizeof(Node));
	node->node_left = NULL;
	node->node_right = NULL;
	node->node_parent = NULL;
	token_tracker.node[token_tracker.count] = node;
	token_tracker.count++;
	return node;	
}

void free_nodes(void) {
	int i;
	for(i = 0; i < token_tracker.count; i++)
		free(token_tracker.node[i]);
}

int precedence(char next, char current) {
	switch(next) {
		case '=':
		case ';':
			next = 0;
			break;
		case '+':
		case '-':
			next = 1;
			break;
		case '*':
		case '/':
			next = 2;
			break;
	}
	switch(current) {
		case ';':
		case '=':
			current = 0;
			break;
		case '+':
		case '-':
			current = 1;
			break;
		case '*':
		case '/':
			current = 2;
			break;
	}
	
	if(next == current)
		return 0;
	else if(next > current)
		return 1;
	else
		return -1;
}

int node_traverse(Node *current_node, int value) {
	if(current_node->node_left->token.value != NUM && current_node->node_left->token.value != IDENTIFIER)
		value = node_traverse(current_node->node_left, value);
	
	return apply_traverse_operator(current_node, value);
}

void parse(Node *current_node) {
	int total = 0;
	while(current_node->node_right->token.value != NUM || current_node->node_parent != NULL) {
		if(current_node->node_right->token.value != NUM) {			
			total = apply_operator(current_node, total, node_traverse(current_node->node_right, 0));
			current_node = current_node->node_right;
		}
		else {
			current_node = current_node->node_parent;
			if(current_node->node_right->token.value == NUM)
				total = apply_operator(current_node, total, atoi(current_node->node_right->token.symbol_entry->str));
			else {				
				total = apply_operator(current_node, total, node_traverse(current_node->node_right, 0));
				current_node = current_node->node_right;
			}
		}		
	}
	printf("%d\n", total);
}

int apply_traverse_operator(Node *current_node, int total) {
	if(current_node->node_left->token.value == NUM && current_node->node_right->token.value == NUM) {
		if(current_node->token.value == '+') {			
			return total = atoi(current_node->node_left->token.symbol_entry->str) +
					atoi(current_node->node_right->token.symbol_entry->str);
		}
		else if(current_node->token.value == '-') {
			return total = atoi(current_node->node_left->token.symbol_entry->str) -
					atoi(current_node->node_right->token.symbol_entry->str);		
		}
		else if(current_node->token.value == '*') {
			return total = atoi(current_node->node_left->token.symbol_entry->str) *
					atoi(current_node->node_right->token.symbol_entry->str);
		}
		else if(current_node->token.value == '/') {
			return total = atoi(current_node->node_left->token.symbol_entry->str) /
					atoi(current_node->node_right->token.symbol_entry->str);
		}
	}
	else if(current_node->node_right->token.value == NUM) {
		if(current_node->token.value == '+') {			
			return total += atoi(current_node->node_right->token.symbol_entry->str);
		}
		else if(current_node->token.value == '-') {
			return total -= atoi(current_node->node_right->token.symbol_entry->str);		
		}
		else if(current_node->token.value == '*') {
			return total *= atoi(current_node->node_right->token.symbol_entry->str);
		}
		else if(current_node->token.value == '/') {
			return total /= atoi(current_node->node_right->token.symbol_entry->str);
		}
	}
	else if(current_node->node_left->token.value == NUM) {
		if(current_node->token.value == '+') {			
			return total += atoi(current_node->node_left->token.symbol_entry->str);
		}
		else if(current_node->token.value == '-') {
			return total -= atoi(current_node->node_left->token.symbol_entry->str);		
		}
		else if(current_node->token.value == '*') {
			return total *= atoi(current_node->node_left->token.symbol_entry->str);
		}
		else if(current_node->token.value == '/') {
			return total /= atoi(current_node->node_left->token.symbol_entry->str);
		}
	}
	return total;	
}

int apply_operator(Node *current_node, int total, int value) {
	if(current_node->token.value == '+') {
		return total += value;
	}
	else if(current_node->token.value == '-') {
		return total -= value;
	}
	else if(current_node->token.value == '*') {
		return total *= value;
	}
	else if(current_node->token.value == '/') {
		return total /= value;
	}
	else if(current_node->token.value == '=') {
		return value;
	}
	return -1;
}