#include "rpn.h"
#include <string.h>
#include <stdio.h>
#include "stack.h"
#include "queue.h"

int comp_prec(char op_one, char op_two){
	if(op_one == '+' || op_one == '-'){
		if(op_two == '('){
			return 1;
		}
		else{
			return -1;
		}
	}
	else if(op_one == '*' || op_one == '/'){
		if(op_two == '^' || op_two == '*' || op_two == '/'){
			return -1;
		}
		else{
			return 1;
		}

	}
	else if(op_one == '^'){
		return 1;

	}
	else{
		return 0;
	}
}

int check_op(char op){
	if(op == '+' || op == '-' || op == '*' || op == '/' || op == '^'){
		return 1;
	}
	else{
		return 0;
	}
}
int check_num(char num){
	if(num == '0' || num == '1' || num == '2' || num == '3' || num == '4' || num == '5' || num == '6' || num == '7' || num == '8' || num == '9'){
		return 1;
	}
	else{
		return 0;
	}
}
void removeSpaces(char* source){
	char* n = source;
	char* k = source;
	while(*k != 0){
		*n = *k++;
		if(*n != ' '){
			n++;
		}
	}
	*n = 0;
}


/* convert an infix expression to postfix (rpn) using the */
/* shunting yard algorithm. */
/* return a queue containing the postfix expression. */
/* if an error occurs during evaluation, return silently with NULL. */
Queue *infix_to_postfix(char *expr)
{
	int l = 0;
	int r = 0;
	int err = 0;
	int i = 0;
	int length;
	int j = 0;
	int space;
	Stack *shuntStack;
	Queue *final;
	shuntStack = initialise_stack();
	final = initialise_queue();
	removeSpaces(expr);
	length = strlen(expr);

	for(i = 0; i < length; i++){
		if(expr[i] == '('){
			l++;
		}
		else if(expr[i] == ')'){
			r++;
		}
		else if(check_num(expr[i])==0 && expr[i] != ')' && expr[i] != '(' && check_op(expr[i])==0 && expr[i]!='.'){
			err = 1;
		}
	}
	if(l!=r){
		err = 1;
	}

	if(err == 0){
		for(i = 0; i < length; i++) {
			if(expr[i] == '('){
				push_stack(shuntStack, (void *) &expr[i], 1);
			}
			else if( (check_op(expr[i])==1) && ((check_num(expr[i-1])==1) || (expr[i-1]==')'))  ){
				if(shuntStack->head){
					if( comp_prec(expr[i],*((char *)peek_stack(shuntStack))) > 0){
						push_stack(shuntStack, (void *) &expr[i], 1);
					}
					else{
						while( comp_prec(expr[i], *((char *)peek_stack(shuntStack))) < 0){
							push_queue(final,pop_stack(shuntStack),1);
							if(!shuntStack->head){
								break;
							}
						}
						push_stack(shuntStack, (void *) &expr[i], 1);
					}
				}
				else{
					push_stack(shuntStack, (void *) &expr[i], 1);
				}
			}
			else if(expr[i] == ')'){
				while(*((char *)peek_stack(shuntStack)) != '('){
					push_queue(final, pop_stack(shuntStack),1);
				}
				pop_stack(shuntStack);
			}
			else if(expr[i] == ' '){
				continue;
			}
			else{
				j=i;
				space=1;
				if(expr[j+1]== '.' || expr[j] == '+' || expr[j] == '-' || check_num(expr[j+1])==1){
					while(1){
						space++;
						j++;
						if(!expr[j+1] || check_op(expr[j+1]) == 1 || expr[j+1] == ')' || expr[j+1] == '('){
							break;
						}
					}
				}
				push_queue(final,(void *) &expr[i],space);
				i+=(space-1);
			}
		}
		while(shuntStack->head){
			push_queue(final,pop_stack(shuntStack),1);
			if(!shuntStack->head){
				break;
			}
		}
		free_stack(shuntStack);
		return final;
	}
	else{
		free_stack(shuntStack);
		free_queue(final);
		return NULL;
	}
}