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

typedef struct stackNode
{
	double data;
	struct stackNode* link;
}stackNode;
stackNode* top = NULL;

typedef struct queueNode
{
	char data;
	struct queueNode* link;
}queueNode;
queueNode* front = NULL;
void Queue_Insert(char ch);
char Queue_Delete();
void Push(double value);
double Pop();
void Infix2Postfix(char expr[], char change_expr[]); 
double Eval_expr(char expr[], double* num);
void Input_expr(char expr[]); 
void Print_expr(char change_expr[]); 

int main() 
{
	while (1) 
	{
		char infix[20], postfix[20];

		system("cls");

		Input_expr(infix);

		Infix2Postfix(infix, postfix);

		Print_expr(postfix);

		system("pause");
	}
	return 0;
}

void Queue_Insert(char ch)
{
	queueNode* tempNode = (queueNode*)malloc(sizeof(struct queueNode));
	queueNode* temp = front;
	tempNode->data = ch;
	tempNode->link = NULL;

	if (front != NULL) 
	{
		while (temp->link != NULL)
			temp = temp->link;

		temp->link = tempNode;
	}
	else
		front = tempNode; 
}

char Queue_Delete() 
{
	char ch;
	queueNode* temp = front;

	if (temp == NULL) 
		exit(1);
	else if (temp->link == NULL)
	{
		front = NULL; 
		ch = temp->data;
		free(temp);
	}
	else
	{
		front = temp->link; 
		ch = temp->data;
		free(temp); 
	}
	return ch;
}

void Push(double value)
{
	stackNode* tempNode = (stackNode*)malloc(sizeof (struct stackNode));
	stackNode* temp = top;

	tempNode->data = value;
	tempNode->link = NULL;

	if (top != NULL) 
	{
		while (temp->link != NULL) 
			temp = temp->link;

		temp->link = tempNode;
	}
	else
		top = tempNode;
}

double Pop() 
{
	double value;
	stackNode* temp = top;
	stackNode* tempNode;

	if (top == NULL) 
	{
		printf("\n\t\tStack is empty!\n");
		exit(1);
	}
	else if (temp->link == NULL) 
	{
		top = NULL; 
		value = temp->data; 
		free(temp); 
	}
	else 
	{
		while (temp->link->link != NULL) 
			temp = temp->link;

		tempNode = temp->link;
		temp->link = NULL; 
		value = tempNode->data; 
		free(tempNode);
	}
	return value;
}

void Infix2Postfix(char expr[], char change_expr[]) 
{
	int i, point = 0;
	double temp;
	char ch;

	for (i = 0; expr[i] != '\0'; i++)
	{
		ch = expr[i];

		if (isdigit(ch))
			change_expr[point++] = ch;
		else if (ch == '(') 
			Push('(');
		else if (ch == ')')
		{
			while ((temp = Pop()) != '(')
			{
				change_expr[point++] = ' ';
				change_expr[point++] = (char)temp;
			}
		}
		else if (ch == '*' || ch == '/') 
		{
			change_expr[point++] = ' ';
			Push(ch);
		}
		else if (ch == '+' || ch == '-') 
		{
			change_expr[point++] = ' ';
			while (top != NULL) 
			{
				temp = Pop();
				if (temp == '*' || temp == '/')
					change_expr[point++] = (char)temp; 
				else
				{
					Push(temp);
					break;
				}
			}
			Push(ch);
		}
		else if (ch == ' ');
	}

	while (top != NULL) 
	{
		change_expr[point++] = ' ';
		change_expr[point++] = (char)Pop();
	}
	change_expr[point] = '\0';
	printf("ÁßÀ§Ç¥±â¹ý :  %s \n\n", expr);
}

double Eval_expr(char expr[], double* value)
{
	int i, temp = 0;
	double result;

	for (i = 0; expr[i] != '\0'; i++)
	if (isdigit(expr[i])) 
	{
		Queue_Insert(expr[i]);

		if (!isdigit(expr[i + 1]))
		{
			while (front != NULL)
				temp = temp * 10 + Queue_Delete() - '0';

			Push(temp);
			temp = 0;
		}
	}
	else if (expr[i] == '+')      
		Push(Pop() + Pop());
	else if (expr[i] == '*')      
		Push(Pop() * Pop());
	else if (expr[i] == '-')       
	{
		result = Pop();
		Push(Pop() - result);
	}
	else if (expr[i] == '/')      
	{
		result = Pop();
		Push(Pop() / result);
	}
	*value = Pop();         
	return 0;
}

void Input_expr(char expr[]) 
{
	printf("\t\t* ÈÄÀ§Ç¥±â¹ý ¿¬»ê ÇÁ·Î±×·¥(ÇÁ·Î±×·¥ Á¾·á : q or Q)*              \n");
	printf("½ÄÀ» ÀÔ·ÂÇϼ¼¿ä : ");
	gets(expr);
	printf("\n");
}

void Print_expr(char change_expr[]) 
{
	double result;

	Eval_expr(change_expr, &result);      // ÈÄÀ§½Ä ¿¬»ê ÇÔ¼ö È£Ãâ

	printf("ÈÄÀ§½Ä :  %s \n\n", change_expr);
	printf("°á°ú :  %.2lf \n\n", result);
}