中綴表達(dá)式和后綴表達(dá)式轉(zhuǎn)換的原理以及計(jì)算原理
1.中綴表達(dá)式的計(jì)算原理
規(guī)則：先計(jì)算高優(yōu)先級(jí)部分算式损话，優(yōu)先級(jí)由高到低，順序從左到右槽唾。
如：12 - （2 - 5）* 6 - 10 = 20
- 括號(hào)內(nèi)優(yōu)先級(jí)最高丧枪，表達(dá)式變?yōu)椋?2 - （-3）* 6 - 10
- 乘法優(yōu)先級(jí)高于加減，表達(dá)式變?yōu)椋?2 + 18 - 10
- 優(yōu)先級(jí)一樣庞萍，從左到右計(jì)算：20
2.后綴表達(dá)式的計(jì)算原理
規(guī)則：從左往右遍歷表達(dá)式的每個(gè)數(shù)字和符號(hào)拧烦，遇到數(shù)字就直接進(jìn)棧，遇到運(yùn)算符號(hào)就出棧兩個(gè)數(shù)字進(jìn)行計(jì)算钝计，將結(jié)果入棧恋博，最后獲得的數(shù)字就是結(jié)果。
如：12 - （2 - 5）* 6 - 10 的后綴表達(dá)式為：12 2 5 - 6 * - 10 -
- 12 2 5 都進(jìn)棧私恬，棧中有：12 2 5债沮；遇到 - ，2 5出棧計(jì)算得-3本鸣，將-3入棧疫衩，棧中有：12 -3。
- 將6進(jìn)棧永高，棧中有：12 -3 6；遇到 * 提针，-3 6出棧計(jì)算得-18命爬，將-18入棧，棧中有：12 -18辐脖。
- 遇到 - 饲宛，將12 -18出棧計(jì)算得30，將30入棧嗜价，棧中有：30艇抠。
- 遇到10幕庐，將10入棧，棧中有：30 10家淤；遇到 - 异剥，將30 10出棧，計(jì)算得：20絮重，即最終結(jié)果是20冤寿。
3.計(jì)算機(jī)中為什么用后綴表達(dá)式進(jìn)行計(jì)算？
? 計(jì)算機(jī)不像人一樣具有智慧青伤，它只是一臺(tái)執(zhí)行指令速度非扯搅快得機(jī)器。所以對(duì)于中綴表達(dá)式而言狠角，如果通過計(jì)算機(jī)來進(jìn)行計(jì)算号杠，那么它需要對(duì)中綴表達(dá)式進(jìn)行很多次重復(fù)的掃描，依優(yōu)先級(jí)得次序進(jìn)行計(jì)算丰歌，將會(huì)大大的降低計(jì)算效率姨蟋，所以聰明得科學(xué)家們想辦法把優(yōu)先級(jí)用某種東西抵消，讓計(jì)算機(jī)一種最簡(jiǎn)單的方式進(jìn)行計(jì)算动遭，從而節(jié)省計(jì)算資源芬探。
? 而恰好棧是一種非常好得抽象數(shù)據(jù)類型，棧中數(shù)據(jù)得進(jìn)出都在一端進(jìn)行厘惦，那么就營(yíng)造出了一種優(yōu)先級(jí)/特權(quán)的相似性質(zhì)偷仿，只要我是最后入棧的，那么第一個(gè)出棧的肯定也是我宵蕉。
? 并且酝静，表達(dá)式的計(jì)算一般都是兩個(gè)數(shù)，一個(gè)運(yùn)算符(暫不考慮一源操作符羡玛，因?yàn)橐辉\(yùn)算符也可以轉(zhuǎn)化成二元運(yùn)算符來計(jì)算别智，當(dāng)然這里的與或非啥的也要進(jìn)行一些嵌套)。所以我們天然的會(huì)想要用二叉樹進(jìn)行表示稼稿，而二叉樹有多種遍歷方式，二叉樹的中序遍歷就是表達(dá)式的中綴表示法，二叉樹的后序遍歷就是表達(dá)式的后綴表示法，當(dāng)然前序遍歷也是前綴表示法。
? 很顯然這三者的遍歷方式是同一個(gè)表達(dá)式在計(jì)算機(jī)中的不同遍歷方式，所以中綴表達(dá)式能夠計(jì)算，那么前后綴表達(dá)是也能進(jìn)行計(jì)算，并且由遍歷方式可以得出后綴表達(dá)式的計(jì)算原理（不討論前綴，因?yàn)榍熬Y和后綴是相互逆向的壹店，并且如果要計(jì)算，稍微復(fù)雜一些）。
? 而二叉樹的前中后序遍歷本就是一種借用棧來實(shí)現(xiàn)的敢辩，所以就可以找出中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的算法历葛，從而就可以大幅度的簡(jiǎn)化計(jì)算。
4.后綴表達(dá)式轉(zhuǎn)中綴表達(dá)式的步驟：
（0）初始化兩個(gè)空棧S1鸠天，S2。
（1）若取出的字符是操作數(shù)帐姻，則分析出完整的運(yùn)算數(shù)稠集，該操作數(shù)直接送入S2棧。
（2）若取出的字符是運(yùn)算符饥瓷，則將該運(yùn)算符與S1棧棧頂元素比較剥纷，如果該運(yùn)算符(不包括括號(hào)運(yùn)算符)優(yōu)先級(jí)高于S1棧棧頂運(yùn)算符（包括左括號(hào)）優(yōu)先級(jí)，則將該運(yùn)算符進(jìn)S1棧呢铆，否則晦鞋，將S1棧的棧頂運(yùn)算符彈出，送入S2棧中棺克，直至S1棧棧頂運(yùn)算符（包括左括號(hào)）低于（不包括等于）該運(yùn)算符優(yōu)先級(jí)時(shí)停止彈出運(yùn)算符悠垛，最后將該運(yùn)算符送入S1棧。
（3）若取出的字符是“（”娜谊，則直接送入S1棧頂确买。
（4）若取出的字符是“）”，則將距離S1棧棧頂最近的“（”之間的運(yùn)算符纱皆，逐個(gè)出棧湾趾，依次送入S2棧，此時(shí)拋棄“（”抹剩。
（5）重復(fù)上面的1~4步撑帖，直至處理完所有的輸入字符。
5.代碼實(shí)現(xiàn)如下（但是帶有一元操作符就不行澳眷，但是可以簡(jiǎn)單改一下胡嘿，遇到一元操作符添加0就可以實(shí)現(xiàn)了）：
#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;
}
