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

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

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

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

代码如下：

#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()函数可以用来快速判断，让程序终止。在空间的处理上还有可以改进的方向。可以通过空间的申请释放，考虑如何提高字符串的处理长度，让字符串的处理长度达到任意值。