小山日志
读书,学习与思考.
posts - 9,comments - 14,trackbacks - 0
    这是严蔚敏《数据结构》配套习题册上的题目:将逆波兰式转换成波兰式,并提示错误(作为简化,只处理"+-*/"和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'表示输入结束。
完整的代码和可执行文件点击这里下载。权当抛砖引玉了,希望有更好算法的同学赐教。


完整的代码:
posted on 2006-12-05 14:45 小山日志 阅读(2148) 评论(0)  编辑 收藏 引用 所属分类: Aha! Algorithm!

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理