題目描述：
給你一段XML程序，問它是否well-formed
算法分析：
用棧來模擬，判斷標簽是否匹配。
trick是<a><b><a></a></b></a>是不可以的。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<string>
5 using namespace std;
6 const int N = 10005;
7 string ch;
8 string stk[N];
9 string tmp[N];
10 const string start = "?xml version=\"1.0\"?";
11 const string end = "?end?";
12 int main(){
13 char c;
14 int back = 0, tp = 0;
15 bool flag = 1, all_start = 1,begin = 1;
16 while(c = getchar()) {
17 // cout<<c;
18 if(c == '\n') continue;
19 else if(c == '<') {
20 back ++;
21 ch.clear();
22 } else if(c == '>') {
23 back --;
24 if(back != 0) flag = 0;
25 back = 0;
26 if(start == ch || ch == end) {
27 if(all_start) {
28 all_start = 0;
29 } else if(!flag || tp != 0) {
30 cout<< "non well-formed" << endl;
31 } else {
32 cout<< "well-formed" << endl;
33 }
34 begin = 1; tp = 0; flag = 1;
35 if(ch == end) break;
36 } else if(ch[0] == '/') {
37 ch.erase(ch.begin());
38 if(tp == 0 || ch != stk[tp-1]) flag = 0;
39 tp --;
40 } else {
41 if(begin) begin = 0; else if(tp == 0) flag = 0;
42 string name;
43 int n = ch.size(), len = 0;
44 if(ch[n-1]=='/') continue;
45 bool first = 1;
46 for(int i = 0; i <= n; i++) {
47 if(i == n || ch[i] == ' '){
48 if(name == "" || i && ch[i-1]==' ') continue;
49 //cout<<name<<" ";
50 if(first) {
51 for(int j = 0; j < tp ; j++)
52 if(stk[j] == name) flag = 0;
53 stk[tp++] = name;
54 first = 0;
55 } else {
56 int m = name.size();
57 int pos = (int)name.find('=');
58 //cout<<pos<<" ";
59 if(pos == -1) flag = 0;
60 else {
61 if(name[m-1] == '"' && name[pos + 1] == '"') {
62 string temp = name.substr(0,pos);
63 //cout<<temp;
64 if(temp == "") flag = 0;
65 else {
66 for(int j = 0; j < len; j++)
67 if(tmp[j] == temp) flag = 0;
68 tmp[len ++] = temp;
69 }
70 } else flag = 0;
71 }
72 }
73 name.clear();
74 } else name.push_back(ch[i]);
75 }
76 }
77 } else {
78 if(back) ch.push_back(c);
79 else if (tp == 0){
80 flag = 0;
81 }
82 }
83 // cout<<flag;//<<tp;
84 }
85 }
86
posted on 2012-10-28 15:58
西月弦 閱讀(283)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告