第四十三练 表达式求值

#include <stdio.h>
#include <stdlib.h>
#include <string.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 hasRedundantBrackets(char *expression) {
    Stack stack;
    initializeStack(&stack, 100);  // 假设表达式不超过100个字符

    int length = strlen(expression);

    for (int i = 0; i < length; i++) {
        char current = expression[i];

        if (current == '(' || current == '{' || current == '[') {
            // 如果是左括号，入栈
            push(&stack, current);
        } else if (current == ')' || current == '}' || current == ']') {
            // 如果是右括号，检查栈顶是否是左括号，如果是则存在循环括号
            if (isEmpty(&stack)) {
                return 1;  // 存在右括号但没有左括号，循环括号
            }

            char top = pop(&stack);

            if ((current == ')' && top != '(') ||
                (current == '}' && top != '{') ||
                (current == ']' && top != '[')) {
                return 1;  // 右括号与栈顶左括号不匹配，循环括号
            }
        }
    }

    return 0;  // 没有循环括号
}

int main() {
    char expression[100];
    printf("Enter an expression: ");
    fgets(expression, sizeof(expression), stdin);

    if (hasRedundantBrackets(expression)) {
        printf("The expression has redundant brackets.\n");
    } else {
        printf("The expression does not have redundant brackets.\n");
    }

    return 0;
}