编写程序,借助顺序栈判断一个字符串是否为对称串。
时间: 2024-10-18 09:21:22 浏览: 4
编写一个程序来判断一个字符串是否是对称串(也称为回文字符串),你可以采用顺序栈数据结构来辅助实现。以下是步骤:
1. 首先,创建一个空的栈,并将字符串的第一个字符压入栈中。
2. 然后从第二个字符开始遍历字符串,对比栈顶元素与当前字符是否相等。
- 如果相等,则继续遍历下一个字符;
- 如果不相等,则说明不是对称串,返回false;
3. 对于每个遍历到的字符,将其压入栈中。
4. 当所有字符都检查完,如果栈不为空,继续取出栈顶元素并与当前位置的字符比较,直到栈变为空。如果所有对应位置的字符都匹配,那么该字符串就是对称串,返回true。
以下是一个简单的Python示例:
```python
def is_palindrome(s):
stack = []
for char in s:
stack.append(char)
while len(stack) > 0:
top_char = stack.pop()
if top_char != s[-len(stack)-1]:
return False
return True
# 测试
print(is_palindrome("madam")) # 输出:True
print(is_palindrome("hello")) # 输出:False
```
相关问题
用C语言代码编写程序,利用顺序栈判断一个字符串是否为对称串
在C语言中,我们可以使用顺序栈数据结构来判断一个字符串是否是对称串。对称串是指从前往后读和从后往前读是一样的。以下是简单的步骤和代码实现:
首先,创建一个函数`is_palindrome()`,它接受一个字符数组作为输入,并使用一个栈来辅助判断:
```c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 定义栈结构体
typedef struct {
char* data;
int top;
int capacity;
} Stack;
// 初始化栈
void init(Stack* stack, int size) {
stack->data = (char*)malloc(size * sizeof(char));
stack->top = -1;
stack->capacity = size;
}
// 入栈操作
void push(Stack* stack, char c) {
if(stack->top == stack->capacity - 1) {
stack->capacity *= 2; // 当满时,容量翻倍
stack->data = (char*)realloc(stack->data, stack->capacity * sizeof(char)); // 扩容内存
}
stack->data[++stack->top] = c;
}
// 出栈操作
char pop(Stack* stack) {
if(stack->top == -1) return '\0'; // 栈空则返回结束标志
return stack->data[stack->top--];
}
// 判断字符串是否为对称串
int is_palindrome(const char* str) {
Stack stack;
init(&stack, 10); // 初始化一个大小为10的栈
for(int i = 0; str[i] != '\0'; i++) {
push(&stack, str[i]); // 依次将字符入栈
}
for(int i = 0; i <= stack.top / 2; i++) { // 只需遍历一半字符,因为另一半已经在栈里了
if(pop(&stack) != str[i]) { // 如果当前字符和对应位置的字符不同,则不是对称串
return 0;
}
}
return 1; // 如果全部匹配,则是对称串
}
int main() {
const char* test_strs[] = {"abcba", "abccba", "hello"};
for(const char* str : test_strs) {
int result = is_palindrome(str);
printf("%s is a palindrome? %d\n", str, result);
}
return 0;
}
```
C语言利用顺序栈判断一个字符串是否为对称串
在C语言中,我们可以使用顺序栈(也称为数组栈)来检查一个字符串是否是对称串。对称串是指从前往后读和从后往前读是一样的字符串,例如 "madam" 和 "level"。
以下是简单的步骤:
1. 首先,创建一个栈并初始化为空,然后将字符串的首字符压入栈中。
2. 接下来,遍历字符串的剩余部分,依次取出每个字符并与栈顶元素比较。如果相等,则继续处理下一个字符;如果不等,则字符串不是对称的,可以结束判断。
3. 每次遍历时都要记得弹出栈顶元素,直到遍历完整个字符串。如果最终栈为空,说明所有的字符都找到了对应的位置,且它们成对存在,所以原始字符串是对称的。
4. 如果遍历结束后还有非空栈,说明有一半以上的字符未找到对应的另一半,因此原字符串不对称。
下面是伪代码示例:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100
bool isPalindrome(char str[]) {
int stack[MAX_SIZE];
int top = -1;
// 将字符串首字符压入栈
for (int i = 0; str[i] != '\0'; i++) {
stack[++top] = str[i];
// 双指针法,一个向前,一个向后
if (i + 1 < strlen(str)) { // 避免越界
if (str[i] != str[i+1]) {
return false; // 对称串条件不满足,直接返回false
}
} else { // 到了字符串末尾
while (top >= 0) { // 逐个对比栈顶元素与前半部分字符
if (stack[top] != str[i-top-1]) {
return false;
}
top--;
}
return true; // 所有元素均匹配,返回true
}
}
}
// 主函数演示
int main() {
char str[] = "madam";
if (isPalindrome(str)) {
printf("'%s' is a palindrome.\n", str);
} else {
printf("'%s' is not a palindrome.\n", str);
}
return 0;
}
```
阅读全文