2021 年 9 月青少年软编等考 C 语言六级真题解析

T1. 合法出栈序列

题目链接：SOJ D1110

给定一个由不同小写字母构成的长度不超过 $8$ 的字符串 $x$，现在要将该字符串的字符依次压入栈中，然后再全部弹出。要求左边的字符一定比右边的字符先入栈，出栈顺序无要求。再给定若干字符串，对每个字符串，判断其是否是可能的 $x$ 中的字符的出栈序列。

时间限制：1 s
内存限制：64 MB

• 输入
  第一行是原始字符串 $x$。
  后面有若干行，每行一个字符串。
• 输出
  对除第一行以外的每个字符串，判断其是否是可能的出栈序列。如果是，输出 YES，否则，输出 NO。
• 样例输入

  abc
  abc
  bca
  cab
  

• 样例输出

  YES
  YES
  NO
  

思路分析

此题考查栈模拟，属于基础题。

可以依次将入栈序列 $x$ 中的元素入栈，每入栈一个元素之后，就检测栈顶元素是否为当前出栈序列 $str$ 的第一个，如果是，则进行出栈操作，并且删除出栈序列 $str$ 的第一个，重复以上检测操作直到栈为空，或者栈顶元素与出栈序列 $str$ 的第一个元素不一致。当入栈序列 $x$ 中的所有元素全入栈，并且做完检测之后，如果栈空，则说明该出栈序列合法，否则不合法。

/** Name: T1.cpp* Problem: 合法出栈序列* Author: Teacher Gao.* Date&Time: 2025/03/09 09:30*/#include <iostream>
#include <stack>using namespace std;int main()
{ios::sync_with_stdio(false);cin.tie(0);string x, str;cin >> x;while (cin >> str) {stack<char> S;for (int i = 0, j = 0; i < x.size(); i++) {S.push(x[i]);while (!S.empty() && S.top() == str[j]) {S.pop(); j++;}}if (S.empty()) cout << "YES\n";else           cout << "NO\n";}return 0;
}

T2. 奇怪的括号

题目链接：SOJ D1111

某天小 A 和同学在课堂上讨论到：“栈这种数据结构真是太优美了，既简单用途又广泛。” 小 B 仰慕小 A 许久，于是他拿出了自己在网上抄写的一道题问小 A，如何判断括号是否匹配呢？

时间限制：1 s
内存限制：64 MB

• 输入
  多组数据，每组数据占一行，且都是由 (、)、[、]、*、/ 这六种字符组成。
• 输出
  每组数据输出一行，如果括号能匹配成功，输出 True，否则输出 False。括号匹配规则是：( 和 ) 匹配，[ 和 ] 匹配， /* 和 */ 匹配。如果含有冗余字符也算匹配失败，例如 /***/ 是匹配失败的，因为中间多了一个 *。
• 样例输入

  ()/*[()]*/
  */**/
  

• 样例输出

  True
  False
  

思路分析

此题考查栈的应用之括号匹配问题，属于基础题。核心思路与 2020 年 9 月三级第三题一致。

麻烦的地方在于此题中需要匹配 $\mathtt{C}$++ 中的多行注释符号，一种可行的方案是把所有的 /* 和 */ 都替换为 { 和 }，在之后的匹配过程中如果检测到 / 或 *，则说明匹配失败。在替换操作完成之后再进行括号匹配，代码思路会更清晰。示例代码是在括号匹配过程中进行的替换，注意代码中的下标。

/** Name: T2.cpp* Problem: 奇怪的括号* Author: Teacher Gao.* Date&Time: 2025/03/09 12:12*/#include <iostream>
#include <stack>using namespace std;stack<char> S;bool check(char ch) {if (!S.empty() && S.top() == ch) {S.pop();return 1;}return 0;
}int main()
{ios::