​第三十九练 汉诺塔问题

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

// 定义栈结构
typedef struct {
    char *data;
    int top;
    int capacity;
} Stack;

// 初始化栈
void initializeStack(Stack *stack, int capacity) {
    stack->data = (char *)malloc(sizeof(char) * capacity);
    stack->top = -1;
    stack->capacity = capacity;
}

// 判断栈是否为空
int isEmpty(Stack *stack) {
    return stack->top == -1;
}

// 判断栈是否已满
int isFull(Stack *stack) {
    return stack->top == stack->capacity - 1;
}

// 入栈操作
void push(Stack *stack, char element) {
    if (isFull(stack)) {
        printf("Stack overflow\n");
        return;
    }
    stack->data[++stack->top] = element;
}

// 出栈操作
char pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return '\0';  // 返回空字符表示栈已空
    }
    return stack->data[stack->top--];
}

// 判断括号是否匹配
int isBracketMatch(char *expression) {
    Stack stack;
    initializeStack(&stack, 100);  // 假设表达式不超过100个字符

    while (*expression) {
        char current = *expression;
        if (current == '(' || current == '{' || current == '[') {
            push(&stack, current);
        } else if (current == ')' || current == '}' || current == ']') {
            if (isEmpty(&stack)) {
                // 栈已空，但当前字符是右括号，匹配失败
                return 0;
            }

            char top = pop(&stack);
            if ((current == ')' && top != '(') ||
                (current == '}' && top != '{') ||
                (current == ']' && top != '[')) {
                // 当前右括号与栈顶左括号不匹配，匹配失败
                return 0;
            }
        }

        expression++;
    }

    // 如果栈不为空，说明左括号多于右括号，匹配失败
    return isEmpty(&stack);
}

int main() {
    char expression[100];
    printf("Enter an expression: ");
    scanf("%s", expression);

    if (isBracketMatch(expression)) {
        printf("Brackets are balanced.\n");
    } else {
        printf("Brackets are not balanced.\n");
    }

    return 0;
}