数据结构测试--表达式转换（中缀转化为后缀）

7-1 表达式转换 (25 分)

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式:
输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。

输出格式:
在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。

输入样例:
2+3*(7-4)+8/4
输出样例:
2 3 7 4 - * + 8 4 / +、
找来别人的方法。
将中缀表达式“1+((2+3)*4)-5”转换为前缀表达式。

（1）构建两个栈，一个存运算符一个存操作数。运算符（以括号分界点）在栈内遵循越往栈顶优先级不降低的原则排序。

（2）从右往左扫描中缀式表达式，从右边第一个字符开始判断。

如果当前字符是数字，则分配到数字串的结尾并将数字串直接输出。

如果是运算符，则比较优先级。如果当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时，直接入栈)，则将运算符直接入栈；否则将栈顶运 算符出栈并输出，直到当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶元素是括号直接入栈)，再将当前运算符入栈。如果是括号，则根据括号的 方向进行处理。如果是括号直接入栈；否则，遇右括号前将所有的运算符全部出栈并输出，遇右括号后将左右的两括号一起删除。

（3）重复上述操作(2)直至扫描结束，将栈内剩余运算符全部出栈并输出，再将缀输出字符串。中缀表达式就变成了前缀表达式了。

#include<cstdio>
#include<stdlib.h> 
#include<string.h> 
#define initsize 20
#define changesize 10
//这里注意一点，书上是伪代码，不一定能运行，坑死我了。 
struct stack{
	char *base;
	char *top;
	int stacksize;
}; 
stack fuhao;
//这个栈的初始化有一点知识我给遗忘了，就是我一开始以为我形参写成stack &a，
//那么我直接传入一个地址就行了，然后我又以为a成了指针。。。。（这里a就能直接当变量用了） 
// 其实是当我形参是数组的时候，int a[]这种形式的时候，我的a才是弱化为了一个指针。
//如果是单个变量传入的话，那么形参为&a时候就可以直接用变量了，如果是*a，那么就当成指针用就好了。 
void initstack(stack* a){
	a->base=(char *)malloc(initsize*sizeof(char));
	a->top=a->base;
	a->stacksize=initsize;
}
void push(char a){
	if(fuhao.top-fuhao.base>=fuhao.stacksize){
		fuhao.base=(char *)realloc(fuhao.base,(fuhao.stacksize+changesize)*sizeof(char));
		fuhao.top=fuhao.base+fuhao.stacksize;
		fuhao.stacksize+=changesize;
	}
	*fuhao.top++=a;
}
 
char pop(){
	if(fuhao.top==fuhao.base){
		printf("空了");
	}
	else {
		return *(--fuhao.top);
	}
}
//构建compare函数的时候由于整体就没考虑清楚，导致出了一些错误。
//这里面分的有一些细了，一个是不存直接打印，一个是直接无脑存，一个是前面符号优先级大，取出优先级大的之后再存，另外一个是括号的特殊性， 
int compare(char a){
	if(a>='0'&&a<='9')return 0;
	if(fuhao.base==fuhao.top)return 1;
	else if( a=='(') return 1;
	else if(a == ')') return 2;
	else {
		switch(*(fuhao.top-1)){
			case '*':
			case '/':
				return 3;
			case '+':
			case '-':
				switch(a){
					case '*':
					case '/':
						return 1;
					case '+':
					case '-':
						return 3;
				}
				default: return 1;
		}
	}
}
int main(){
	char input[30];
	scanf("%s",input);
	initstack(&fuhao);
	int len=strlen(input);
	for(int i=0;i<len;i++){
		switch(compare(input[i])){
			case 1:{
				push(input[i]);
				break;
			}
			case 0:{
				printf("%c ",input[i]);
				break;
			}
			case 2:{
				char a='0';
				while(a!='('){
					a=pop();
					if(a!='(') {
						printf("%c ",a);
					}
				}
				break;
			}
			case 3:{
				printf("%c ",pop());
				while(compare(input[i])==3){
					printf("%c ",pop());
				}
				push(input[i]);
				break;
			}
		}
	}
	while(fuhao.base!=fuhao.top){
		printf("%c ",*(--fuhao.top));
	}
}

这个题就到这里里了，一个是函数传参的时候忘了很多，另外一个是逻辑一开始就没搞透，自己写伪代码的时候没有考虑全面。应该是自己在纸上的伪代码写出来以后，然后再验证一下题目中的输入。