多彩的讲座笔记[HihoCoder-1103]

问题描述比较长，废话也比较多，就放个链接好了。https://vjudge.net/problem/HihoCoder-1103

这道题也是基础的数据结构题。题目要求统计在一个<A>..</A>标记（类似于HTML的语法）内部的字符个数。考虑到标记A本身是闭合的，因此依然可以利用栈这一简单的数据结构。扫描到前标记，进栈；当扫描到后一个标记时，出栈。至于统计字符，这里也是应用了一个巧妙的做法，即使用了数组cnt[3]，因为题目中只给了三种标记，故这里让标记名称与数组下标进行了简单对应。跳过标记字符后，每扫描到一个字符，栈顶元素表示了这个字符所属的最内层的标记，因此让cnt[s.top()]++就可以完成统计了。如果标记比较多，可能会用到关联数组（STL的map）；至于具体在工程上如何读取标记描述的文本，正好前一段时间下载了TinyXML这一开源库，可以研究研究。

最后注意输入数据中可能包括空格，不能直接用scanf或者cin。

我的C++实现如下

 1 #include<iostream>
 2 #include<stack>
 3 using namespace std;
 4 #define red 0
 5 #define blue 1
 6 #define yellow 2
 7 int main()
 8 {
 9     stack<int> s;
10     int cnt[3] = { 0 };
11     char buf[2000];
12     fgets(buf, 1005, stdin);
13     int i;
14     for (i = 0; buf[i] != 0; i++)
15     {
16         if (buf[i] == '<')
17         {
18             switch (buf[i + 1])
19             {
20                 case 'r':
21                     s.push(red);
22                     i += 4;
23                     break;
24                 case 'b':
25                     s.push(blue);
26                     i += 5;
27                     break;
28                 case 'y':
29                     s.push(yellow);
30                     i += 7;
31                     break;
32                 case '/':
33                     switch (buf[i + 2])
34                     {
35                         case 'r':
36                             i += 5;
37                             break;
38                         case 'b':
39                             i += 6;
40                             break;
41                         case 'y':
42                             i += 8;
43                             break;
44                     }
45                     s.pop();
46                     break;
47             }
48         }
49         else
50             if (!s.empty() && buf[i] != ' ')
51                 cnt[s.top()]++;
52     }
53     cout << cnt[red] << " " << cnt[yellow] << " " << cnt[blue];
54     return 0;
55 }