資源簡介
這是嚴蔚敏《數據結構》配套習題冊上的題目:將逆波蘭式轉換成波蘭式,并提示錯誤(作為簡化,只處理"+-*/"和0~9的數字)。
例如:"123*-"轉換成波蘭式為"-1*23"
逆波蘭式"123*-"的表達式樹如下:
所以這個轉換過程就是:已知一個二叉樹的后根遍歷序列,求先根遍歷序列。
算法是根據后根遍歷的序列構造一個表達式樹,進而先根遍歷此樹獲得波蘭式表達式。
代碼片段和文件信息
#include?
#include?
#include?
#include?
#include?
using?namespace?std;
using?boost::shared_ptr;
struct?Exp;
struct?Item{
????char??number;
????shared_ptr?pExp;
????bool?isNumber;
explicit?Item():isNumber(true)?number(‘0‘)?pExp(){ }
Item(const?Item&?i):number(i.number)?pExp(i.pExp)?isNumber(i.isNumber){?}
};
struct?Exp{
????char??op;
????Item??lhs;
????Item??rhs;
Exp(){};
Exp(char?_op?Item?_lhs?Item?_rhs):op(_op)?lhs(_lhs)?rhs(_rhs){?}
Exp(const?Exp&?e):op(e.op)?lhs(e.lhs)?rhs(e.rhs)?{?}
};
class?Error{
????string?info;
public:
????Error(string?_info):info(_info){?}
????Error():info(““){?}
????string?what(){return?info;}???
};
void?printPorland(Exp&?exp){
cout?< if(exp.lhs.isNumber)??cout?< else?printPorland(*exp.lhs.pExp);
if(exp.rhs.isNumber)??cout?< else?printPorland(*exp.rhs.pExp);
return;
}
int?main()
{
????stack- ??ExpStack;
????char?tmpChar;
????Item?tmpItem;
????Item?tmpLhs;
????Item?tmpRhs;
????string??numbers?=?“0123456789“;
????string??operators?=?“+-*/“;
????cout<<“Input?the?Express(輸入?‘e‘標識結束):“;
do{
try{
while(cin>>tmpChar){
- 上一篇:STC15的modbus程序
- 下一篇:C++課件+STL
評論
共有 條評論