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

typedef unsigned int uint;

/*
Teorie:
	In primul rand, trebuie sa stiu ca sunt 3 moduri in care pot scrie o expresie:
		a) Infix: X + Y -> operatorii sunt intre operanzi
		b) Prefix: + X Y -> operatorii sunt primii urmati de operanzi
		c) Postfix: X Y + -> operanzii apoi operatorii. I se mai spune Polish notaion
	Un arbore de expresii(expression tree) poate fi folosit pentru a evalua o expresie
	algebrica(x + y) sau booleana(x > y).
	Un arbore de expresii este un arbore binar in care frunzele sunt operanzii
	iar nodurile interne contin operatorii.
	Pentru a construi un arbore de expresii vom folosi o stiva, astfel:
		Parcurgem expresia de la dreapta la stanga, daca caracterul curent este
		un operand i-l punem(push) pe stiva, daca este un operator, atunci luam(pop)
		2 valori din stiva(ultimele 2 puse), creem un nou nod pentru operator si 
		face cele 2 valori extrase copii sai si punem nodul creat pentru operator in stiva.
		La final, stiva va contine un singur element ce reprezinta radacina arborelui de expresii.

	De asemenea, parcurgerea unui arbore de expresii fie inordine(infix), preordine sau
	postordine ne scrie expresia initiala fie infix, prefix sau postfix fara a faca vreo
	modificare arborelui.
*/

// Pentru a creea stiva ne vom folosi de o lista simplu inlantuita

struct tree_node
{
	uint payload;
	bool is_operator;
	struct tree_node *left;
	struct tree_node *right;
};

struct node2
{
	uint key;
	struct node2 *next;
};

struct node
{
	struct tree_node *dt;
	struct node *next;
};

// Stack for infix
struct node2 *push2(struct node2 *head, char k);
struct node2 *pop2(struct node2 *head);
char peek2(struct node2 *head);
int get_precedence(char c);

struct node *push(struct node *head, struct tree_node *dt);
struct node *pop(struct node *head);
struct tree_node *peek(struct node *head);
struct tree_node *new_node(uint dt, bool is_op, struct tree_node *lc, struct tree_node *rc);
void display(struct node *head);

struct node *construct(struct node *head, char *text, uint size);
uint eval(struct tree_node *root);

char *infix2postfix(FILE *from, uint size);

// Algoritmii obisnuiti de parcurgere a arborilor binari
void inorder(struct tree_node *cr);
void preorder(struct tree_node *cr);
void postorder(struct tree_node *cr);

int main(void)
{
	FILE *in = fopen("evaluare.in", "r");
	FILE *out = fopen("evaluare.out", "w");
	if(in != NULL && out != NULL)
	{
		struct node *head = NULL;

		// Todo: Merge doar pe expresii postfix si fara paranteze
		char *infix = infix2postfix(in, 100001);
		// printf("%s\n", infix);
		head = construct(head, infix, strlen(infix));
		// inorder(peek(head));
		fprintf(out, "%u\n", eval(peek(head)));

		free(infix);
		fclose(in);
		fclose(out);
	}
	else
	{
		printf("Error\n");
	}

	return 0;
}

// Aceasta functie va construi arborele binar de expresie pentru expresia data.
// Principiul de functionare este acesta:
//   Se parcurge expresia de la stanga la dreapta. Daca se gaseste un operand
//   atunci se creeaza un nod frunza cu payload-ul egal cu acesta si se depune pe stiva
//   Daca se gaseste un operator, se extrag ultimele 2 noduri din stiva, se creeaza un nou
//   nod cu valoarea operandului si facem cele 2 noduri extrase copii sai si punem nodul creeat pe stiva
//   In final, stiva va contine un singur nod ce reprezinta radacina arborelui binar de expresii
struct node *construct(struct node *head, char *text, uint size)
{
	char c = 'a';
	char *operands = "+-*/";
	uint current = 0; // Pentru a suporta numere mai mari ca 10
	uint i = 0;
	for(; i < size; i++)
	{
		c = text[i];
		if(c == EOF || c == '\n')
		{
			break;
		}
		if(c != ' ')
		{
			if(strchr(operands, c) != NULL)
			{
				if(current)
				{
					head = push(head, new_node(current, false, NULL, NULL));
					current = 0;
				}
				struct tree_node *t1 = peek(head);
				head = pop(head);
				struct tree_node *t2 = peek(head);
				head = pop(head);
				head = push(head, new_node(c, true, t2, t1));
			}
			else
			{
				current = current * 10 + c - '0';
			}
		}
		else
		{
			if(current)
			{
				head = push(head, new_node(current, false, NULL, NULL));
				current = 0;
			}
		}
	}
	return head;
}

// Compexitate: O(n)
// Algoritmul este unul simplu:
//  Daca nodul curent este o frunza(adica contine un operand) returnam valoarea sa
//  Daca nu, atunci contine un operator si tot ce trebuie sa facem este sa evalua
//  acel operator si cu cei 2 operanzi ai sai, operanzi pe care-i determinam apeland
//  functia recurisv
uint eval(struct tree_node *root)
{
	if(root != NULL)
	{
		if(!root->is_operator)
		{
			return root->payload;
		}
		else
		{
			if(root->payload == '+')
			{
				return eval(root->left) + eval(root->right);
			}
			else if(root->payload == '-')
			{
				return eval(root->left) - eval(root->right);
			}
			else if(root->payload == '/')
			{
				return eval(root->left) / eval(root->right);
			}
			else if(root->payload == '*')
			{
				return eval(root->left) * eval(root->right);
			}
		}
	}
}

// Acest algoritm va citi un o expresie dintr-un fisier(infix) si o va converti
// in postfix.
// Algoritmul de convertire a unei expresii infix in postfix este urmatorul:
//   Se parcurge expresia de la stanga la dreapta
//   Daca caracterul curent este:
//      a) un operand atunci pune-l in sir pur si simplu
//      b) Daca precedenta operatorului este mai mare decat cea a ultimului caracter
//         din stiva sau stiva este goala atunci pune-l pur si simplu in stiva
//         Daca nu, elimina din stiva elemente pana cand precedenta operatorului din varful stivei
//         este mai mica sau egala cu precedenta operatorului curent apoi pune operatorul pe stiva
//      c) Daca este paranteza '(', atunci pune-o pe stiva
//      d) Daca este paranteze ')', atunci elimina si pune in sir elemente pana cand gasesti o paranteza ')'
char *infix2postfix(FILE *from, uint size)
{
	char *infix = malloc(sizeof(char) * (size + 1));
	if(infix != NULL)
	{
		char *operands = "+-/*";
		struct node2 *head = NULL;
		char c = 'a';
		uint dx = 0;
		char digits[20], efx = 0;
		while(1)
		{
			c = getc(from);
			if(c == EOF || c == '\n')
			{
				break;
			}

			if(c == '(')
			{
				if(efx)
				{
					digits[efx++] = ' ';
					uint j = 0;
					for(; j < efx; j++)
					{
						infix[dx++] = digits[j];
					}
					efx = 0;
				}
				head = push2(head, c);
			}
			else if(c == ')')
			{
				if(efx)
				{
					digits[efx++] = ' ';
					uint j = 0;
					for(; j < efx; j++)
					{
						infix[dx++] = digits[j];
					}
					efx = 0;
				}
				while(peek2(head) != '(' && head != NULL)
				{
					infix[dx++] = peek2(head);
					head = pop2(head);
				}
				head = pop2(head);
			}
			else if((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9'))
			{
				digits[efx++] = c;
			}
			else
			{
				if(efx)
				{
					digits[efx++] = ' ';
					uint j = 0;
					for(; j < efx; j++)
					{
						infix[dx++] = digits[j];
					}
					efx = 0;
				}
				while(head != NULL && get_precedence(c) <= get_precedence(peek2(head)))
				{
					infix[dx++] = peek2(head);
					head = pop2(head);
				}
				head = push2(head, c);
			}
		}
		if(efx)
		{
			digits[efx++] = ' ';
			uint j = 0;
			for(; j < efx; j++)
			{
				infix[dx++] = digits[j];
			}
			efx = 0;
		}

		while(head != NULL)
		{
			infix[dx++] = peek2(head);
			head = pop2(head);
		}
		infix[dx++] = '\0';
		return infix;
	}
	else
	{
		printf("Error init\n");
		return NULL;
	}
}

int get_precedence(char c)
{
	switch(c)
	{
		case '+':
		case '-':
			return 1;
		case '*':
		case '/':
			return 2;
		case '^':
			return 3;
	}
	return -1;
}

void postorder(struct tree_node *cr)
{
	if(cr != NULL)
	{
		postorder(cr->left);
		postorder(cr->right);
		printf("%c ", cr->payload);
	}
}

void preorder(struct tree_node *cr)
{
	if(cr != NULL)
	{
		printf("%c ", cr->payload);
		preorder(cr->left);
		preorder(cr->right);
	}
}

// Nota: Parcurgerea inordine a unui arbore de expresii construit dintr-o expresie
// postfix ne afiseaza nodurile ca pe o expresie infix, cu alte cuvinte:
//  postfix ->(inorder) -> infix
void inorder(struct tree_node *cr)
{
	if(cr != NULL)
	{
		inorder(cr->left);
		if(cr->is_operator)
		{
			printf("%c ", cr->payload);
		}
		else
		{
			printf("%u ", cr->payload);
		}
		inorder(cr->right);
	}
}

struct tree_node *new_node(uint dt, bool is_op, struct tree_node *lc, struct tree_node *rc)
{
	struct tree_node *kp = malloc(sizeof(struct tree_node));
	if(kp != NULL)
	{
		kp->payload = dt;
		kp->is_operator = is_op;
		kp->left = lc;
		kp->right = rc;
	}
	return kp;
}

struct tree_node *peek(struct node *head)
{
	if(head == NULL)
	{
		printf("Empty\n");
		return NULL;
	}
	else
	{
		return head->dt;
	}
}

struct node *pop(struct node *head)
{
	if(head == NULL)
	{
		printf("Empty\n");
	}
	else
	{
		struct node *temp = head;
		head = head->next;
		free(temp);
	}
	return head;
}

struct node *push(struct node *head, struct tree_node *data)
{
	struct node *kp = malloc(sizeof(struct node));
	if(kp != NULL)
	{
		kp->dt = data;
		kp->next = NULL;

		if(head == NULL)
		{
			head = kp;
		}
		else
		{
			kp->next = head;
			head = kp;
		}
		return kp;
	}
}

void display(struct node *head)
{
	if(head == NULL)
	{
		printf("Empty\n");
	}
	else
	{
		struct node *cr = head;
		for(; cr != NULL; cr = cr->next)
		{
			printf("%c ", cr->dt->payload);
		}
		printf("\n");
	}
}

struct node2 *push2(struct node2 *head, char k)
{
	struct node2 *kp = malloc(sizeof(struct node2));
	if(kp != NULL)
	{
		kp->key = k;
		kp->next = NULL;
		if(head == NULL)
		{
			head = kp;
		}
		else
		{
			kp->next = head;
			head = kp;
		}
	}
	return head;
}

struct node2 *pop2(struct node2 *head)
{
	if(head == NULL)
	{
		printf("Error\n");
	}
	else
	{
		struct node2 *temp = head;
		head = head->next;
		free(temp);
	}
	return head;
}

char peek2(struct node2 *head)
{
	if(head == NULL)
	{
		printf("Empty\n");
	}
	else
	{
		return head->key;
	}
}