intopost.c

该文件夹中包含了大部分经典的算法的源程序代码

/* file name: intopost.c                */
/*将数学式子由中序表达式转为后序表达式*/

#include <stdio.h>
#define MAX 20

void infix_to_postfix(char [], int);   /* 由中序转后序函数 */
int compare(char, char);  /* 比较两个运算符函数 */

/* 在中序表达式队列及暂存堆栈中，运算符的优先权表，其优先值为INDEX/2 */
char infix_priority[9] = {'#', ')', '+', '-', '*', '/', '^', ' ', '('};
char stack_priority[8] = {'#', '(', '+', '-', '*', '/', '^', ' '};
void main(void)
{
	int rear = -1;
	char infix_q[MAX]; /* 存储使用者数入中序式的队列 */
	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] = '#';   /*于队列结束时插入#为结束符号 */
	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] = '#';  /* 于堆栈最底下插入#为结束符号 */
	for(ctr = 0; ctr <= rear; ctr++)
	{
		switch(infix_q[ctr])
		{
			/* 输入为)，则应输出堆栈内运算符，直到堆栈内为（*/
			case ')':
				while(stack_t[top] != '(')
					printf("%c", stack_t[top--]);
				top--;
				break;
			/* 输入为#，则将堆栈内还未输出的运算符输出 */
			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;
		}
	}
}

/* 比较两运算符优先权，若输入运算符小于堆栈中运算符，则返回值为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;
}