#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX_N 20 //max chars in any one number
#define MAX_E 100 // max chars in equation (also max elements in struct array)
struct element {
	char type;   // this will work like an enum n for number, a for add, s for subtract, 
				 // m for multiply, d for divide, l for left parenthesis, r for right parenthasis
				 // e for end of input
	char number_str[MAX_N];
	double number;
};

struct element elements[MAX_E];
struct element new_elements[MAX_E];
struct element within_p[MAX_E];
struct element temp;

char input_str[MAX_E];

int from_p_to_p[2], lc = 0, rc = 0; //positions of inner-most parentheses to use in removing elements
									// lc left parentheses count, rc right  (to make sure even)	
int invalid_char = 0;

int read_input(char *str, int max){
	char ch;
	int i = 0;
	while((ch = getchar()) != '\n'){
		if (ch != ' ')
			str[i++] = ch;
		if (i >= max)
			return -1;
	}
	str[i] = '\0';
	return i;
}

int process_input_str(char *str, struct element *elements){
	int p = 0, np = 0, sp = 0;  //p = string position, np = number position
								//sp = struct array position
	int is_negative = 0;
	while (str[p] != '\0'){
		is_negative = 0;
		if (isdigit(str[p]) || str[p] == '.' || str[p] == 'n'){
			if (str[p] == 'n'){
				is_negative = 1;
				++p;
				while (str[p] == 'n'){
					if (is_negative == 1)
						is_negative = 0;
					else if (is_negative == 0)
						is_negative = 1;
					++p;
				}
			}
			elements[sp].type = 'n';
			elements[sp].number_str[np++] = str[p++];
			while ((isdigit(str[p])) || str[p] == '.'){
				elements[sp].number_str[np++] = str[p++];
			}
			np = 0;
			elements[sp].number = atof(elements[sp].number_str);
			if (is_negative)
				elements[sp].number *= -1;
		}else{
			if (str[p] == '+' )
				elements[sp].type = 'a';
			else if (str[p] == '-' )
				elements[sp].type = 's';
			else if (str[p] == '*' )
				elements[sp].type = 'm';
			else if (str[p] == '/' )
				elements[sp].type = 'd';
			else if (str[p] == '('){
				elements[sp].type = 'l';
				++lc;
			}else if (str[p] == ')'){
				elements[sp].type = 'r';
				++rc;
			}else
				invalid_char = 1;
			++p;
			}
		++sp;
		}
	elements[sp].type = 'e';
	return sp;
}

void copy_ne_to_e(struct element *elem, struct element *new_elem){
	int i = 0;
	while (i <= MAX_E){
		elem[i] = new_elem[i];
		if (elem[i].type == 'e')
			return;
		++i;
	}
	return;
}

void remove_one_element(int sap, struct element *elem, struct element *new_elem){
	int i = 0, j = 0;
	while (i <= MAX_E){
		if (i != sap)
			new_elem[j++] = elem[i];
		if (new_elem[j-1].type == 'e'){
			copy_ne_to_e(elem, new_elem);
			return;
		}
		++i;
	}
	return;
}

	
void remove_two_elements(int sap, struct element *elem, struct element *new_elem){
	remove_one_element(sap, elem, new_elem);
	remove_one_element(sap, elem, new_elem);

	return;
}

int multiply(struct element *elem, struct element *new_elem){
	int found_m = 0;
	int i = 0; 
	while (i++ <= MAX_N){
		if (elem[i].type == 'e')
			return found_m;
		if (elem[i].type == 'm'){
			found_m = 1;
			elem[i-1].number =  elem[i-1].number * elem[i+1].number;
			remove_two_elements(i, elem, new_elem);
		}
	}
	return found_m;
}

int divide(struct element *elem, struct element *new_elem){
	int found_d = 0;
	int i = 0; 
	while (i++ <= MAX_N){
		if (elem[i].type == 'e')
			return found_d;
		if (elem[i].type == 'd'){
			found_d = 1;
			elem[i-1].number =  elem[i-1].number / elem[i+1].number;
			remove_two_elements(i, elem, new_elem);
		}
	}
	return found_d;
}

int add(struct element *elem, struct element *new_elem){
	int found_a = 0;
	int i = 0; 
	while (i++ <= MAX_N){
		if (elem[i].type == 'e')
			return found_a;
		if (elem[i].type == 'a'){
			found_a = 1;
			elem[i-1].number =  elem[i-1].number + elem[i+1].number;
			remove_two_elements(i, elem, new_elem);
		}
	}
	return found_a;
}


int subtract(struct element *elem, struct element *new_elem){
	int found_s = 0;
	int i = 0; 
	while (i++ <= MAX_N){
		if (elem[i].type == 'e')
			return found_s;
		if (elem[i].type == 's'){
			found_s = 1;
			elem[i-1].number =  elem[i-1].number - elem[i+1].number;
			remove_two_elements(i, elem, new_elem);
		}
	}
	return found_s;
}

void mdas(struct element *elem, struct element *new_elem){
	while (multiply(elem, new_elem))
		;
	while (divide(elem, new_elem))
		;
	while (add(elem, new_elem))
		;
	while (subtract(elem, new_elem))
		;
}

void gen_within_p(){
	int i = 0, j = 0;
	while (elements[i].type != 'r'){
		if (elements[i].type == 'l')
			from_p_to_p[0] = i;
		++i;
	}
	from_p_to_p[1] = i;
	for (i = from_p_to_p[0]+1; i < from_p_to_p[1]; i++)
		within_p[j++] =  elements[i];
	within_p[j].type = 'e';
}


void evaluate_within_p(){
	if (within_p[0].type == 'n' && within_p[1].type == 'e'){
		temp = within_p[0];
		return;
	}else{
		mdas(within_p, new_elements);
		temp = within_p[0];
	}
}

void replace_content_of_im_p(int *pp, struct element *elem, struct element *new_elem){
	int i = 0, j = 0;
	while (elem[i].type != 'e'){
		if (i == pp[0]){
			new_elem[j] = temp;
			++j;
		}else if (i < pp[0]){
			new_elem[j++] = elem[i];
		}else if (i > pp[1]){
			new_elem[j++] = elem[i];
		}
		++i;
	}
	new_elem[i].type = 'e';
	copy_ne_to_e(elem, new_elem);
}

int check_for_l(struct element *elem){
	int found_l = 0, i = 0;
	while (i <= MAX_E){
		if (elem[i].type == 'l')
			found_l = 1;
		if (elem[i].type == 'e')
			return found_l;
		++i;
	}
	return found_l;
}

int another_expression(){
	printf("\n\tEnter another expression?[Y/n] ");
    char ch = getchar();
    if (ch == '\n')
        return 1;
    while (ch != '\n'){
        if (ch == 'y' || ch == 'Y'){
            while ((getchar()) != '\n')
                ;
            return 1;
            }
        ch = getchar();
    }
    return 0;
}


int main(int argc, char *argv[])
{
	int repeat();
	printf("\n\n\tThis program evaluates expressions of the type:\n\n\t"
			"(8+4*2)-(2*(3+4/2))-1\n\n\tindicate negative number by prefixing n:\n\n\t"
			"n14 = -14");
	printf("\n\n\n\tEnter an expression: ");
	int over_flow = read_input(input_str, MAX_E);
	if (over_flow == -1){
		printf("\nError: expression excedes maximum length.\n");
		return -1;
	}
    process_input_str(input_str, elements);  
	if (invalid_char){
		invalid_char = 0;
		printf("\n\tError: invalid symbol detected.\n");
		return -1;
	}
	if (rc != lc){
		lc = rc = 0;
		printf("\n\tError: uneven number of parentheses.\n");
		return -1;
	}
	if (elements[0].type != 'n' && elements[0].type != 'l'){
		printf("\n\tError: expression begins with invalid symbol.\n\n");
		return -1;
			
	}
	while (check_for_l(elements)){
		gen_within_p();
		evaluate_within_p();
		replace_content_of_im_p(from_p_to_p, elements, new_elements);
	}
	printf("\n");
	mdas(elements, new_elements);
	int i = 0; 
	char ch;
	printf("\n\t");
	while ((ch = input_str[i++]) != '\0'){
		if (ch == 'n')
			ch = '-';
		printf("%c", ch);
	}
	printf(" = %lf\n\n", elements[0].number);
	if (another_expression()){
		while (repeat())
			;
	}
	printf("\n\tHave a nice day!\n\n");
	return 0;
}

int repeat(){
	int go_again;
	printf("\n\n\n\tEnter an expression: ");
	int over_flow = read_input(input_str, MAX_E);
	if (over_flow == -1){
		printf("\nError: expression excedes maximum length.\n");
		return -1;
	}
    process_input_str(input_str, elements);  
	if (elements[0].type != 'n' && elements[0].type != 'l'){
		printf("\n\tError: expression begins with invalid symbol.\n\n");
		return -1;
	}
	if (invalid_char){
		invalid_char = 0;
		printf("\n\tError: invalid symbol detected.\n");
		return -1;
	}

	if (rc != lc){
		lc = rc = 0;
		printf("\n\tError: uneven number of parentheses.\n");
		return -1;
	}
	
	while (check_for_l(elements)){
		gen_within_p();
		evaluate_within_p();
		replace_content_of_im_p(from_p_to_p, elements, new_elements);
	}
	printf("\n");
	mdas(elements, new_elements);
	int i = 0; 
	char ch;
	printf("\n\t");
	while ((ch = input_str[i++]) != '\0'){
		if (ch == 'n')
			ch = '-';
		printf("%c", ch);
	}
	printf(" = %lf\n\n", elements[0].number);
	go_again = another_expression();
	return go_again;
}