C++详解 中缀表达式转化为后缀表达式

中缀表达式转化为后缀表达式算法思想细节
首先明确什么是中缀表达式，什么是后缀表达式。
中缀表达式是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（eg:3+4）。
附：中缀表达式不易被计算机处理。
后缀表达式，又称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行(不再考虑运算符的优先规则)。

转化思想：
首先明确中缀转化为后缀过程中，需要转化的部分。
转化内容分为两个部分运算数和运算符号。
运算数：可以分为正数和负数。也可以分为整数和小数。
运算符号：分为六种，包括加减乘除和左右括号。
特别注意：关于数字的处理要注意正负号以及加减的判别。

1. 括号分为左括号和右括号。左括号直接进栈但不输出，右括号直接开始出栈，直到遇到左括号为止。
2. 乘除运算在运算转化里处于高级运算的行列。在运算转化过程中，遇到乘除运算直接进栈。
3. 加减还是正负，This is a question！
   正负的条件：字符串的首字母为正负号。即str[0] = ±;或者正负号的前一个元素为(。eg:(+9)，(-9)。处理后应为：9，-9。
   加减的条件：不为正负即为加减。
4. 数字或小数点直接输出，不影响栈内元素。

代码如下：

#include<iostream>
#include<ctype.h>
#include<assert.h>
using namespace std;

#define length 125

typedef struct{
	char *begin;
	char *end;
	int StackSize;
}SqStack;

void InitStack(SqStack *Q)
{
	Q->begin = new char[length];
	assert(Q->begin !=NULL);
	Q->end = Q->begin;
	Q->StackSize = length;
}

void InitStr(char str[])
{
	for(int i = 0;i < length;i++){
		str[i] = '\0';
	}
}

void PushStack(SqStack *Q,char c)
{
	*Q->end++ = c;
}

int StackLength(SqStack *Q)
{
	return (Q->end - Q->begin);
}

void PopStack(SqStack *Q,char *c)
{
	*c = *--Q->end;
}

void zhan()
{
	SqStack Q;
	InitStack(&Q);
	char str[length];
	InitStr(str);
	cin >> str;
	char c;
	for(int i = 0;str[i] != '\0';++i){ 
		if(isdigit(str[i]) || str[i]=='.') cout << str[i];
		else if(str[i] == '*' || str[i] == '/' || str[i] == '(') {if(str[i] != '(') cout << " ";PushStack(&Q,str[i]);}
		else if(str[i] == '+' || str[i] == '-'){
			if(!StackLength(&Q) && i != 0) {cout << " ";PushStack(&Q,str[i]);}
			else{
				if(i == 0) {
					if(str[i] == '-') cout << str[i];
					continue;
				}
				PopStack(&Q,&c);
				PushStack(&Q,c);
				if(c == '('){
					if(str[i-1] == '(') {if(str[i] == '-') cout << str[i];} 
					else {cout << " ";PushStack(&Q,str[i]);}
				}
				else{
					cout << " ";
					do{
						PopStack(&Q,&c);
						if(c == '(') break;
						else cout << c << " ";
					}while(StackLength(&Q) && c != '(');
					if(c == '(') PushStack(&Q,c);
					PushStack(&Q,str[i]);
				}
			}
		}
		else if(str[i] == ')')
		{
			PopStack(&Q,&c);
			if(c == '(') continue;
			do{
				cout << " " << c;
				PopStack(&Q,&c);
			}while(c != '(');
		}
	}
	if(StackLength(&Q)) cout << " ";
	while(StackLength(&Q)){
		PopStack(&Q,&c);
		cout << c;
		if(StackLength(&Q) != 0) cout << " ";
	 }
}


int main()
{
	zhan();
	return 0;
}

PTA提交屡次出错的原因分析：

• 小数点未经处理。
• 正负号处理不当。应注意(+9)->9,(-9)->-9;
• 括号的处理应注意。若字符串元素不为右括号，在依次弹栈过程中，应注意将左括号再次放回栈中。若字符串元素为右括号，在弹出左括号时，不做处理。接着处理后续元素。

感悟：

• StackLength()函数也可改为StackIsEmpty()函数。
• assert()函数可以用来快速判断，让程序终止。
• 在空间的处理上还有可以改进的方向。可以通过空间的申请释放，考虑如何提高字符串的处理长度，让字符串的处理长度达到任意值。