??? 這是嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)》配套習(xí)題冊上的題目：將逆波蘭式轉(zhuǎn)換成波蘭式，并提示錯(cuò)誤（作為簡化，只處理"+-*/"和0~9的數(shù)字）。
??? 例如："123*-"轉(zhuǎn)換成波蘭式為"-1*23"
??? 逆波蘭式"123*-"的表達(dá)式樹如下：
???
所以這個(gè)轉(zhuǎn)換過程就是：已知一個(gè)二叉樹的后根遍歷序列，求先根遍歷序列。
??? 我的算法是根據(jù)后根遍歷的序列構(gòu)造一個(gè)表達(dá)式樹，進(jìn)而先根遍歷此樹獲得波蘭式表達(dá)式。
??? 定義了兩個(gè)結(jié)構(gòu)體：
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)?{?}
};
表示一個(gè)表達(dá)式，也是表達(dá)式樹上的一個(gè)子樹。
struct?Item{
????char??number;
????shared_ptr<Exp>?pExp;
????bool?isNumber;
????explicit?Item():isNumber(true),?number('0'),?pExp(){????}
????Item(const?Item&?i):number(i.number),?pExp(i.pExp),?isNumber(i.isNumber){?}
};
表示一個(gè)節(jié)點(diǎn)，它可以是一個(gè)數(shù)字，或者一個(gè)表達(dá)式（pExp這里我使用的是boost庫的智能指針shared_ptr，所以編譯的話，需要先安裝boost庫）。
運(yùn)行的結(jié)果如圖：
*輸入時(shí)，以'e'表示輸入結(jié)束。
完整的代碼和可執(zhí)行文件點(diǎn)擊這里下載。權(quán)當(dāng)拋磚引玉了，希望有更好算法的同學(xué)賜教。
完整的代碼：
#include?<stack>
#include?<algorithm>
#include?<string>
#include?<iostream>
#include?<boost/shared_ptr.hpp>
using?namespace?std;
using?boost::shared_ptr;
struct?Exp;
struct?Item
{
????char??number;
????shared_ptr<Exp>?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?<<?exp.op?;
????if(exp.lhs.isNumber)??cout?<<?exp.lhs.number;
????else?printPorland(*exp.lhs.pExp);
????if(exp.rhs.isNumber)??cout?<<?exp.rhs.number;
????else?printPorland(*exp.rhs.pExp);
????return;
}
int?main()
{
????stack<Item>??ExpStack;
????char?tmpChar;
????Item?tmpItem;
????Item?tmpLhs;
????Item?tmpRhs;
????string??numbers?=?"0123456789";
????string??operators?=?"+-*/";
????cout<<"Input?the?Express(輸入?'e'標(biāo)識(shí)結(jié)束):";
????do{
????try{
????????while(cin>>tmpChar){
????????????if(tmpChar?==?'e')?break;??//e為結(jié)束符
????????????else?if(find(numbers.begin(),?numbers.end(),??//是一個(gè)數(shù)字
????????????????????tmpChar)!=numbers.end()){
????????????????tmpItem.isNumber?=?true;
????????????????tmpItem.number???=?tmpChar;
????????????????ExpStack.push(tmpItem);//數(shù)字入棧
????????????}else?if(find(operators.begin(),?operators.end(),?//是一個(gè)操作符
????????????????????tmpChar)!=operators.end()){
????????????????//操作符每次要對應(yīng)兩個(gè)被操作數(shù)，否則語法錯(cuò)誤
????????????????if(ExpStack.size()<2)?throw?Error("Syntactic?Error!");?
????????????????//操作符兩邊的元素出棧
????????????????tmpRhs?=?ExpStack.top();
????????????????ExpStack.pop();
????????????????tmpLhs?=?ExpStack.top();
????????????????ExpStack.pop();
????????????????tmpItem.isNumber?=?false;???//非數(shù)字，是一個(gè)表達(dá)式
????????????????tmpItem.pExp?=?shared_ptr<Exp>(new?Exp(tmpChar,?tmpLhs,?tmpRhs));?
????????????????ExpStack.push(tmpItem);?????//表達(dá)式入棧
???????????????????????????
????????????}else?{??//?未知字符
????????????????throw??Error("Unknow?Character!");
????????????}
????????}
????????if(ExpStack.size()!=1)?throw?Error("Syntactic?Error!");
????????tmpItem?=?ExpStack.top();
????????ExpStack.pop();
????????if(tmpItem.isNumber)?cout?<<?tmpItem.number?<<endl;
????????else?printPorland(*tmpItem.pExp);
????????cout?<<?endl;
????}catch(Error&?e){
????????cout?<<?e.what()?<<?endl;
????????getline(cin,?string());????????//跳過錯(cuò)誤的當(dāng)前行
????}
????????cout?<<?"Try?again?(y/n)"?<<?endl;
????????cin?>>?tmpChar;
????}while(tmpChar?==?'y'?||?tmpChar?==?'Y');
????
????return?0;
}
posted on 2006-12-05 14:45
小山日志 閱讀(2187)
評論(0) 編輯 收藏 引用 所屬分類:
Aha! Algorithm!