2-4 栈操作的合法性
分数 6
作者 DS课程组
单位 浙江大学
假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序列，判断该序列是否合法。
输入格式:
输入第一行给出两个正整数 n 和 m，其中 n 是待测序列的个数，m（≤50）是堆栈的最大容量。随后 n 行，每行中给出一个仅由S和X构成的序列。序列保证不为空，且长度不超过100。
输出格式:
对每个序列，在一行中输出YES如果该序列是合法的堆栈操作序列，或NO如果不是。
输入样例：
1
2
3
4
5
| 4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX
|
输出样例：
我的错误答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
while (n--) {
stack<int> stack;
bool isWrong = true;
string str;
cin >> str;
for(int i = 0; i < str.length(); i++) {
char c = str[i];
if (c == 'S') {
if (stack.size() == m) {
break;
} else {
stack.push(1);
}
} else {
if (stack.empty()) {
break;
} else {
stack.pop();
}
}
}
if (stack.empty()) {
isWrong = false;
}
if (isWrong) {
cout << "NO" << endl;
} else {
cout << "YES" << endl;
}
}
}
|
当序列中途出现不合法操作（如栈满入栈、栈空出栈）时，虽然跳出了循环，但没有标记这种情况为 “不合法”，导致即使中途出错，只要最后栈是空的，就会误判为 “合法”。
具体错误场景分析：
以输入序列 "X"（仅一个出栈操作）为例：
- 循环开始，读取
'X'，此时栈为空，执行 break 跳出循环。
- 循环结束后，栈仍然是空的（因为没做任何操作），所以
isWrong 被设为 false。
- 最终输出
YES，但实际这个序列是不合法的（栈空时出栈）。
问题的核心在于：你的代码只检查了 “最终栈是否为空”，却没有检查 “过程中是否出现了不合法操作”。即使过程中出错（如栈满入栈、栈空出栈），只要最后栈是空的，就会被误判为合法。
修复方案：
增加一个标记（如 valid），专门记录 “过程中是否出现不合法操作”。只有当 “过程完全合法” 且 “最终栈为空” 时，才判定为 YES
答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
while (n--) {
stack<int> stack;
bool valid = true;
string str;
cin >> str;
for(int i = 0; i < str.length(); i++) {
char c = str[i];
if (c == 'S') {
if (stack.size() == m) {
valid = false;
break;
} else {
stack.push(1);
}
} else {
if (stack.empty()) {
valid = false;
break;
} else {
stack.pop();
}
}
}
if (valid && stack.empty()) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
}
|
