算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
题目描述:
   给你一段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 = 0else 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 西月弦 阅读(247) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理