栈实现中缀表达式转后缀表达式

C语言版中缀表达式转后缀表达式

    I    通常，用户输入的表达是为中缀表达式，通过算法，将中缀表达式转化为后缀表达式，然后利用栈存储操作数，遇到operator，弹出栈中的操作数进行相应的运算后再圧栈，直至表达式运算完成或出错退出。

    

     II   利用“栈”将中缀表达式转化为后缀表达式算法：

        根据各种运算的运算符的优先级，优先级表格：

操作符ch	#	(	*、/、%	+、-	)
Isp	0	1	5	3	6
Icp	0	6	4	2	1

    III    扫描中缀表达式，将它转化为后缀表达式的算法描述：

        1、 操作符栈初始化，将结束符“#”进栈。然后读入中缀表达式字符流的首字符ch；

        2、 I）若ch为操作数，直接输出，读下一字符；

               II）若ch是操作符，比较ch的优先级icp与当前栈顶操作符op的优先级isp:

                    If  icp(ch) > isp(op)  then  令ch进栈，读入下一个字符；

                    If  icp(ch) < isp(op)  then  弹栈并输出

                    If  icp(ch) == isp(op) then  弹栈但不输出，若退出的是“（”号则读入下一个字符ch。

        3、 算法结束，输出序列即为所求的后缀表达式。

    IV 算法C语言实现

//============================================================================
// Name        : fixTransform.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
//============================================================================

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

#define stkSize 20
#define maxSize 30

int isp(char op){
	switch(op){
	case '#' : return 0; break;
	case '(' : return 1; break;
	case '*' : return 5; break;
	case '/' : return 5; break;
	case '+' : return 3; break;
	case '-' : return 3; break;
	case ')' : return 6; break;
	default : return -1;
	}
}

int icp(char op){
	switch(op){
	case '#' : return 0; break;
	case '(' : return 6; break;
	case '*' : return 4; break;
	case '/' : return 4; break;
	case '+' : return 2; break;
	case '-' : return 2; break;
	case ')' : return 1; break;
	default : return -1;
	}
}

/**
 * 将中缀表达式in[]转化为后缀表达式post[]
 */
void infix_to_postfix(char in[], char post[]){
	char optr[stkSize];
	int top = -1;
	char ch, topOp, op;
	int i = 0, j = 0;

	//初始化符号栈
	optr[++ top] = '#';

	ch = in[i ++];
	while(-1 != top || '#' != ch){
		if(ch >= '0' && ch <= '9'){
			post[j ++] = ch;
			ch = in[i ++];
		}
		else {
			topOp = optr[top];
			if(icp(ch) > isp(topOp)){
				optr[++ top] = ch;
				ch = in[i ++];
			} else if(icp(ch) < isp(topOp)){
				op = optr[top --];
				post[j ++] = op;
			}
			else{
				op = optr[top --];
				if('(' == op){
					ch = in[i ++];	//消括号
				}
			}
		}
	}
	post[j] = '#';
}


int main() {
	char in[maxSize] = "5+9*(6-4)-9/3#\0", post[maxSize];
	for(int i = 0; '#' != in[i]; i ++){
		printf("%c", in[i]);
	}
	printf("\n");
	infix_to_postfix(in, post);
	for(int i = 0; '#' != post[i]; i ++){
		printf("%c", post[i]);
	}
	printf("\n");
	return EXIT_SUCCESS;
}

        运行结果截图：

望每天进步一点，