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

typedef struct node {
	Token *token;
	struct node *left;
	struct node *right;	
} Node;

typedef enum {FALSE=0, TRUE=1} bool;

extern Token *token;
char *input;

/* Parsing functions */
Node *new_node(void);
Node *parse(void);
Node *expr(Node *left);
Node *term(Node *left);
Node *factor(void);
void expect(char id);
void syntax_error(char *string);

/* Traversal functions */
int traverse(Node *node);
int traverse_right(Node *node, int value);
bool precedence(char op_left, char op_right);
int operation(int left, char operation, int right);
void free_tree(Node *node);

/* Main program */
int main(int argc, char *argv[]) {	
	Node *root;
	if(argc < 2 || argc > 2) {
		printf("Usage: arith \"EXPRESSION\"\n");
		return(1);
	}
	input = argv[1];
	root = parse();	
	printf("%d\n", traverse(root));
	free_tree(root);
	return 0;
}

/********************************************/
/* Parsing functions */

/* 
   Grammer:
   expr   -> term + expr | term - expr | term
   term   -> factor * term | factor / term | factor
   factor -> NUM | (expr)
   NUM    -> 1|2|3|4|5 ...
*/

Node *new_node(void) {	
	Node *node;
	if((node = malloc(sizeof(Node))) == NULL)
		memory_error();
	node->token = NULL;
	node->left = NULL;
	node->right = NULL;
	return node;
}

Node *parse(void) {	
	Node *node;
	node = expr(term(factor()));
	if(token->id != END_OF_TOKENS)
		syntax_error("Possible errors: illegal character, missing beginning parenthesis or missing operation");
	return node;
}

Node *expr(Node *left) {	
	Node *top_node;
	peek();
	if(token->id == '+' || token->id == '-') {
		next();
		top_node = new_node();
		top_node->token = token;
		top_node->left = left;
		top_node->right = expr(term(factor()));
		return top_node;
	}
	return left;
}

Node *term(Node *left) {
	Node *top_node;
	peek();
	if(token->id == '*' || token->id == '/') {
		next();
		top_node = new_node();
		top_node->token = token;
		top_node->left = left;
		top_node->right = term(factor());
		return top_node;
	}
	return left;	
}

Node *factor(void) {
	Node *node;
	peek();
	if(token->id == '(') {
		next();
		node = expr(term(factor()));
		expect(')');
		return node;
	}
	else if(token->id == NUM) {
		next();
		node = new_node();
		node->token = token;
		return node;
	}	
	syntax_error("missing number or ending parenthesis");
	return NULL;
}

void expect(char id) {	
	char error_msg[11] = "expected ";
	error_msg[9] = id;
	error_msg[10] = '\0';
	peek();
	if(token->id == id)
		next();
	else
		syntax_error(error_msg);
}

void syntax_error(char *string) {
	printf("Syntax error: %s\n", string);	
	exit(1);
}

/********************************************/
/* Tree traversal functions */

int traverse(Node *node) {	
	if(node->left->token->id == NUM) {
		return traverse_right(node, node->left->token->value);
	}
	return traverse_right(node, traverse(node->left));
}

int traverse_right(Node *node, int value) {
	if(node->right->token->id == NUM) {
		return operation(value, node->token->id, node->right->token->value);
	}
	else if(precedence(node->token->id, node->right->token->id)) {
		return operation(value, node->token->id, traverse(node->right));
	}
	else if(node->right->left->token->id == NUM) {		
		return traverse_right(node->right, operation(value, node->token->id, node->right->left->token->value));
	}	
	return traverse_right(node->right, operation(value, node->token->id, traverse(node->right->left)));
}

bool precedence(char op_left, char op_right) {
	if     (op_left == '+' && op_right == '*') return TRUE;
	else if(op_left == '*' && op_right == '+') return TRUE;
	else if(op_left == '-' && op_right == '*') return TRUE;
	else if(op_left == '*' && op_right == '-') return TRUE;
	else if(op_left == '+' && op_right == '/') return TRUE;
	else if(op_left == '/' && op_right == '+') return TRUE;
	else if(op_left == '-' && op_right == '/') return TRUE;
	else if(op_left == '/' && op_right == '-') return TRUE;
	return FALSE;
}

int operation(int left, char operation, int right) {
	if     (operation == '*') return left * right;
	else if(operation == '/') return left / right;
	else if(operation == '+') return left + right;
	else if(operation == '-') return left - right;
	return -1;
}

void free_tree(Node *node) {
	if(node->token->id != NUM) {
		free_tree(node->left);
		free_tree(node->right);
	}
	free(node->token);
	free(node);
}