[LeetCode]Tag Validator

这题本质上就是写一个html/xml的parser，我们只是不需要生成最后的html/xml tree，只要验证输入的string是valid的即可。Parser的普遍写法可以参考LL(1) parser，但是这里我们不需要那么复杂，仍然沿用State Machine的思路即可。我们定义不同的状态，然后根据不同的状态处理输入即可。这里我们定义以下状态：

1. Start，初始状态
2. End，结束状态
3. Open_Tag，现在处于Open tag当中
4. Close_Tag，现在处于Close tag当中
5. CDATA，处于CDATA当中
6. Tag，现在我们处于某个Tag但还没有足够的信息判断是处在Open, Close还是CDATA当中
7. Content，现在处于Content当中

那么对于不同的状态，我们要处理的输入是：

1. 处在Start，我们跳过space，除此之外只要输入不是<就是不valid的。如果是<进入Open_Tag状态
2. 处在End，如果还没有到达string的末尾，就是不valid的
3. 处在Open_Tag，记录所有input string直到>出现，并且判断tag那么是不是都是大写，并且长度在[1, 9]范围中
4. 处在Close_Tag，记录所有input string直到>出现，判断栈顶有元素并且和当前tag的name match。如果栈还有元素，进入Content状态；否则进入End状态。（这道题只允许一个root tag）
5. 处在CDATA，我们记录直到第一个]]>出现，并且判断前缀是![CDATA[。如果不是那么不valid，否则进入Content
6. 处在Tag，我们判断下一个input char，如果是！，进入CDATA; 如果是/，进入Close_Tag，如果是大写字母，进入Open_Tag。否则不valid。
7. 处在Content，接受任何input直到出现<，进入Tag状态(我们当前并不知道这个是哪种类型)

我们需要确定最后的状态是End，并且没有未处理的char即可，时间复杂度O(n)，n为input string的长度，代码如下：