首页 > ACM题库 > HDU-杭电 > HDU 3426-XML[解题报告]HOJ
2014
03-23

HDU 3426-XML[解题报告]HOJ

XML

问题描述 :

In this problem, you are asked to determine if a given document satisfies the syntax of an XML-like language.

A simple XML-like document can be parsed as a sequence of the following:

1. Plain text—ASCII codes between 32 and 127 (inclusive), with none of the following symbols: <, >, &
2. The sequences:
* &lt;
* &gt;
* &amp;
These encode a <, >, or & respectively.
3. &xHEX; HEX must be any even (positive) number of upper or lower case hexadecimal digits, and this represents the bytes given.
4. <tag> Tag can be any lowercase alphanumeric string. This tag is pushed onto the context stack.
5. <tag/> This tag is not pushed onto the context stack (there is no closing context).
6. </tag> This tag removes the <tag> context from the stack, which must be topmost on the stack.

By the time the entire document is parsed, the context stack is empty for a valid document. We should also note that the empty string is considered valid.

输入:

You will be given a number of documents to process. Each document is given as one line oftext which may be empty. The input is terminated by the end of file.

输出:

You will be given a number of documents to process. Each document is given as one line oftext which may be empty. The input is terminated by the end of file.

样例输入:

the quick brown fox.
the <i><b>quick</b> brown</i> fox.
<doc>fox &amp; socks.</doc>
3x+5&gt;7
Null: &x00;
<doc>the quick brown fox.
the <i>quick <b>brown</i></b> fox
fox & socks.
3x+5>7
Null: &x0;

样例输出:

valid
valid
valid
valid
valid
invalid
invalid
invalid
invalid
invalid

#include <stdio.h>
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;


vector<string> st;

int tag_type(const string& s) {
	int cnt=0;	
	for(int i=0; i<s.size(); ++i) {
		if(s[i]=='/') { cnt++; continue; }
		if(!((s[i]<='z' && s[i]>='a') || (s[i]>='0' && s[i]<='9'))) return 0;
	}
	if(s.size()-cnt==0) return 0;
	if(s[0]=='/' && cnt == 1) return 2;
	if(s[s.size()-1]=='/' && cnt == 1) return 3;
	if(cnt == 0) return 1;
	return 0;
}
bool hex(const string& s) {
	if(s.size() <= 1 || s.size()%2==0) return false;
	if(s[0] != 'x') return false;
	for(int i=1; i<s.size(); ++i)
		if( !((s[i]<='F' && s[i] >='A') || (s[i]<='9' && s[i]>='0') || (s[i]<='f' && s[i]>='a')) ) return false;
	return true;
}
bool bad_qoute(const string& s) {
	return !(s=="lt" || s=="gt" || s=="amp" || hex(s));
}
bool bad_txt(const string& s) {
	string qoute;
	for(int i=0; i<s.size(); ++i)
		if(s[i]=='&') {
			for(int j=i+1; j<s.size() && s[j] != ';'; ++j) qoute += s[j];
			if(bad_qoute(qoute)) return true;
			qoute="";
		} 
		else if(s[i]=='<' || s[i] =='>') return true;
		else if(s[i]>127 || s[i]<32) return true;
	return false;
}
void get_l(stringstream& os, string& s, char del) {
	char t;
	while(!os.eof()) {
		os >> t;
		if(t==del) return;
		s += t;
	}	
}
int main() {
	string ln;
	while(getline(cin, ln)) {
		stringstream ss(ln);
		st.clear();
		string s;
		int inv=0;
		while(!ss.eof()) {
			s="";
			getline(ss,s,'<');
			// cout << "txt: " << s << endl;
			if(bad_txt(s)) {
				inv=1;
				break;
			}
			if(ss.eof()) break;
			s="";
			getline(ss,s,'>');
			if(ss.eof()) {
				inv=4;
				break;
			}
			// cout << "tag: " << s << endl;
			int tty = tag_type(s);
			if(tty==0) {
				inv=2;
				break;
			} 
			else if(tty==1) st.push_back(s);
			else if(tty==2) {				
				if(st.size()==0 || st.back() != s.substr(1)) {
					inv=3;
					break;
				}
				else st.pop_back();
			}
		}
		// cout << inv << endl;
		if(inv || st.size() > 0) puts("invalid");
		else puts("valid");
	}
	return 0;
}

  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮