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

struct stack {
	int*bd; /* stack body */
	int pt; /* stack pointer */
	int mx; /* stack body size */
	char *id; /* stack identifier */
};
void error_id (char *frm, char *id)
{
	fprintf(stderr, frm, id);
	exit(1);
}
struct stack *newstack (int maxsize, char *name)
{
	struct stack *s;
	if ((s = (struct stack *)malloc(sizeof(struct stack))) == NULL)
		error_id("malloc for %s\n", name);
	if ((s->bd = (int *)malloc(maxsize * sizeof(int))) == NULL)
		error_id("malloc for %s's body\n", name);
	s->pt = -1;
	s->mx = maxsize;
	s->id = name;
	return s;
}

struct stack *push (int v, struct stack *s)
{
	if (++(s->pt) >= s->mx)
		error_id("%s overflows\n", s->id);
	s->bd[s->pt] = v;
	return s;
}
int pop (struct stack *s)
{
	if (s->pt < 0)
		error_id("empty %s is popped\n", s->id);
	return s->bd[(s->pt)--];
}
int top (struct stack *s)
{
	if (s->pt < 0)
		error_id("empty %s is referred\n", s->id);
	return s->bd[s->pt];
}
int isempty (struct stack *s)
{
	return (s->pt < 0);
}


#define MAX_STACK_SIZE 256
#define STACK_NAME "_my_stack"

void nfix2postfix ( char* nfix, char*postfix )
{
	char c ;
	struct stack* st ;

	// スタック生成
	st = newstack ( MAX_STACK_SIZE, STACK_NAME ) ;	

	for ( ;*nfix;nfix++ ){
		c = *nfix ;
		if(c==' '){// スペースは読み飛ばす
		} else if ('0' <= c && c <= '9'){//数字ならそのままバッファへ
			*postfix = c ;
			postfix++ ;
		} else if (c==')'){// ')'ならスタックの中から'('が見つかるまでpopしてバッファへ
			for (;;){
				c = pop(st) ;
				if (c=='('){
					break ;
				}
				else{
					*postfix = c ;
					postfix++ ;
				}
			}
		} else if ( c=='(' ){//'('ならスタックへ積む
			push(c, st) ;
		} else{// 演算子
			while(!isempty(st)){
				if ( (top(st)=='*'||top(st)=='/') 
					|| ((top(st)=='+'||top(st)=='-')&&(c=='+'||c=='-')) ){//スタックに何かが詰まれていて、スタックのトップの優先度が同じか高ければバッファへ
					*postfix = pop(st) ;
					postfix++ ;
				}else{
					break ;
				}
			}
			push(c, st) ;// スタックが空かトップの優先度が低ければスタックへ
		}
	}

	// スタックに残ってるものを全部バッファへ
	while(!isempty(st)){
		*postfix = pop(st) ;
		postfix++ ;
	}

	// 後始末
	free (st->bd) ;
	free (st) ;
}


int main ( void )
{	
	char nfix[256] = "(1 - 2) * 3 + 4 / 5" ;
	char postfix[256] ={0};

	//gets(nfix) ; // 標準入力する？

	nfix2postfix ( nfix, postfix ) ;

	printf ( "%s\n", nfix ) ;
	printf ( "%s\n", postfix ) ;

	return 0 ;
}

(1 - 2) * 3 + 4 / 5
12-3*45/+