?LeetCode刷題實(shí)戰(zhàn)591：標(biāo)簽驗(yàn)證器

class?Solution?{
public:
????bool?isValid(string?code)?{
????????stack<string> stk; // 用棧維護(hù) tag_name
????????for(int?i = 0;i < code.size();i ++ ){
????????????if(code[i] == '<'){
????????????????int?j = i + 1;
????????????????while(j < code.size() && code[j] != '>') j ++ ; // 找到與之對(duì)應(yīng)的 > 
????????????????if(code[i + 1] == '/'){
????????????????????if(stk.empty()) return?false; // 沒(méi)有匹配的 左標(biāo)簽直接反回 false
????????????????????if(stk.top() != code.substr(i + 2, j - (i + 2))) return?false; // 有匹配的 但是兩個(gè)不一樣
????????????????????stk.pop(); // 記得刪除棧頂
????????????????}else?if(code.substr(i, 9) != "){ // 如果不是 CDATA 那么就一定是一個(gè)起始標(biāo)簽
????????????????????if(i && stk.empty()) return?false; // 如果有多個(gè) tag_name 并列 返回 false
????????????????????for(int?k = i + 1;k < j;k ++ ) if(code[k] < 'A'?|| code[k] > 'Z') return?false; // 字母不合法
????????????????????if(j - 1?- (i + 1) + 1?> 9?|| j - 1?- (i + 1) + 1?< 1) return?false; // 長(zhǎng)度不合法
????????????????????stk.push(code.substr(i + 1, j - (i + 1))); // 壓入棧中
????????????????}else{
????????????????????if(code.substr(i, 9) == "){ 
????????????????????????if(stk.empty()) return?false; // 如果是沒(méi)有被包含在標(biāo)簽里的直接返回 false
????????????????????????j = i;
????????????????????????while(j < code.size() && code.substr(j, 3) != "]]>") j ++ ;
????????????????????????if(j == code.size()) return?false;
????????????????????????j += 2; // 過(guò)濾掉 CDATA 里邊的所有字符
????????????????????}
????????????????}
????????????????i = j;
????????????}else{ // tag_content
????????????????if(stk.empty()) return?false; // 沒(méi)有被包含進(jìn)來(lái) 直接返回 false
????????????????int?j = i;
????????????????while(j < code.size() && code[j] != '<') j ++ ; // 過(guò)濾掉中間不包含 < 的所有字符
????????????????if(j == code.size()) return?false;
????????????????i = j - 1;
????????????}
????????}
????????if(stk.size()) return?false; // 如果棧還有東西 返回false
????????return?true; // 萬(wàn)事大吉 返回 true
????}
};

作者：Lemmon_kk
鏈接：https://www.acwing.com/activity/content/code/content/625320/
來(lái)源：AcWing
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。