#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX 50

char formula[MAX] = {}; //식을 입력받는 변수
char newfor[MAX][MAX] = {}; //피연산자와 연산자를 분리해서 저장하는 변수
char newop[MAX] = {}; //연산자를 후위식으로 변형하기위한 임시 저장 변수

char num[1][10] = {}; // 입력받은 식에서 피연산자를 저장하는 변수
char operate[1] = {}; // 입력받은 식에서 연산자를 임시로 저장하는 변수

int fmlength = 0; // 입력받은 식의 길이를 저장하는 변수

void Token(char x[]){ //피연산자와 연산자 분리

	int ncount = 0; //피연산자 개수
	int ocount = 0; //연산자 개수
	int fcount= 0; //피연산자와 연산자의 개수
	int xlength; // 매개변수 문자열x의 길이
	int tcount = 0; // 연산자 전의 문자 개수
	
	xlength = strlen(x);

	for(int i = 0; i < xlength; i++){

		if(x[i] == '*'|| x[i] == '/'|| x[i] == '+'|| x[i] == '-'){			
			strcpy(newfor[fcount],num[0]);//피연산자 복사
			fcount++;
			memset(num[0], '\0', sizeof(num[0])); //피연산자 임시저장 변수 초기화
			tcount = 0; // 피연산자 임시저장위치 초기화

			operate[0] = x[i];
			strcpy(newfor[fcount],operate); // 연산자 복사
			fcount++;
			ocount++;
			ncount++;
		}
		else if(x[i] == '('){
			operate[0] = x[i];
			strcpy(newfor[fcount],operate);
			fcount++;
			ocount++;			
		}
		else if(x[i] == ')'){
			strcpy(newfor[fcount],num[0]);
			fcount++;
			memset(num[0], '\0', sizeof(num[0]));
			tcount = 0;

			operate[0] = x[i];
			strcpy(newfor[fcount],operate);
			fcount++;
			ocount++;
			ncount++;
		}
		else if(x[i] == ' '){
			continue;
		}
		else{
			num[0][tcount]= x[i];
			tcount++;
		}
	}
	strcpy(newfor[fcount],num[0]);// 마지막 피연산자 복사
	ncount++; // 마지막 피연산자
	fmlength = ncount + ocount; //피연산자 개수와 연산자 개수의 합을 저장
}

void sort(){ //후위연산 변환

	int lcount = 0; //연산자 개수 저장 위치
	int ncount = 0; // 후위식 변경 저장
	int ocount = 0; // 연산자 저장 위치
	int left[MAX] = {}; //'(' 이전까지의 연산자 개수 저장
	int barket = 0; // '(' 개수 저장
	char nnewfor[MAX][MAX] = {};

	for(int i = 0; i < fmlength; i++){
		strcpy(nnewfor[i],newfor[i]);
	}
	memset(newfor, '\0', sizeof(newfor));

	
	for(int i = 0; i < fmlength; i++){
		if(nnewfor[i][0] == '+' || nnewfor[i][0] == '-'){ // 연산자를 만나면 저장하고 다음 수식을 비교
			newop[ocount] = nnewfor[i][0];
			ocount++;	
			i++;
			if(nnewfor[i][0] == '('){ // 다음수식이 '(' 지금까지의 연산자 개수 저장
				barket++;
				left[lcount] = ocount;				
			}
			else{			
				strcpy(newfor[ncount],nnewfor[i]);
				ncount++;				
			}
		}
		else if(nnewfor[i][0] == '*' || nnewfor[i][0] == '/'){
			newop[ocount] = nnewfor[i][0];
			ocount++;
			i++;
			if(nnewfor[i][0] == '('){
				barket++;
				left[lcount] = ocount;				
			}
			else if(nnewfor[i][0] == ')'){
				barket--;
				if(barket == 0){
					for(int j = ocount - 1; j >= 0; j--){ //수식에서 newop에 저장되있던 나머지 newfor에저장
						newfor[ncount][0] = newop[j];
						ncount++;
					}
					ocount = 0;
				}
				else{
					for(int j = ocount - 1; j >= left[lcount]; j--){ // ')'가 남아있으면 그전까지 연산자 출력
						newfor[ncount][0] = newop[j];
						ncount++;
					}
					ocount = left[lcount];
					lcount--;
				}
			}
			else{
				if(barket == 0){
					strcpy(newfor[ncount],nnewfor[i]);
					ncount++;
					for(int j = ocount - 1; j >= 0; j--){
						newfor[ncount][0] = newop[j];
						ncount++;
					}
					ocount = 0;
				}
			}
		}
		else if(nnewfor[i][0] == '('){//수의 개수 저장
			barket++;
			lcount++;
			left[lcount] = ocount;
		}	
		else if(nnewfor[i][0] == ')'){
			barket--;
			if(barket == 0){
				for(int j = ocount - 1; j >= 0; j--){ 
					newfor[ncount][0] = newop[j];
					ncount++;
				}
				ocount = 0;
			}
			else{
				for(int j = ocount - 1; j >= left[lcount]; j--){ 
					newfor[ncount][0] = newop[j];
					ncount++;
				}
				ocount = left[lcount];
				lcount--;
			}
		}		
		else{
			strcpy(newfor[ncount],nnewfor[i]);
			ncount++;
		}
	}
	for(int j = ocount - 1; j >= 0; j--){ //수식에서 newop에 저장되있던 나머지 저장
			newfor[ncount][0] = newop[j];
			ncount++;
	}
	ocount = 0;
}

double calculate(char x[][MAX]){//후위연산식 계산

	double numeric[MAX] = {};
	double result = 0;
	int count = 0;
	int ncount = 0;
	
	for(int i = 0; i < fmlength; i++){ // 후위식으로 연산자 앞의 두개의 수로 계산
		if(x[i][0] == '+'){
			numeric[ncount-2] = numeric[ncount-2] + numeric[ncount-1];
			ncount--;
		}
		else if(x[i][0] == '-'){
			numeric[ncount-2] = numeric[ncount-2] - numeric[ncount-1];
			ncount--;
		}
		else if(x[i][0] == '/'){
			numeric[ncount-2] = numeric[ncount-2] / numeric[ncount-1];
			ncount--;
		}
		else if(x[i][0] == '*'){
			numeric[ncount-2] = numeric[ncount-2] * numeric[ncount-1];
			ncount--;
		}
		else{ // 연산자가 아니면 자료형 변형
			numeric[ncount] = atof(x[i]);
			ncount++;
		}
	}
	result = numeric[0];

	return result;
}

void main(){

	double result = 0;

	printf("수식 입력 : ");
	gets(formula);

	Token(formula);
	printf("토큰 : \n");

	for(int i = 0; i < fmlength; i++){
		printf("%s\n", newfor[i]);
	}
	printf("\n");
	sort();
	
	printf("후위 연산식 : ");
	for(int i = 0; i < fmlength; i++){
		printf("%s", newfor[i]);
	}
	
	printf("\n");
	result = calculate(newfor);
	printf("결과값 : %0.2f", result);

}