C语言实现字符序列对称性判断算法

#include <stdio.h> #include <stdlib.h> #include <stdbool.h>

#define STACK_INIT_SIZE 100 // 定义栈的初始大小 #define STACK_INCREMENT 10 // 定义栈的增量

typedef struct { char *base; // 栈底指针 char *top; // 栈顶指针 int size; // 栈的当前大小 } Stack;

// 初始化栈 bool InitStack(Stack *S) { S->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char)); if (!S->base) { return false; } S->top = S->base; S->size = STACK_INIT_SIZE; return true; }

// 入栈 bool Push(Stack *S, char e) { if (S->top - S->base >= S->size) { // 栈满，追加存储空间 S->base = (char *)realloc(S->base, (S->size + STACK_INCREMENT) * sizeof(char)); if (!S->base) { return false; } S->top = S->base + S->size; S->size += STACK_INCREMENT; } *(S->top) = e; S->top++; return true; }

// 出栈 bool Pop(Stack *S, char *e) { if (S->top == S->base) { return false; } S->top--; *e = *(S->top); return true; }

// 判断栈是否为空 bool StackEmpty(Stack *S) { if (S->top == S->base) { return true; } return false; }

// 销毁栈 bool DestroyStack(Stack *S) { free(S->base); S->base = NULL; S->top = NULL; S->size = 0; return true; }

// 判断字符序列是否对称 bool Symmetry(char al[]) { Stack S; if (!InitStack(&S)) { return false; } int i = 0; char e; while (al[i] != '@') { if (al[i] == '&') { // 遇到&, 弹出栈顶元素并比较 if (!Pop(&S, &e)) { DestroyStack(&S); return false; } if (e != al[i+1]) { DestroyStack(&S); return false; } i += 2; } else { // 其他字符入栈 if (!Push(&S, al[i])) { DestroyStack(&S); return false; } i++; } } // 判断栈中是否还有元素 if (!StackEmpty(&S)) { DestroyStack(&S); return false; } DestroyStack(&S); return true; }

int main() { char al[] = "a+b&b+a@"; if (Symmetry(al)) { printf("字符序列对称\n"); } else { printf("字符序列不对称\n"); } return 0; }