infix to postfix

infix_to_postfix.c

// input.txt
// 6
// 21+(3-4)*(8-3)*(3+1)/2
// (3+4)*8-(3+7)/2
// (11-8)/3+7*2
// 11+(14-3+2)*2-3+(1+6-5)
// (1+2+3+4+5+6)/3+4+5
// 1*2+3/2+4-4+5+6+6+5-(5*7-5)


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

int GetLineNum(FILE* in){
	char buf[50];
	fgets(buf, sizeof(buf)-1, in);

	return atoi(buf);
}

char* GetOneLine(FILE* in){
	char *buf = (char*)malloc( sizeof(char)*50 );
	fgets(buf, 49, in);
	int null_pos = strlen(buf);
	buf[null_pos-1] = 0;

	return buf;
}

typedef struct entry {
	struct entry *next;
	char   *el;
	int    type;
} Entry;

typedef struct {
	Entry *head;
	int count;
} List;

List *MakeList(void){
	List *l = (List*)malloc( sizeof(List) );
	l->head = NULL;
	l->count = 0;

	return l;
}

void DestroyList(List* l){
	free(l);
}

void AttachRear(List* l, Entry* entry){
	l->count ++;
	//printf("%s %d\n", entry->el, entry->type);
	entry->next = NULL;

	if( !l->head ){
		l->head = entry;
	}else{
		Entry* temp = l->head;
		while( true ){
			if( temp->next == NULL ) break;
			temp = temp->next;

		}
		temp->next = entry;
	}
	
}
void AttachFront(List* l, Entry* entry){
	l->count ++;

	entry->next = l->head;
	l->head = entry;
}

Entry* DetachFront(List *l){
	Entry* entry = l->head;
	l->head = l->head->next;
	l->count--;

	entry->next = NULL;
	return entry;
}

Entry* Split(char *str, int initial){
	static int pos = 0;
	int bufSize = 0;
	int old_pos = pos;
	char *buf = NULL;
	Entry *entry = (Entry*)malloc( sizeof(Entry) );
	entry->next = NULL;

	if( initial ){
		pos = 0;
		old_pos = pos;
	}

	if( strlen(str) <= pos ){
		return NULL;
	}

	if( '0'<= str[pos] && str[pos] <='9'){
		while( '0'<= str[pos] && str[pos] <='9' ){
			pos++;
		}

		int len = pos - old_pos;
		buf = (char*)malloc( sizeof(char)*len + 1);
		buf[len] = 0;
		for( int i=0; i <len; i++){
			buf[i] = str[old_pos++];
		}

		entry->el = buf;
		entry->type = 0;
	}else{
		// printf("[%d] %c %s\n", pos, str[2], str);
		buf = (char*)malloc( sizeof(char)*2 );
		buf[0] = str[pos++];
		buf[1] = 0;

		entry->el = buf;

		if( buf[0]=='+' || buf[0]=='-'){
			entry->type=1;
		}else if(buf[0]=='*' || buf[0]=='/'){
			entry->type=2;
		}else{ // ( )
			entry->type=3;
		}

	}

	return entry;
}

void CheckStack(List* stack, List* postfixList, Entry* tar){
	Entry *entry;
	while(true){
		if( stack->count == 0 || stack->head->type == 3 ) break;

		// printf("[%s %s]", stack->head->el, tar->el);

		if( stack->head->type >= tar->type ){
			entry = DetachFront(stack);
			AttachRear(postfixList, entry);
			if( entry->type == 1){
				break;
			}
		}else{
			break;
		}

	}
}

List* Conversion(char* buf){
	// printf("%lu\n", strlen(buf));
	List* infixList = MakeList();
	List* postfixList = MakeList();
	List* stack = MakeList();

	Entry* entry = Split(buf, 1);
		
	AttachRear(infixList, entry);
				
	while( (entry = Split(buf,0)) ){
		AttachRear(infixList, entry);		
	}
			// printf("fuck\n");
	// entry = infixList->head;
	// do{
	// 	printf("%s\n", entry->el);
	// }
	// while( (entry=entry->next));

	// printf("[%d]\n", infixList->count);
	while( infixList->count ){
		entry = DetachFront(infixList);
		// printf("[Test] %s\n", entry->el);

		switch( entry->type){
			case 0: //number
				// printf("Test %s\n", entry->el);
				AttachRear(postfixList, entry);
			
				break;
			case 1: // + -
				// printf("Test %s\n", entry->el);
				if( stack->count == 0 || strcmp(stack->head->el,"(")==0 ){
					
					AttachFront(stack, entry);
				}else{
					// if( stack->head->type >= entry->type){
						// Entry* temp  = DetachFront(stack);
						// AttachRear(postfixList, temp);
					// }

					CheckStack(stack, postfixList, entry);
					AttachFront(stack, entry);
				}
				break;
			case 2: // / *
				// printf("Test %s\n", entry->el);
				if( stack->count == 0 || strcmp(stack->head->el,"(")==0 ){
					AttachFront(stack, entry);
				}else{
					// if( stack->head->type == entry->type){
					// 	Entry* temp  = DetachFront(stack);
					// 	AttachRear(postfixList, temp);
					// }
					CheckStack(stack, postfixList, entry);
					AttachFront(stack, entry);
				}
				break;
			case 3: // ( )
				if( strcmp(entry->el, "(" ) == 0){
					// printf("Test %s\n", entry->el);
					AttachFront(stack, entry);
				}else{
					// printf("Test %s\n", entry->el);
					while(1){
						entry = DetachFront(stack);
						if( strcmp(entry->el, "(") == 0 ) break;
						AttachRear(postfixList, entry);
					}
				}
				break;
			default:
				break;
		} //end switch
	} //end while
	
	while( stack->count ){
			entry = DetachFront(stack);
			if( strcmp(entry->el, "(") > 0 )
				AttachRear(postfixList, entry);
			// stack->count--;
	}
	
	return postfixList;
}

int main(void){
	FILE *in, *out;
	char *buf=NULL;
	List* l = NULL;
	Entry *entry = NULL;
	int lineNUM;
	in = fopen("input.txt","rt");

	lineNUM = GetLineNum(in);
	printf("%d\n", lineNUM );


	for(int i =0; i<lineNUM ; i++){

		buf = GetOneLine(in);
		// printf("%s\n", buf);

		l = Conversion(buf);
			//printf("%s\n", buf);
		entry = l->head;

		do{
			printf("%s ", entry->el);
		}
		while( (entry=entry->next));

		printf("\n");
		free(buf);
		DestroyList(l);
	}
	

	// printf("[%d]\n", infixList->count);
	fclose(in);
	fclose(out);
	return 0;
}