一.定義
逆波蘭式，又稱后綴表達(dá)式，指的是操作符在其所控制的操作數(shù)后面的表達(dá)式。
舉個例子，1 + 2 * 3 - 4這個表達(dá)式是我們熟悉的中綴表達(dá)式，那么其所對應(yīng)的后綴表達(dá)式為：1 2 3 * + 4 -。
再來個復(fù)雜的例子：1 * (2 + 3) / 5 - 4 / 2其對應(yīng)的后綴表達(dá)式為：1 2 3 + * 5 / 4 2 / -（其中括號由于只是提升表達(dá)式優(yōu)先級的作用，因此不放入后綴表達(dá)式中）。
二.逆波蘭式的意義
為什么要將看似簡單的中綴表達(dá)式轉(zhuǎn)換為復(fù)雜的逆波蘭式，原因就在于這個簡單是相對我們?nèi)祟惖乃季S結(jié)構(gòu)來說的，對計算機(jī)而言中序表達(dá)式是非常復(fù)雜的結(jié)構(gòu)。相對的，逆波蘭式在計算機(jī)看來卻是比較簡單易懂的結(jié)構(gòu)。因為計算機(jī)普遍采用的內(nèi)存結(jié)構(gòu)是棧式結(jié)構(gòu)，它執(zhí)行先進(jìn)后出的順序。
三.逆波蘭式的實現(xiàn)
1.方法
（1）中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式
對于給出的中綴表達(dá)式，如何將其轉(zhuǎn)化為后綴表達(dá)式呢？
第一，若遇到操作數(shù)則直接輸出/存儲。
第二，遇到操作符，若此時棧為空或者操作符優(yōu)先級高于棧頂，則入棧。
第三，若操作符的優(yōu)先級低于或者等于棧頂，則出棧直至棧空或者優(yōu)先級低于該操作符。
第四，遇到"(",其后的所有操作符（直至遇到")"）按上述操作入棧或出棧；當(dāng)遇到")‘時，將"("頂上的所有操作符出棧。
（2）由后綴表達(dá)式計算結(jié)果
第一，遇到操作數(shù)則入棧。
第二，遇到操作符則將棧頂?shù)膬蓚€操作數(shù)出棧，其中第一個數(shù)為右操作數(shù)，第二個數(shù)為左操作數(shù)。
第三，計算結(jié)果并將計算的結(jié)果入棧。
第四，最后棧頂?shù)慕Y(jié)果即為所計算的結(jié)果。
2.代碼實現(xiàn)
#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;
string trans(string& s)
{
string operand;
stack<char> Operator;
int flag = 0;//記錄括號優(yōu)先級
for (const auto& e : s)
{
if (e == "(")
{
Operator.push(e);
flag = 1;
continue;
}
if (e == ")")
{
flag = 0;
while (Operator.top() != "(")
{
operand.push_back(Operator.top());
Operator.pop();
}
Operator.pop();
continue;
}
//操作符
if (e == "+" || e == "-" || e == "*" || e == "/")
{
if (flag == 1)
{
if (Operator.top() == "(")
{
Operator.push(e);
}
else if ((e == "*" || e == "/") && (Operator.top() == "+" || Operator.top() == "-"))
{
Operator.push(e);
}
else//操作符的優(yōu)先級低于或等于棧頂操作符則出棧，直至遇到"("
{
while (Operator.top() != "(")
{
operand.push_back(Operator.top());
Operator.pop();
}
Operator.push(e);
}
}
else if (Operator.empty())//棧空就入棧
{
Operator.push(e);
}
//操作符的優(yōu)先級高于棧頂操作符，入棧
else if ((e == "*" || e == "/") && (Operator.top() == "+" || Operator.top() == "-"))
{
Operator.push(e);
}
else//操作符的優(yōu)先級低于或等于棧頂操作符則出棧，直至棧空或者優(yōu)先級高于棧頂操作符
{
while (!Operator.empty())
{
operand.push_back(Operator.top());
Operator.pop();
}
Operator.push(e);
}
}
//操作數(shù)
else
{
operand.push_back(e);
}
}
while (!Operator.empty())
{
operand.push_back(Operator.top());
Operator.pop();
}
return operand;
}
int evalRPN(const string& s)
{
stack<char> operand;
int left = 0, right = 0;
for (const auto& e : s)
{
if (e == "+" || e == "-" || e == "*" || e == "/")
{
switch (e)
{
case "+":
right = operand.top();
operand.pop();
left = operand.top();
operand.pop();
operand.push(left + right);
break;
case "-":
right = operand.top();
operand.pop();
left = operand.top();
operand.pop();
operand.push(left - right);
break;
case "*":
right = operand.top();
operand.pop();
left = operand.top();
operand.pop();
operand.push(left * right);
break;
case "/":
right = operand.top();
operand.pop();
left = operand.top();
operand.pop();
operand.push(left / right);
break;
}
}
else//操作數(shù)
{
operand.push(e - "0");
}
}
return operand.top();
}
int RPN(const string& str)
{
//1.中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式
string s(str);
s = trans(s);
//2.后綴表達(dá)式計算答案
return evalRPN(s);
}
int main()
{
string s("1*(2*3+5)/5-4/2");
int ret = RPN(s);
cout << "ret:" << ret << endl;
return 0;
}
結(jié)果:
到此這篇關(guān)于C++棧實現(xiàn)逆波蘭式的應(yīng)用的文章就介紹到這了,更多相關(guān)C++ 逆波蘭式內(nèi)容請搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://blog.csdn.net/love_guanghui/article/details/121526718
