UVA 11869 SOAP Response

概要
簡易的なXMLを解析せよ。タグに複数のプロパティが割り当てられている場合があるので、クエリで呼びだそうとしているプロパティが存在するものならその値を、存在しないなら代わりに "Undefined" を出力せよ。

解法
木を作って走査するだけ。

#include <bits/stdc++.h>
 
using namespace std;
 
struct node;
typedef node* node_ptr;
 
struct node
{
  string tag;
  vector<string> elements, values;
  vector<node_ptr> children;
  
  node() {
  }
   
  ~node() {
    vector<node_ptr>::iterator iter = children.begin();
    for(; iter!=children.end();iter++) {
      delete *iter;
    }
  }
};
 
node_ptr root;
int LNUM;
string lines[1010];
 
int lidx;
node_ptr rec() {
   
  node_ptr ret = new node();
   
  stringstream ss(lines[lidx]);
  vector<string> data;
  string s;
  while(ss >> s) {
    data.push_back(s);
  }
   
  ret->tag = data[0];
   
  for(int i=1; i<data.size(); i++) {
    int eq = data[i].find("=");
    string s = data[i].substr(0, eq);
    string t = data[i].substr(eq+1);
     
    s = "\"" + s + "\"";
    ret -> elements.push_back(s);
    ret -> values.push_back(t);
     
  }
   
  lidx++;
   
  while(1) {
    if(lidx >= LNUM) return ret;
    if(lines[lidx][0] == '/') {
      lidx++;
      return ret;
    }
    ret -> children.push_back(rec());
  }
}
 
string ans;
 
bool traverse(node_ptr n, string query) {
   
  int lpar = query.find("[");
  int dot = query.find(".");
   
  if(dot == -1) {

    string key = query.substr(lpar+1, query.size()-lpar-2);
     
    for(int i=0; i<n->elements.size(); i++) {
      if(n->elements[i] == key) {
        ans = n->values[i].substr(1, (int)n->values[i].size()-2);
        return true;
      }
    }
     
    return false;
  }
   
 
  if(dot >= (int)query.size()) return false;
   
  if(query.substr(0, dot) == n->tag) {
    for(int i=0; i<n->children.size(); i++) {
      if(traverse(n->children[i], query.substr(dot+1))) {
        return true;
      }
    }
  }
   
  return false;
}
 
 
int main() {
   
  int Tc; cin >> Tc;
   
  for(int Tcnt=1; Tcnt<=Tc; Tcnt++) {
 
    root = new node();
     
    cout << "Case " << Tcnt << ":" << endl;
     
    cin >> LNUM; cin.ignore();
     
    for(int i=0; i<LNUM; i++) {
      getline(cin, lines[i]);
      lines[i] = lines[i].substr(1);
      lines[i] = lines[i].substr(0, lines[i].size()-1);
    }
     
    lidx = 0;
    root->children.push_back(rec());
     
    int Q;
    cin >> Q; 
    string query;
    for(int i=0; i<Q; i++) {
      cin >> query;
       
      if(traverse(root->children[0], query)) {
        cout << ans << endl;
      }
      else {
        cout << "Undefined" << endl;
      }
    }
     
    delete root;
  }
   
  return 0;
}