The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

已知先序+中序遍历求后序遍历（模板类）

 

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
//////////////////////////////////////////////////////////////////////////////////////////
///                                    Pre_in_to_pos class
///        此类封装了能够将树的先序遍历和中序遍历转化成后序遍历的操作(AC北大pku2255)
///                                                    -By abilitytao
///                                                            2009年5月24日
//////////////////////BEGIN_TEMPLATE_BY_ABILITYTAO_ACM/////////////////////////////////////
class Pre_in_to_pos
{

private:
    string pre;
    string in;
    string post;
    void trans(string a,string b);
public:
    Pre_in_to_pos()
    {

        pre.erase();
        in.erase();
        post.erase();
    }
    int inputpre();
    int inputpre(string a)
    {

        pre=a;
        return 1;
    }
    int inputin();
    int inputin(string a)
    {

        in=a;
        return 1;
    }

    void trans();
    void output();
    void clear();
};

int Pre_in_to_pos::inputpre()
{

    cin>>pre;
    return 1;
}

int Pre_in_to_pos::inputin()
{

    cin>>in;
    return 1;
}

void Pre_in_to_pos::trans(string a,string b)
{

    int k=a.find(b.substr(0,1));
    if(k>0)
        trans(a.substr(0,k),b.substr(1,k));
    if(k<a.length()-1)
        trans(a.substr(k+1,a.length()-1-k),b.substr(k+1,b.length()-1-k));
    post+=a[k];
}

void Pre_in_to_pos::trans()
{
    post.erase();
    trans(in,pre);
}

void Pre_in_to_pos::output()
{

    cout<<post;
}//没有预置回车；


/////////////////////END_TEMPLATE_BY_ABILITYTAO_ACM/////////////////////////////





int main()
{

    Pre_in_to_pos test;
    string pre;
    string in;
    while(cin>>pre>>in)
    {
        test.inputpre(pre);
        test.inputin(in);
        test.trans();
        test.output();
        cout<<endl;
    }
    return 0;
}

posted on 2009-05-24 01:41 abilitytao 阅读(322) 评论(0)  编辑 收藏 引用


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