题解 | 好串

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

#define MAX_SIZE 100000
//将ab两个符号看成是括号的左边和右边，a为左，b为右，原理与括号匹配一致
//链式栈
typedef struct Node
{
    char data;
    struct Node* next;
}Node;

typedef struct 
{
    Node* top;
} LinkedStack;

//初始化链式栈
void initLinkedStack(LinkedStack* stack)
{
    stack->top = NULL;
}

//检查栈是否为空
bool isEmpty(LinkedStack* stack)
{
    return stack->top == NULL;
}

//入栈操作
void push(LinkedStack* stack, char data)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    if(newNode == NULL)
    {
        printf("newNode create falied\n");
        return;
    }
    newNode->data = data;
    newNode->next = stack->top;
    stack->top = newNode;
}

//出栈操作
void pop(LinkedStack* stack)
{
    //先判断栈是否为空
    if(isEmpty(stack))
    {
        printf("Stack is Empty\n");
        return;
    }
    Node* temp = stack->top;
    char data = temp->data;
    stack->top = temp->next;
    free(temp);
}

//获取栈顶元素
char peek(LinkedStack* stack)
{
    if(isEmpty(stack))
    {
        printf("Stack is Empty\n");
        return 1;
    }
    return stack->top->data;
}

//释放栈内存
void freeStack(LinkedStack* stack)
{
    while(!isEmpty(stack))
    {
        pop(stack);
    }
}

bool isGoodString(char* s)
{
    LinkedStack stack;
    initLinkedStack(&stack);

    for(int i = 0; s[i] != '\0'; i++)
    {
        if(s[i] == 'a')
        {
            push(&stack, s[i]);
        }
        else
        {
            if(isEmpty(&stack))
            {
                return false;
            }

            char temp = peek(&stack);
            if(s[i] == 'b' && temp != 'a')
            {
                return false;
            }

            pop(&stack);
        }
    }
    return isEmpty(&stack);
}

int main()
{
    LinkedStack stack;
    LinkedStack* stack_ptr = &stack;
    initLinkedStack(stack_ptr);
    char data[MAX_SIZE] = {'\0'};
    scanf("%s",data);
    getchar();

    if(isGoodString(data))
    {
        printf("Good\n");
    }
    else
    {
        printf("Bad\n");
    }

    freeStack(stack_ptr);

    return 0;
}