#include<stdio.h>
#include<stdlib.h>


#define MAX_SIZE 100
#define lparen 0
#define rparen 1
#define plus 2
#define minus 3
#define times 4
#define divide 5
#define mod 6
#define eos 7
#define operand 8

int isp[] = {0, 19, 12, 12, 13, 13, 13, 0,14}; //우선순위 지정
int icp[] = {20, 19, 12, 12, 13, 13, 13, 0,14};


int stack[MAX_SIZE]; //스택 할당

char input[MAX_SIZE];
char output[MAX_SIZE];
char symbol;
int top = 0;

void push(int *top, int item)// 스택삽입
{
	(*top)++;
	stack[*top] = item;

}
void pop(int *top)//스택삭제
{
	stack[*top] = NULL;
	(*top)--;
}
int popInteger(int *top)
{
	int pop = stack[*top];
	stack[*top] =NULL;
	(*top)--;
	return pop;
}
char get_op()//정수형 스택에 맞는 문자형 연산자 구하기
{
	switch(stack[top])
	{
	case 2:
		return '+';
	case 3:
		return '-';
	case 4:
		return '*';
	case 5:
		return '/';
	case 6:
		return '%';
	}
}
void input_to_output()//중위표기를 후위표기로 변환하는 함수
{
	int token;
	int index =-1;
	int count =0;
	int i;
	stack[0] =eos;
	
	
	for(token = get_token(&symbol, &index); token!=eos; token = get_token(&symbol ,&index)) 
	{

		
		if(token == operand) //토큰이 정수 일시 바로 후위 표기 배열에 입력
		{	
			output[count] = symbol;
			count ++;
		}
		else if(token == rparen)//토큰이 ')' 일경우 '('앞까지 출력
		{
			while(stack[top] != lparen)
			{
				output[count] = get_op(); //후위표기배열에 스택에 알맞은 연산자 삽입
				pop(&top);
				count++;
			}
			pop(&top);//'('삭제
		}
		else
		{
			while(isp[stack[top]]>=icp[token])
			{
				output[count] = get_op();
				count++;
				pop(&top);
		
			}
			push(&top, token);
			
		}
	}

	if(stack[top] !=NULL) //마지막으로 스택에 남아있는 연산자를 후위표기 배열로 삽입
	{
		output[count] = get_op();
		pop(&top);
	}

	printf("중위 표기 계산식에서 후위표기 계산식으로 바꾼 식 : "); //후위표기로 변환한 계산식 출력
	for(i=0; output[i]!=NULL ; i++) 
		printf("%c", output[i]);
	printf("\n");
}

int get_token(char *symbol, int *index) //입력한 중위 표기 계산식에서 문자 하나씩 가져오는 함수
{
	(*index)++;
	*symbol = input[*index];
	switch(*symbol)
	{
	case '(':
		return lparen;
	case ')':
		return rparen;
	case '+':
		return plus;
	case '-':
		return minus;
	case '*':
		return times;
	case '/':
		return divide;
	case '%':
		return mod;
	case '\0':
		return eos;
	default :
		return operand;
	}
	
		
}
int cal()
{
	int op1, op2;
	int i;

	for(i=0; i<output[i]; i++)
	{
		switch(output[i])
		{
		case '+':
			op1 = popInteger(&top);
			op2 = popInteger(&top);
			push(&top, (op1+op2));
			break;
		case '-':
			op1 = popInteger(&top);
			op2 = popInteger(&top);
			push(&top, (op2-op1));
			break;
		case '*':
			op1 = popInteger(&top);
			op2 = popInteger(&top);
			push(&top, (op1*op2));
			break;
		case '/':
			op1 = popInteger(&top);
			op2 = popInteger(&top);
			push(&top, (op2/op1));
			break;
		case '%':
			op1 = popInteger(&top);
			op2 = popInteger(&top);
			push(&top, (op2%op1));
			break;
		default:
			push(&top, output[i]-48);
			
		}
	}
	return stack[top];
}
main()
{
	int result;
	
	printf("\n\n|-------------------------------------|\n");
	printf("|-----------계산기 프로그램-----------|\n");
	printf("|-------------------------------------|\n");
	printf("|----계산식을 입력방법 : ----|\n");
	printf("|-------------------------------------|\n\n");
	printf("계산식을 입력하시오 : "); gets(input);
	printf("%s", input);
	input_to_output();
	result = cal();
	printf("답은 %d 입니다. \n", result);
}