4189940_ac_0ms_228k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

set <string> tags;
set <string> ::iterator it;
stack <string> trace;

const string head = "<?xml version=\"1.0\"?>";
const string over = "<?end?>";

string nextTag(string &str)
{
	int index1 = str.find_first_of('<');
	int index2 = str.find_first_of('>');

	string tmp = str;
	str = str.substr(index2 + 1);
	if (index1 == -1 || index2 == -1)
	{
		return "I love Shengqi";
	}
	return tmp.substr(index1 + 1, index2 - index1 - 1);
}

bool goodTag(string str)
{
	if (str.at(0) == '/')
	{
		str = str.substr(1);
	}
	string tag = str;
	if (str.find('/') != string::npos)
	{
		tag = tag.substr(0, tag.length() - 1);
	}
	set <string> ts;
	ts.clear();
	int i1, i2;
	while (true)
	{
		i1 = tag.find_first_of('=');
		if (i1 == string::npos)
		{
			break;
		}
		i2 = i1 - 1;
		while (tag.at(i2) != ' ')
		{
			i2--;
		}

		string att = tag.substr(i2 + 1, i1 - i2);
		tag = tag.substr(i1 + 1);
		int i3 = tag.find_first_of('\"');
		if (i3 == string::npos)
		{
			return false;
		}
		tag = tag.substr(i3 + 1);
		int i4 = tag.find_first_of('\"');
		if (i4 == string::npos)
		{
			return false;
		}
		for (int i = 0; i < i4; i++)
		{
			if (tag.at(i) == ' ')
			{
				return false;
			}
		}
		tag = tag.substr(i4 + 1);
		if (ts.find(att) != ts.end())
		{
			return false;
		}
		ts.insert(att);
	}
	return true;
}

string getName(string str)
{
	int i1, i2;

	for (i1 = 0; str.at(i1) == ' '; i1++);
	for (i2 = i1; i2 < str.length() && str.at(i2) != ' '; i2++);
	return str.substr(i1, i2 - i1);
}

bool isXML(string str)
{
	while (!trace.empty())
	{
		trace.pop();
	}

	string tag;

	int total = 0;
	while (true)
	{
		if (tags.size() == 0)
		{
			total++;
		}
		tag = nextTag(str);
		if (tag == "I love Shengqi")
		{
			break;
		}
		if (!goodTag(tag))
		{
			return false;
		}
		if (tag.at(tag.length() - 1) == '/')
		{	
			continue;
		}
		string name = getName(tag);
		if (name.at(0) == '/')
		{
			it = tags.find(name.substr(1));
			if (it == tags.end())
			{
				return false;
			}
			if (trace.top() != *it)
			{
				return false;
			}
			trace.pop();
			tags.erase(it);
		}
		else
		{
			it = tags.find(name);
			if (it != tags.end())
			{
				return false;
			}
			tags.insert(name);
			trace.push(name);
		}
	}
	if (total != 2 || tags.size() != 0 || !trace.empty())
	{
		return false;
	}
	return true;
}

int main()
{
	string all, line;
	char tmpstr[1000];

	gets(tmpstr);
	line = string(tmpstr);
	while (true)
	{
		all = "";
		tags.clear();
		while (true)
		{
			gets(tmpstr);
			line = string(tmpstr);
			if (line == head || line == over)
			{
				break;
			}
			all += line;
		}
		puts(isXML(all) ? "well-formed" : "non well-formed");
		if (line == over)
		{
			break;
		}
	}
	return 0;
}