C语言前缀表达式和中缀表达式转后缀表达式

将前缀表达式和中缀表达式转换成后缀表达式的方法是类似的，都可以利用栈来实现。

对于前缀表达式，我们可以从右往左遍历，遇到操作数直接输出到后缀表达式中，遇到运算符则将其压入栈中，并将栈顶的两个操作数弹出进行运算后再将结果压入栈中。最后将栈中剩余的运算符依次弹出并输出到后缀表达式中即可。

对于中缀表达式，我们可以从左往右遍历，遇到操作数直接输出到后缀表达式中，遇到运算符则判断其与栈顶运算符的优先级，如果栈顶运算符的优先级高于或等于当前运算符，则弹出栈顶运算符并输出到后缀表达式中，直到栈为空或栈顶运算符的优先级低于当前运算符，然后将当前运算符压入栈中。最后将栈中剩余的运算符依次弹出并输出到后缀表达式中即可。

以下是 C 语言代码实现：

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

#define MAX_STACK_SIZE 100

typedef struct stack {
    char data[MAX_STACK_SIZE];
    int top;
} Stack;

void push(Stack *s, char c) {
    if (s->top == MAX_STACK_SIZE - 1) {
        printf("Stack overflow!\n");
        exit(1);
    }
    s->data[++s->top] = c;
}

char pop(Stack *s) {
    if (s->top == -1) {
        printf("Stack underflow!\n");
        exit(1);
    }
    return s->data[s->top--];
}

int is_operator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int get_operator_priority(char c) {
    if (c == '*' || c == '/') {
        return 2;
    } else if (c == '+' || c == '-') {
        return 1;
    } else {
        return 0;
    }
}

void prefix_to_postfix(char *prefix, char *postfix) {
    Stack stack;
    stack.top = -1;
    int len = strlen(prefix);
    for (int i = len - 1; i >= 0; i--) {
        if (is_operator(prefix[i])) {
            char op1 = pop(&stack);
            char op2 = pop(&stack);
            postfix[strlen(postfix)] = op1;
            postfix[strlen(postfix)] = op2;
            postfix[strlen(postfix)] = prefix[i];
            push(&stack, postfix[strlen(postfix) - 1]);
        } else {
            push(&stack, prefix[i]);
        }
    }
    while (stack.top != -1) {
        postfix[strlen(postfix)] = pop(&stack);
    }
    postfix[strlen(postfix)] = '\0';
}

void infix_to_postfix(char *infix, char *postfix) {
    Stack stack;
    stack.top = -1;
    int len = strlen(infix);
    for (int i = 0; i < len; i++) {
        if (is_operator(infix[i])) {
            while (stack.top != -1 && get_operator_priority(stack.data[stack.top]) >= get_operator_priority(infix[i])) {
                postfix[strlen(postfix)] = pop(&stack);
            }
            push(&stack, infix[i]);
        } else if (infix[i] == '(') {
            push(&stack, infix[i]);
        } else if (infix[i] == ')') {
            while (stack.top != -1 && stack.data[stack.top] != '(') {
                postfix[strlen(postfix)] = pop(&stack);
            }
            if (stack.top == -1) {
                printf("Invalid expression!\n");
                exit(1);
            }
            pop(&stack);
        } else {
            postfix[strlen(postfix)] = infix[i];
        }
    }
    while (stack.top != -1) {
        if (stack.data[stack.top] == '(') {
            printf("Invalid expression!\n");
            exit(1);
        }
        postfix[strlen(postfix)] = pop(&stack);
    }
    postfix[strlen(postfix)] = '\0';
}

int main() {
    char expression[100], postfix[100] = "";
    printf("Enter expression: ");
    gets(expression);
    infix_to_postfix(expression, postfix);
    printf("Postfix expression: %s", postfix);
    return 0;
}