treefloor.cpp

// transverse a tree based on levels
// Lrj's whitebook p102
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

struct Node{
    int val;
    Node* left;
    Node* right;

    Node():val(-1),left(NULL), right(NULL){}
    Node(int valp, Node* leftp, Node* rightp):val(valp), left(leftp), right(rightp){}
};

const int MAXN = 256;
char s[MAXN+10];

int addnode(Node* root, int v, char *p){
    if(!strcmp(p, ")")){
        if(root->val != -1){ //replication
            return -1;
        }
        else{
            root->val = v;
            return 0;
        }
    }else if(*p == 'L'){
        Node *left = root->left;
        if(left == NULL){
            root->left = new Node(-1, NULL, NULL);
        }
        return addnode(root->left, v, p+1);
    }else if(*p == 'R'){
        Node *right = root->right;
        if(right == NULL){
            root->right = new Node(-1, NULL, NULL);
        }
        return addnode(root->right, v, p+1);
    }
}

void destroy(Node *p){
    if(p == NULL){
        return;
    }else{
        destroy(p->left);
        destroy(p->right);
        delete p;
    }
}

void printtree(Node *p){
    queue<Node*> q;
    q.push(p);
    Node * cur;
    while(!q.empty()){
        cur = q.front();
        cout << cur->val << " ";
        if(cur->left != NULL){
            q.push(cur->left);
        }
        if(cur->right != NULL){
            q.push(cur->right);
        }
        q.pop();
    }
    cout << endl;
}

bool checktree(Node *p){
    if(p == NULL) return true;
    else if(p->val == -1) return false;
    else{
        return checktree(p->left) && checktree(p->right);
    }
}

int read_input()
{
    int failed = 0;
    Node* root = new Node(-1, NULL, NULL);
    while(true)
    {
        if(scanf("%s", s) != 1) return 0;
        if(!strcmp(s, "()")) break;
        int v;
        sscanf(&s[1], "%d", &v);
        failed = addnode(root, v, strchr(s, ',') + 1);
        if(failed == -1){
            break;
        }
    }
    if(failed == -1 || !checktree(root)){
        cout << -1 << endl;
    }
    else{
        printtree(root);
    }

    destroy(root);
    return 1;
}


int main(){
    char buf[256+10];
    int id;
    while(read_input()){
    }
}