后缀表达式：后缀表达式，又称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。（抄自百度百科） 说到后缀表达式就不得不说中缀表达式了，中缀表达式就是我们最常见的表达式即运算符在两个操作数中间，运算优先级由运算符（包括括号）来决定，例如7+3*(8+1)-4/2. 在来讲一下中缀表达式转后缀表达式的方法： 首先我们需要有一个放符号的地方，一下 从左往右开始扫描 1.如果遇到数字： 就加入到后缀表达式中 2.如果遇到符号： 若为非括号（‘(’或‘)’）判断该符号与栈顶符号的优先级，若该符号高于栈顶符号，则入栈，否则栈顶元素依此出栈；并加入到后缀表达式中。 若为‘(’则直接入栈。 若为‘)’则栈顶元素出栈，并加入到后缀表达式中，直到遇到‘)’为止。
根据上边写的“7+3*(8+1)-4/2”转换后缀表达式的操作步骤
后缀表达式栈77+7 3+7 3+ *7 3 8+ * (7 3 8+ * ( +7 3 8 1+ * ( +7 3 8 1 ++ *7 3 8 1 + * +-7 3 8 1 + * + 4-7 3 8 1 + * + 4- /7 3 8 1 + * + 4 2- /7 3 8 1 + * + 4 2 / -代码很垃圾，不值得参考（后面会调整）
#include<iostream> using namespace std; struct Node { Node *Next; char Data; }; bool IsHigh(char c_Top, char c_Cur) { if (c_Top == 0) return false; if (c_Top == '(') return true; if (c_Cur == ')')return true; if ((c_Top == '-' ||c_Top == '+')&&(c_Cur == '+' || c_Cur == '-')) return true; if ((c_Top == '*' || c_Top == '/')&& c_Cur != '(')return true; return false; } Node *AddNode(Node *Head,char Data) { Node *Temp = (Node *)malloc(sizeof(Node)); Temp->Next = Head; Temp->Data = Data; return Temp; } Node *GetNode(Node *Head, char &data) { if (Head == NULL) { data = 0; return Head; } data = Head->Data; Node *Temp = Head->Next; free(Head); return Temp; } int main() { char *Str = (char *)malloc(sizeof(char) * 512); Node *Head = NULL; while (cin >> Str) { char *TempStr = (char *)malloc(sizeof(char) * 512); int nTempCount = 0; memset(TempStr, 0X00, sizeof(char) * 512); for (int i = 0; i < strlen(Str); i++) { if (Str[i] >= '0' && Str[i] <= '9') { TempStr[nTempCount++] = Str[i]; } else { while (true) { char Temp = Head != NULL ? Head->Data : 0; int Mark = 0; if (IsHigh(Temp, Str[i])) { Head = GetNode(Head, Temp); if (Str[i] == ')') { Mark++; } if (Temp != '(') { TempStr[nTempCount++] = Temp; } else if(Temp == '(') { if (Mark == 0) { Head = AddNode(Head, Temp); } Mark--; break; } } else { break; } } if (Str[i] != ')') { Head = AddNode(Head, Str[i]); } } } while (Head != NULL) { char Temp = 0; Head = GetNode(Head, Temp); if (Temp != 0) { TempStr[nTempCount++] = Temp; } else { break; } } cout << TempStr << endl; } }