/* file name: intopost.c                */
/*將數(shù)學式子由中序表達式轉(zhuǎn)為后序表達式*/

#include <stdio.h>
#define MAX 20

void infix_to_postfix(char [], int);   /* 由中序轉(zhuǎn)后序函數(shù) */
int compare(char, char);  /* 比較兩個運算符函數(shù) */

/* 在中序表達式隊列及暫存堆棧中，運算符的優(yōu)先權(quán)表，其優(yōu)先值為INDEX/2 */
char infix_priority[9] = {'#', ')', '+', '-', '*', '/', '^', ' ', '('};
char stack_priority[8] = {'#', '(', '+', '-', '*', '/', '^', ' '};
void main(void)
{
	int rear = -1;
	char infix_q[MAX]; /* 存儲使用者數(shù)入中序式的隊列 */
	printf("*********************************\n");
	printf("      -- Usable operator --\n");
	printf(" ^: Exponentiation\n");
	printf(" *: Multiply      /: Divide\n");
	printf(" +: Add           -: Subtraction\n");
	printf(" (: Left Brace    ): Right Brace\n");
	printf("*********************************\n");
	printf("Please enter infix expression: ");
	while(infix_q[rear] != '\n')
		infix_q[++rear] = getchar();
	infix_q[rear] = '#';   /*于隊列結(jié)束時插入#為結(jié)束符號 */
	printf("Postfix expression: ");
	infix_to_postfix(infix_q, rear);
	printf("\n");
}

void infix_to_postfix(char infix_q[], int rear)
{
	int top = 0, ctr, tag=1;
	char stack_t[MAX];  /* 用以存儲還不必輸出的運算符 */
	stack_t[top] = '#';  /* 于堆棧最底下插入#為結(jié)束符號 */
	for(ctr = 0; ctr <= rear; ctr++)
	{
		switch(infix_q[ctr])
		{
			/* 輸入為)，則應(yīng)輸出堆棧內(nèi)運算符，直到堆棧內(nèi)為（*/
			case ')':
				while(stack_t[top] != '(')
					printf("%c", stack_t[top--]);
				top--;
				break;
			/* 輸入為#，則將堆棧內(nèi)還未輸出的運算符輸出 */
			case '#':
				while(stack_t[top] != '#')
					printf("%c", stack_t[top--]);
				break;
			/* 輸入為運算符，若小于TOP在堆棧中所指運算符，則將堆棧
               所指運算符輸出，若大于等于TOP在堆棧中所指運算符，則將
               輸入的運算符放入堆棧中 */
			case '(':
			case '^':
			case '*':
			case '/':
				while(compare(stack_t[top], infix_q[ctr]))
					printf("%c", stack_t[top--]);
				stack_t[++top] = infix_q[ctr];
				tag=1;
				break;
			case '+':
			case '-':
				if(tag==1)
				{
				    stack_t[++top] = infix_q[ctr];
			        tag=2;
				}
			    else
				{
				    while(compare(stack_t[top], infix_q[ctr]))
					    printf("%c", stack_t[top--]);
				    stack_t[++top] = infix_q[ctr];
				    tag=1;
				}
				break;
			/*輸入為運算符，則直接輸出 */
			default :
				printf("%c", infix_q[ctr]);
			    if(tag==2)
				    printf("%c",stack_t[top--]);
				tag=0;
				break;
		}
	}
}

/* 比較兩運算符優(yōu)先權(quán)，若輸入運算符小于堆棧中運算符，則返回值為1，否則返回值為0 */
int compare(char stack_o, char infix_o)
{
	int index_s = 0, index_i = 0;
	while(stack_priority[index_s] != stack_o)
		index_s++;
	while(infix_priority[index_i] != infix_o)
		index_i++;
	return index_s/2 >= index_i/2 ? 1 : 0;
}