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