资源简介

这是严蔚敏《数据结构》配套习题册上的题目:将逆波兰式转换成波兰式,并提示错误(作为简化,只处理"+-*/"和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 << 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  ExpStack;
    char tmpChar;
    Item tmpItem;
    Item tmpLhs;
    Item tmpRhs;
    string  numbers = “0123456789“;
    string  operators = “+-*/“;

    cout<<“Input the Express(输入 ‘e‘标识结束):“;
do{
try{
while(cin>>tmpChar){

评论

共有 条评论