这是严蔚敏《数据结构》配套习题册上的题目:将逆波兰式转换成波兰式,并提示错误(作为简化,只处理"+-*/"和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
小山日志 阅读(2178)
评论(0) 编辑 收藏 引用 所属分类:
Aha! Algorithm!