解題區/解題區 - UVa

UVa 11869 - SOAP Response

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一個 SOAP 的回應格式，解析給定的回應，並且提供屬性查找。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
8
<a good="true" wants="no">
<b>
<c contest="running">
<d ballon="no">
</d>
</c>
</b>
</a>
4
a.b.c.d["ballon"]
a.c["contest"]
a.b.c["contest"]
c["contest"]

Sample Output

1
2
3
4
5
Case 1:
no
Undefined
running
Undefined

Solution

SOAP 類似 HTML XML 那種，在不少網路上的諮詢服務都會有這一套規則。

不過看到這一道題目很簡單，保證輸入格式一定可以相互匹配且完整，那使用遞迴 parsing 輸入，建造一個 tree 出來，同時子樹不會出現相同的命名。

建造樹出來之後，詢問就沿著樹走訪即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdio.h> 
#include <string.h>
#include <map>
#include <algorithm>
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
struct Node {
    string name;
    map<string, string> attr;
    vector<int> son;
    void init() {
        attr.clear();
        son.clear();
    }
};
Node node[32767];
int nodesize;
char s[1024];
void parsingAttr(string line, Node &p) {
    string ign = "<>=", attr, val;
    for (int i = 0; i < line.length(); i++) {
        if (ign.find(line[i]) != string::npos) {
            line[i] = ' ';
        }
    }
    stringstream sin(line);
    sin >> p.name;
    while (sin >> attr >> val) {
        p.attr[attr] = val.substr(1, val.length()-2);
//		cout << attr << "+++" << val << endl;
    }
}
int build(string line) {
    int label = ++nodesize;
    Node &p = node[label];
    p.init();
    parsingAttr(line, p);
    while (gets(s)) {
        if (s[1] == '/')
            break;
        p.son.push_back(build(s));
    }
    return label;
}
int main() {
    int testcase, cases = 0, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        while(getchar() != '\n');
        gets(s);
        nodesize = 0;
        int root = build(s);
        scanf("%d", &m);
        while (getchar() != '\n');
        printf("Case %d:\n", ++cases);
        while(m--) {
            gets(s);
            string ign = ".[]", token;
            for (int i = 0; s[i]; i++) {
                if (ign.find(s[i]) != string::npos) {
                    s[i] = ' ';
                }
            }
            stringstream sin(s);
            int pos = root;
            string res = "Undefined";
            sin >> token;
            if (token == node[pos].name) {
                while (sin >> token) {
                    if (token[0] == '"') {
                        string a = token.substr(1, token.length()-2);
                        if (node[pos].attr.find(a) != node[pos].attr.end())
                            res = node[pos].attr[a];
                        break;
                    } else {
                        int f = 0;
                        for (int i = 0; i < node[pos].son.size(); i++) {
                            if (token == node[node[pos].son[i]].name) {
                                f = 1;
                                pos = node[pos].son[i];
                                break;
                            }
                        }
                        if (!f)
                            break;
                    }
                }
            }
            printf("%s\n", res.c_str());
        } 
    }
    return 0;
}