2013年7月18日 星期四

[UVA] 122 - Trees on the level solution

#include<iostream>
#include <string>
#include <queue>
#define Notc "not complete"
using namespace std;

int to_int(char const *s)
{
     if ( s == NULL || s[0] == '\0' )
     {
       return 0;
     }
     bool negate = (s[0] == '-');
     if ( *s == '+' || *s == '-' )
          ++s;
     int result = 0;
     while(*s)
     {
          if ( *s >= '0' && *s <= '9' )
          {
              result = result * 10  - (*s - '0');
          }
          else
              return 0;
          ++s;
     }
     return negate ? result : -result;
}
class node{
public:
    node(){
        value=-1;
        bLeft=0;
        bRight=0;
    }
    bool bLeft,bRight;
    node *left,*right;
    int value;

};
int LevelOrderTraversal(node *root){
    queue<node*> myqueue;
    queue<int> qAnswer;
    myqueue.push(root);
    while(!myqueue.empty()){
        node *ptr=myqueue.front();
        myqueue.pop();
        if(ptr->value==-1){
            cout<<Notc<<endl;
            return 1;

        }
        else{
            qAnswer.push(ptr->value);
            if(ptr->bLeft)
                myqueue.push(ptr->left);
            if(ptr->bRight)
                myqueue.push(ptr->right);
        }


    }
    bool whiteSpace=false;
    while(!qAnswer.empty()){
        if(whiteSpace) cout<<" ";
        cout<<qAnswer.front();
        qAnswer.pop();
        whiteSpace=true;
    }
    cout<<endl;

}
int main(){
    string tempV,tempP,bufs;


    int count_notc=0;
    node *root=new node();
    bool bRepeate=false;
    while(cin>>bufs){
        std::size_t comma=bufs.find(",",0);
       if(bufs.length()==2){
            if(bRepeate) {
                cout<<Notc<<endl;
                root->bLeft=false;
                root->bRight=false;
                root->value=-1;
                bRepeate=false;
                continue;
            }
            else{
                LevelOrderTraversal(root);
                root->bLeft=false;
                root->bRight=false;
                root->value=-1;
                bRepeate=false;
                continue;
            }
       }
       tempV=bufs.substr(1,comma-1);
       tempP=bufs.substr(comma+1,bufs.find(")",0)-comma-1);
       int value=to_int(tempV.c_str());
       node *ptr;
       ptr=root;
       if(tempP!=""){
            for(int i=0;i<tempP.length();i++){
               if(tempP[i]=='L'){
                    if(!ptr->bLeft){
                        ptr->left=new node();
                        ptr->bLeft=true;
                    }
                    ptr=ptr->left;
               }
                else if(tempP[i]=='R'){
                    if(!ptr->bRight){
                        ptr->right=new node();
                        ptr->bRight=true;
                    }
                    ptr=ptr->right;
               }
            }
       }
        if(ptr->value!=-1){
            bRepeate=true;
            continue;
        }
        else
            ptr->value=value;
   }
    return 0;
}

沒有留言:

張貼留言