[UVA] 122 - Trees on the level

題意:
給一棵二元樹的節點，
輸入(n,s)，
n是該節點的編號，
s是從根結點走到該節點的路徑，(根結點沒有s)
R是右，L是左，
輸入()表示該筆測資結束。
注意! 這題是多筆測資喔!
由左到右，從上到下將樹的節點編號輸出，
如果給重複的節點或該節點沒有父節點，則輸出not complete，
例如:
輸入:(1,R) (2,RR) ()
輸出:not complete//沒有根結點

方法:
判斷路徑s長度，
長度越短越先輸出，
長度相同，L比R先輸出，
依此排序，
排序後，
第一個點必須沒有s，
而後面的所有點都要有父節點，
否則就是not complete

判斷父節點就判斷是否有節點的路徑是該節點的路徑去尾，
例如(1,RRL)和(2,RRR)的父節點就是(n,RR)


/* 20150818
 * hanting
 * UVa 122 - Trees on the level
 * C++
 */
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>//sort
#include <sstream>
using namespace std;
struct Node
{
    int id;
    string route;
    Node(int x,string str):id(x),route(str){}
    bool operator<(const Node &n)const
    {
        if(route.size()<n.route.size()) return true;
        else if(route.size()==n.route.size())return route<n.route;
        else return false;
    }
};
inline string Parent(string &str)
{
    return str.substr(0,str.size()-1);
}
string str;
vector<Node> vec;
map<string,int> Map;
bool Input()
{
    Map.clear();
    vec.clear();
    bool input=false;
    while(cin>>str and str!="()")
    {
        input=true;
        stringstream sin(str);
        char ch;
        int x;
        string tmp;
        sin>>ch>>x>>ch>>tmp;//( 11 , LL)
        tmp.erase(tmp.size()-1);//右括弧
        vec.push_back(Node(x,tmp));
    }
    return input;
}
int main()
{
    while(Input())
    {
        sort(vec.begin(),vec.end());
        bool NO=vec[0].route!="";
        Map[""]=1;
        for(int i=1;i<vec.size() and !NO;i++)
        {
            string par=Parent(vec[i].route);//求父節點
            if(Map.count(par)==0 or Map.count(vec[i].route)!=0)
            {
                NO=true;
                break;
            }
            Map[vec[i].route]++;
        }
        if(NO)
        {
            cout<<"not complete"<<endl;
        }
        else
        {
            for(int i=0;i<vec.size()-1;i++)
            {
                cout<<vec[i].id<<" ";
            }
            cout<<vec.back().id<<endl;
        }
    }
    return 0;
}