第四十二练 检测循环括号

#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--];
}

// 获取栈顶元素
char peek(Stack *stack) {
    if (isEmpty(stack)) {
        return '\0';  // 返回空字符表示栈已空
    }
    return stack->data[stack->top];
}

// 判断运算符的优先级
int getPriority(char operator) {
    switch (operator) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;  // 非运算符返回0
    }
}

// 中缀表达式转后缀表达式
void infixToPostfix(char *infixExpression, char *postfixExpression) {
    Stack stack;
    initializeStack(&stack, 100);  // 假设表达式不超过100个字符

    int length = strlen(infixExpression);
    int j = 0;  // 用于记录后缀表达式的下标

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

        if (isalnum(current)) {
            // 如果是字母或数字，直接输出到后缀表达式
            postfixExpression[j++] = current;
        } else if (current == '(') {
            // 如果是左括号，入栈
            push(&stack, current);
        } else if (current == ')') {
            // 如果是右括号，将栈中的运算符出栈并输出到后缀表达式，直到遇到左括号
            while (!isEmpty(&stack) && peek(&stack) != '(') {
                postfixExpression[j++] = pop(&stack);
            }
            pop(&stack);  // 弹出左括号
        } else {
            // 如果是运算符，比较优先级并进行相应处理
            while (!isEmpty(&stack) && getPriority(peek(&stack)) >= getPriority(current)) {
                postfixExpression[j++] = pop(&stack);
            }
            push(&stack, current);
        }
    }

    // 将栈中剩余的运算符输出到后缀表达式
    while (!isEmpty(&stack)) {
        postfixExpression[j++] = pop(&stack);
    }

    // 添加字符串结束符
    postfixExpression[j] = '\0';
}

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

    // 假设后缀表达式不超过两倍的中缀表达式长度
    char postfixExpression[2 * strlen(infixExpression)];

    infixToPostfix(infixExpression, postfixExpression);

    printf("Postfix expression: %s\n", postfixExpression);

    return 0;
}