中缀表达式转换后缀表达式的C语言代码

中缀表达式转换为后缀表达式的算法可以使用栈来实现，以下是基本的 C 语言代码实现：

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

#define MAX_SIZE 100

// 定义运算符栈结构体
typedef struct operator_stack {
    char data[MAX_SIZE]; // 栈数据
    int top; // 栈顶指针
} OperatorStack;

// 定义操作数栈结构体
typedef struct operand_stack {
    int data[MAX_SIZE]; // 栈数据
    int top; // 栈顶指针
} OperandStack;

// 判断字符是否为运算符
int is_operator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

// 获取运算符优先级
int get_priority(char c) {
    int priority = 0;
    switch (c) {
        case '+':
        case '-':
            priority = 1;
            break;
        case '*':
        case '/':
            priority = 2;
            break;
        default:
            break;
    }
    return priority;
}

// 运算符栈入栈
void push_operator(OperatorStack *stack, char c) {
    if (stack->top >= MAX_SIZE) {
        printf("Operator stack overflow.\n");
        exit(1);
    }
    stack->data[++stack->top] = c;
}

// 运算符栈出栈
char pop_operator(OperatorStack *stack) {
    if (stack->top < 0) {
        printf("Operator stack underflow.\n");
        exit(1);
    }
    return stack->data[stack->top--];
}

// 获取运算符栈栈顶元素
char get_top_operator(OperatorStack *stack) {
    if (stack->top < 0) {
        printf("Operator stack underflow.\n");
        exit(1);
    }
    return stack->data[stack->top];
}

// 操作数栈入栈
void push_operand(OperandStack *stack, int num) {
    if (stack->top >= MAX_SIZE) {
        printf("Operand stack overflow.\n");
        exit(1);
    }
    stack->data[++stack->top] = num;
}

// 操作数栈出栈
int pop_operand(OperandStack *stack) {
    if (stack->top < 0) {
        printf("Operand stack underflow.\n");
        exit(1);
    }
    return stack->data[stack->top--];
}

// 中缀表达式转后缀表达式
void infix_to_postfix(char *infix, char *postfix) {
    OperatorStack operator_stack; // 运算符栈
    OperandStack operand_stack; // 操作数栈
    int i, num, len;
    char c, top_operator, *p;

    len = strlen(infix);
    operator_stack.top = -1;
    operand_stack.top = -1;
    p = infix;
    while (*p != '\0') {
        if (isdigit(*p)) {
            // 如果是数字，将其入操作数栈
            num = 0;
            while (isdigit(*p)) {
                num = num * 10 + (*p - '0');
                p++;
            }
            push_operand(&operand_stack, num);
        } else if (is_operator(*p)) {
            // 如果是运算符，将其入运算符栈
            while (operator_stack.top >= 0 && get_priority(get_top_operator(&operator_stack)) >= get_priority(*p)) {
                // 如果当前运算符优先级小于等于栈顶运算符优先级，将栈顶运算符出栈并加入后缀表达式中
                top_operator = pop_operator(&operator_stack);
                postfix[strlen(postfix)] = top_operator;
                postfix[strlen(postfix)] = ' ';
            }
            push_operator(&operator_stack, *p);
            p++;
        } else if (*p == '(') {
            // 如果是左括号，将其入运算符栈
            push_operator(&operator_stack, *p);
            p++;
        } else if (*p == ')') {
            // 如果是右括号，将栈内左括号之后的运算符出栈并加入后缀表达式中，左括号出栈
            while (operator_stack.top >= 0 && get_top_operator(&operator_stack) != '(') {
                top_operator = pop_operator(&operator_stack);
                postfix[strlen(postfix)] = top_operator;
                postfix[strlen(postfix)] = ' ';
            }
            if (operator_stack.top >= 0 && get_top_operator(&operator_stack) == '(') {
                pop_operator(&operator_stack);
            }
            p++;
        } else {
            // 如果是空格或其他字符，跳过
            p++;
        }
    }

    // 将运算符栈中的运算符出栈并加入后缀表达式中
    while (operator_stack.top >= 0) {
        top_operator = pop_operator(&operator_stack);
        postfix[strlen(postfix)] = top_operator;
        postfix[strlen(postfix)] = ' ';
    }

    // 将操作数栈中的操作数出栈并加入后缀表达式中
    while (operand_stack.top >= 0) {
        num = pop_operand(&operand_stack);
        sprintf(postfix + strlen(postfix), "%d ", num);
    }
}

int main() {
    char infix[MAX_SIZE], postfix[MAX_SIZE];

    printf("Enter the infix expression: ");
    fgets(infix, MAX_SIZE, stdin);
    infix[strlen(infix) - 1] = '\0'; // 去掉输入字符串的换行符

    infix_to_postfix(infix, postfix);

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

    return 0;
}