#include
#include
#include
#include
using?namespace?std;

//判斷是否為括號
bool?isPra（char?c）
{
????if（c==‘（‘||c==‘）‘）
????????return?true;
????else
????????return?false;
}

//獲得符號的優(yōu)先性
int?getPri（char?c）
{
????switch（c）
????{
????case?‘+‘:
????case?‘-‘:
????????return?0;???//如果是加減，返回0
????????break;
????case?‘*‘:
????case?‘/‘:
????????return?1;???//如果是乘除，返回1
????????break;
????case?‘（‘:
????case?‘）‘:
????????return?-1;??//注意，這里將括號設(shè)為最低優(yōu)先級，因此括號不會被彈出，除非遇到右括號
????????break;
?????}
}

//判斷符號的優(yōu)先性
void?check（char?c?stack&?coll2?deque&?coll3）
{
????if（coll2.empty（））
????{
????????coll2.push（c）;
????????return;
????}

????if（isPra（c））
????{
????????if（c==‘（‘）
????????????coll2.push（c）;
????????else
????????{
????????????//彈出所有元素直到遇到左括號
????????????while（coll2.top（）!=‘（‘）
????????????{
????????????????char?ch?=?coll2.top（）;
????????????????coll3.push_back（ch）;
????????????????coll2.pop（）;
????????????}

????????????//當(dāng)遇到左括號時，彈出但不加入coll3（后綴表達式中）
????????????coll2.pop（）;
????????}
????}
????else????//如果不是括號
????{
????????//取出棧頂元素，與當(dāng)前符號進行優(yōu)先性比較
????????char?sym?=?coll2.top（）;

????????//比較兩符號的優(yōu)先性
????????if（getPri（c）<=getPri（sym））
????????{
????????????//如果c的優(yōu)先性比棧頂符號小或等于，彈出棧頂元素
????????????coll2.pop（）;
????????????//并將其壓入coll3（后綴表達式）中
????????????coll3.push_back（sym）;
????????????//遞歸調(diào)用check比較當(dāng)前符號c與下一個棧頂符號的優(yōu)先性
????????????check（ccoll2coll3）;
????????}
????????else
????????{
????????????//如果c比棧頂符號優(yōu)先級大，那將c壓入coll2（操作符棧）中
????????????coll2.push（c）;
????????}
????}
}

//從coll中取出元素，分配元素到coll2和coll3中
void?allocate（deque&?coll1?stack&?coll2?deque&?coll3）
{
????while（!coll1.empty（））
????{
????????char?c?=?coll1.front（）;
????????coll1.pop_front（）;

????????if（c>=‘0‘&&c<=‘9‘）
????????{
????????????coll3.push_back（c）;
????????}
????????else
????????{
????????????//調(diào)用check函數(shù)，針對不同情況作出不同操作
????????????check（ccoll2coll3）;
????????}

????}

????//如果輸入結(jié)束，將coll2的元素全部彈出，加入后綴表達式中
????while（!coll2.empty（））
????{
????????char?c?=?coll2.top（）;
????????coll3.push_back（c）;
????????coll2.pop（）;
????}
}

//計算后綴表達式
void?calculate（deque&?coll3?stack&?coll4）
{
????while（!coll3.empty（））
????{
????????char?c?=?coll3.front（）;
????????coll3.pop_front（）;

????????//如果是操作數(shù)，壓入棧中
????????if（c>=‘0‘&&c<=‘9‘）
????????{
????????????//減去‘0‘得出偏移值，即為真實數(shù)值（如果直接轉(zhuǎn)換成int，結(jié)果不對，因為char?轉(zhuǎn)換為int是其編碼值，例如‘1‘的編碼值為49
????????????int?op?=?c-‘0‘;
????????????coll4.push（op）;
????????}
????????else?????//如果是操作符，從棧中彈出元素進行計算
????????{
????????????int?op1?=?coll4.top（）;
????????????coll4.pop（）;
????????????int?op2?=?coll4.top（）;
????????????coll4.pop（）;
????????????switch（c）
????????????{
????????????case?‘+‘:
????????????????coll4.push（op2+op1）;
????????????????break;
????????????case?‘-‘:
????????????????coll4.push（op2-op1）;
????????????????break;
????????????case?‘*‘:
????????????????coll4.push（op2*op1）;
???