C语言实现中缀表达式转后缀表达式

这是一个使用 C 语言实现中缀表达式转后缀表达式的代码。代码利用栈数据结构，根据运算符优先级进行转换。

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

// 定义栈结构
typedef struct {
    char data;
    struct StackNode* next;
} StackNode;

// 创建空栈
StackNode* createStack() {
    return NULL;
}

// 判断栈是否为空
int isStackEmpty(StackNode* stack) {
    return stack == NULL;
}

// 入栈
void push(StackNode** stack, char data) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    newNode->data = data;
    newNode->next = *stack;
    *stack = newNode;
}

// 出栈
char pop(StackNode** stack) {
    if (isStackEmpty(*stack)) {
        printf("Error: Stack is empty\n");
        exit(EXIT_FAILURE);
    }
    char data = (*stack)->data;
    StackNode* temp = *stack;
    *stack = (*stack)->next;
    free(temp);
    return data;
}

// 获取栈顶元素
char peek(StackNode* stack) {
    if (isStackEmpty(stack)) {
        printf("Error: Stack is empty\n");
        exit(EXIT_FAILURE);
    }
    return stack->data;
}

// 判断操作符优先级
int getPrecedence(char operator) {
    if (operator == '+' || operator == '-')
        return 1;
    else if (operator == '*' || operator == '/')
        return 2;
    else if (operator == '^')
        return 3;
    else
        return 0;
}

// 将中缀表达式转换为后缀表达式
void infixToPostfix(char* infixExpression) {
    StackNode* stack = createStack();
    int i = 0;
    while (infixExpression[i] != '\0') {
        if (isdigit(infixExpression[i]) || isalpha(infixExpression[i])) {
            printf("%c", infixExpression[i]);
        }
        else if (infixExpression[i] == '(') {
            push(&stack, infixExpression[i]);
        }
        else if (infixExpression[i] == ')') {
            while (!isStackEmpty(stack) && peek(stack) != '(') {
                printf("%c", pop(&stack));
            }
            if (isStackEmpty(stack) || peek(stack) != '(') {
                printf("Error: Invalid expression\n");
                exit(EXIT_FAILURE);
            }
            pop(&stack); // 弹出'(' 
        }
        else {
            while (!isStackEmpty(stack) && getPrecedence(infixExpression[i]) <= getPrecedence(peek(stack))) {
                printf("%c", pop(&stack));
            }
            push(&stack, infixExpression[i]);
        }
        i++;
    }
    while (!isStackEmpty(stack)) {
        if (peek(stack) == '(' || peek(stack) == ')') {
            printf("Error: Invalid expression\n");
            exit(EXIT_FAILURE);
        }
        printf("%c", pop(&stack));
    }
}

int main() {
    char infixExpression[100];
    printf("Enter an infix expression: ");
    scanf("%s", infixExpression);
    printf("Postfix expression: ");
    infixToPostfix(infixExpression);
    printf("\n");
    return 0;
}

代码首先定义了栈结构 StackNode，并创建了相应的栈操作函数，包括 createStack()、isStackEmpty()、push()、pop() 和 peek()。

接下来定义了 getPrecedence() 函数，用于获取操作符的优先级。

infixToPostfix() 函数则是核心转换函数，它使用栈来存储运算符，并根据运算符的优先级进行转换。

最后，main() 函数中获取用户输入的中缀表达式，并调用 infixToPostfix() 函数进行转换，最终输出转换后的后缀表达式。

这个代码示例演示了如何使用栈将中缀表达式转换为后缀表达式，同时解释了代码的关键部分，并提供了详细的注释。你可以将代码复制到你的 C 语言环境中进行测试。