c语言应用栈编程实现字符串消消乐,把字符串相邻的相同字符消除,所有相邻的相同字符被消除后,剩余字符会重新拼接成新的字符串,再按照相同的规则消除字符,直到所有相邻的字符都不相同或者变成空串为止,输出结果,消除为空串输出YES,否则输出NO。
时间: 2024-10-24 07:07:23 浏览: 6
在C语言中,实现字符串消消乐(也称为异位词删除游戏)可以通过维护一个栈来跟踪当前字符序列,以及一个额外的变量记录已查看过的字符。以下是一个简单的步骤:
1. 创建两个全局变量:一个栈`char stack[MAX_LEN]`(假设MAX_LEN是字符串的最大长度),用于存储字符;另一个布尔变量`visited[ch]`(其中ch是字符),用于标记字符是否已被查看过。
```c
#define MAX_LEN 1000
char stack[MAX_LEN];
bool visited['z'+1]; // 使用ASCII码范围作为索引
int top = -1;
```
2. 定义一个函数`stringSolve(char str[])`,接收输入字符串`str`:
```c
void stringSolve(char str[]) {
int i;
// 初始化已查看过的字符
memset(visited, false, sizeof(visited));
// 将字符串中的每个字符逐个加入栈中
for (i = 0; str[i]; ++i) {
if (!visited[str[i]]) {
stack[++top] = str[i];
visited[str[i]] = true;
}
}
// 当栈非空时继续处理
while (top > 0) {
// 如果栈顶两字符相同且均未被查看过
if (top >= 2 && stack[top] == stack[top - 1]) {
--top; // 删除栈顶字符
visited[stack[top]] = false; // 更新已查看状态
} else {
break; // 否则跳出循环
}
}
// 输出最终结果
if (top == -1)
printf("YES\n");
else
printf("NO\n");
}
```
3. 主函数中读取输入字符串,并调用`stringSolve`函数:
```c
int main() {
char input[100];
printf("请输入字符串:");
fgets(input, sizeof(input), stdin);
stringSolve(input);
return 0;
}
```
在这个过程中,我们遍历输入字符串,将未见过的字符压入栈中。然后,我们在栈中寻找连续的相同字符,如果找到,则从栈顶移除它们。重复此过程,直到栈为空或者无法找到更多的连续相同字符。
阅读全文