标题：根据给出的括号表达式字符串建立二叉树
出处：Felix021
时间：Wed, 27 May 2009 02:17:47 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1615

内容：
突然想写了，就写了一个。
因为调试需要，自己写了一个stack，继承vector实现（如果是继承自通用stack类的话那就是个类适配器了哦^_^）

代码如下：
#include<iostream>
#include<vector>
using namespace std;

struct node_t{
    char data;
    node_t *left, *right;
    node_t(){
        data = '\0';
        left = NULL;
        right = NULL;
    }
    ~node_t() {
        delete left; 
        delete right;
    }
    friend inline ostream & operator << (ostream &os, const node_t &t){
        os << t.data << "(" << t.left << "," << t.right << ")";
        return os;
    }
}*root;
void print(node_t **t){
    if(*t == NULL){
        cout << 0;
    } else {
        cout << *t << "|" << (**t);
    }
}

void dump(node_t *t = root, int dep = 0){
    if(t != NULL){
        for(int i = 0; i < dep; ++i) printf("  ");
        print(&t);
        printf("\n");
        dump(t->left, dep+1);
        dump(t->right, dep+1);
    }
}

template<typename T>
class mystack: private vector<T>{ //很少使用private继承哦，嘿嘿。
public:
    void push(const T &a){
        this->push_back(a);
    }
    void pop(){
        this->pop_back();
    }
    T & top(){
        return *(this->rbegin());
    }
    void dump(void (*print)(T)){
        for(unsigned int j = 0; j < this->size(); ++j){
            print(this->operator[](j));
            cout << ',' ;
        }
        cout << endl;
    }
};

node_t* build(char *s){
    mystack<node_t**>ooxx;
    node_t *root = new node_t, **t;
    ooxx.push(&root);
    for(int i = 0; s[i] != '\0'; ++i){
        printf("procesing %c\n", s[i]);
        switch(s[i]){
            case ' ':
                break;
            case '(':
                t = ooxx.top();
                ooxx.push(&((*t)->left));
                break;
            case ',':
                ooxx.pop();
                t = ooxx.top();
                ooxx.push(&((*t)->right));
                break;
            case ')':
                ooxx.pop();
                break;
            default:
                t = ooxx.top();
                if(*t == NULL) *t = new node_t;
                (*t)->data = s[i];
                break;
        }
        ooxx.dump(print);
    }
    return root;
}

int main(){
    root = build("a(b(,e(f,g(h(j,),i(k,)))),c(d,))");
    dump(root);
    return 0;
}



Generated by Bo-blog 2.1.0