中缀表达式和后缀表达式转换的原理以及计算原理
1.中缀表达式的计算原理
规则：先计算高优先级部分算式，优先级由高到低，顺序从左到右。
如：12 - （2 - 5）* 6 - 10 = 20
- 括号内优先级最高，表达式变为：12 - （-3）* 6 - 10
- 乘法优先级高于加减，表达式变为：12 + 18 - 10
- 优先级一样，从左到右计算：20
2.后缀表达式的计算原理
规则：从左往右遍历表达式的每个数字和符号，遇到数字就直接进栈，遇到运算符号就出栈两个数字进行计算，将结果入栈，最后获得的数字就是结果。
如：12 - （2 - 5）* 6 - 10 的后缀表达式为：12 2 5 - 6 * - 10 -
- 12 2 5 都进栈，栈中有：12 2 5；遇到 - ，2 5出栈计算得-3，将-3入栈，栈中有：12 -3。
- 将6进栈，栈中有：12 -3 6；遇到 * ，-3 6出栈计算得-18，将-18入栈，栈中有：12 -18。
- 遇到 - ，将12 -18出栈计算得30，将30入栈，栈中有：30。
- 遇到10，将10入栈，栈中有：30 10；遇到 - ，将30 10出栈，计算得：20，即最终结果是20。
3.计算机中为什么用后缀表达式进行计算？
计算机不像人一样具有智慧，它只是一台执行指令速度非常快得机器。所以对于中缀表达式而言，如果通过计算机来进行计算，那么它需要对中缀表达式进行很多次重复的扫描，依优先级得次序进行计算，将会大大的降低计算效率，所以聪明得科学家们想办法把优先级用某种东西抵消，让计算机一种最简单的方式进行计算，从而节省计算资源。
而恰好栈是一种非常好得抽象数据类型，栈中数据得进出都在一端进行，那么就营造出了一种优先级/特权的相似性质，只要我是最后入栈的，那么第一个出栈的肯定也是我。
并且，表达式的计算一般都是两个数，一个运算符(暂不考虑一源操作符，因为一元运算符也可以转化成二元运算符来计算，当然这里的与或非啥的也要进行一些嵌套)。所以我们天然的会想要用二叉树进行表示，而二叉树有多种遍历方式，二叉树的中序遍历就是表达式的中缀表示法，二叉树的后序遍历就是表达式的后缀表示法，当然前序遍历也是前缀表示法。
很显然这三者的遍历方式是同一个表达式在计算机中的不同遍历方式，所以中缀表达式能够计算，那么前后缀表达是也能进行计算，并且由遍历方式可以得出后缀表达式的计算原理（不讨论前缀，因为前缀和后缀是相互逆向的，并且如果要计算，稍微复杂一些）。
而二叉树的前中后序遍历本就是一种借用栈来实现的，所以就可以找出中缀表达式转换成后缀表达式的算法，从而就可以大幅度的简化计算。
4.后缀表达式转中缀表达式的步骤：
（0）初始化两个空栈S1，S2。
（1）若取出的字符是操作数，则分析出完整的运算数，该操作数直接送入S2栈。
（2）若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符(不包括括号运算符)优先级高于S1栈栈顶运算符（包括左括号）优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符（包括左括号）低于（不包括等于）该运算符优先级时停止弹出运算符，最后将该运算符送入S1栈。
（3）若取出的字符是“（”，则直接送入S1栈顶。
（4）若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。
（5）重复上面的1~4步，直至处理完所有的输入字符。
5.代码实现如下（但是带有一元操作符就不行，但是可以简单改一下，遇到一元操作符添加0就可以实现了）：
#include <bits/stdc++.h>
using namespace std;
const int MaxSize = 50;
struct SNode {
string Data[MaxSize];
int Top;
};
struct LNode {
string Data[MaxSize];
int Front;
int Rear;
};
using Stack = struct SNode*;
using List = struct LNode*;
Stack CreateStack()
{
Stack S = new (struct SNode);
S->Top = -1;
return S;
}
bool StackIsFull(Stack S)
{
return S->Top == MaxSize - 1;
}
bool StackIsEmpty(Stack S)
{
return S->Top == -1;
}
void Push(Stack S, const string &str)
{
if (StackIsFull(S)) {
cout << "堆栈已满！" << endl;
return;
}
S->Data[++S->Top] = str;
}
string Pop(Stack S)
{
if (StackIsEmpty(S)) {
return "Stack Is Empty!";
}
return S->Data[S->Top--];
}
List CreateList()
{
List L = new (struct LNode);
L->Front = -1;
L->Rear = -1;
return L;
}
bool ListIsFull(List L)
{
return (L->Rear == (L->Front - 1 + MaxSize) % MaxSize);
}
bool ListIsEmpty(List L)
{
return (L->Front == L->Rear);
}
void Add(List L, const string str)
{
if (ListIsFull(L)) {
cout << "List Is Full" << endl;
return;
}
L->Rear = (L->Rear + 1) % MaxSize;
L->Data[L->Rear] = str;
}
string Delete(List L)
{
if (ListIsEmpty(L)) {
return "List Is Empty!";
}
L->Front = (L->Front + 1) % MaxSize;
return L->Data[L->Front];
}
bool iSOperator(string str)
{
if (str == "+" || str == "-" || str == "/" || str == "*") {
return true;
}
return false;
}
string compute(string s1, string s2, string op)
{
int a = stoi(s1);
int b = stoi(s2);
if (op == "+") {
return to_string(b + a);
} else if (op == "-") {
return to_string(b - a);
} else if (op == "*") {
return to_string(b * a);
} else {
return to_string(b / a);
}
}
vector<string> PreTreatment(string str)
{
vector<string> res;
for (int i = 0; i <= str.size() - 1; ) {
if (str[i] == '(' || str[i] == ')' || str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/') {
if (i == 0) {
if (str[i] == '-') {
int j = i + 1;
for ( ; j <= str.size() - 1; ++j) {
if (str[j] == '(' || str[j] == ')' || str[j] == '+' || str[j] == '-' || str[j] == '*' || str[j] == '/') {
break;
}
}
string s = "";
for (; i <= j - 1; ++i) {
s += str[i];
}
res.push_back(s);
} else if (str[i] == '+') {
i += 1;
int j = i + 1;
for ( ; j <= str.size() - 1; ++j) {
if (str[j] == '(' || str[j] == ')' || str[j] == '+' || str[j] == '-' || str[j] == '*' || str[j] == '/') {
break;
}
}
string s = "";
for (; i <= j - 1; ++i) {
s += str[i];
}
res.push_back(s);
} else if (str[i] == '(') {
int j = i + 1;
if (str[j] == '-') {
i = j;
for (j += 1; j <= str.size() - 1; ++j) {
if (str[j] == ')') {
break;
}
}
string s = "";
for (; i <= j - 1; ++i) {
s += str[i];
}
res.push_back(s);
} else if (str[j] == '+') {
i = j + 1;
for (j += 1; j <= str.size() - 1; ++j) {
if (str[j] == ')') {
break;
}
}
string s = "";
for (; i <= j - 1; ++i) {
s += str[i];
}
res.push_back(s);
} else {
string s = "";
s += str[i];
res.push_back(s);
++i;
}
}
} else if (str[i] == '(') {
int j = i + 1;
if (str[j] == '-') {
i = j;
for (j += 1; j <= str.size() - 1; ++j) {
if (str[j] == ')') {
break;
}
}
string s = "";
for (; i <= j - 1; ++i) {
s += str[i];
}
res.push_back(s);
} else if (str[j] == '+') {
i = j + 1;
for (j += 1; j <= str.size() - 1; ++j) {
if (str[j] == ')') {
break;
}
}
string s = "";
for (; i <= j - 1; ++i) {
s += str[i];
}
res.push_back(s);
} else {
string s = "";
s += str[i];
res.push_back(s);
++i;
}
} else {
string s = "";
s += str[i];
res.push_back(s);
++i;
}
} else if (str[i] <= '9' && str[i] >= '0') {
int j = i + 1;
for ( ; j <= str.size() - 1; ++j) {
if (str[j] == '(' || str[j] == ')' || str[j] == '+' || str[j] == '-' || str[j] == '*' || str[j] == '/') {
break;
}
}
string s = "";
for (; i <= j - 1; ++i) {
s += str[i];
}
res.push_back(s);
}
}
return res;
}
int main ()
{
string in;
float res = 0;
//cin >> expression;
getline(cin, in);
Stack opStack = CreateStack();
Stack numStack = CreateStack();
List reversepolish = CreateList();
vector<string> expression = PreTreatment(in);
int len = expression.size();
for (int i = 0; i <= len - 1; ++i) {
string str { expression[i] };
if (expression[i] == "(") {
Push(opStack, str);
} else if (expression[i] == ")") {
while (!StackIsEmpty(opStack)) {
string op = Pop(opStack);
if (op == "(") {
break;
} else {
Add(reversepolish, op);
if (iSOperator(op)) {
string a = Pop(numStack);
string b = Pop(numStack);
string c = compute(a, b, op);
Push(numStack, c);
} else {
Push(numStack, op);
}
}
}
} else if (expression[i] == "+" || expression[i] == "-" || expression[i] == "/" || expression[i] == "*"){
while (!StackIsEmpty(opStack)) {
string op = Pop(opStack);
if (op == "(") {
Push(opStack, op);
Push(opStack, str);
break;
} else if ((op == "+" || op == "-") && (str == "*" || str == "/")) {
Push(opStack, op);
Push(opStack, str);
break;
} else {
Add(reversepolish, op);
if (iSOperator(op)) {
string a = Pop(numStack);
string b = Pop(numStack);
string c = compute(a, b, op);
Push(numStack, c);
} else {
Push(numStack, op);
}
}
}
if(StackIsEmpty(opStack)) {
Push(opStack, str);
}
} else {
Add(reversepolish, str);
if (iSOperator(str)) {
string a = Pop(numStack);
string b = Pop(numStack);
string c = compute(a, b, str);
Push(numStack, c);
} else {
Push(numStack, str);
}
}
}
while(!StackIsEmpty(opStack)) {
string str = Pop(opStack);
Add(reversepolish, str);
if (iSOperator(str)) {
string a = Pop(numStack);
string b = Pop(numStack);
string c = compute(a, b, str);
Push(numStack, c);
} else {
Push(numStack, str);
}
}
int i = 1;
while (!ListIsEmpty(reversepolish)) {
string out = Delete(reversepolish);
if (i == 1) {
cout << out;
} else {
cout << " " << out;
}
++i;
}
cout << " = "<< Pop(numStack) << endl;
return 0;
}
image.png
