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

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

中缀表达式转后缀表达式（也称为逆波兰表示法）是编译原理中的一个经典问题，下面我将提供一个完整的C语言实现，包括详细的解释。

算法思路

1. 初始化：创建一个空栈用于存放运算符，以及一个空字符串用于存放输出结果。
2. 遍历中缀表达式：
   • 如果是数字,直接添加到输出结果中。
   • 如果是左括号,压入栈中。
   • 如果是右括号,弹出栈中元素直到遇到左括号，将弹出的元素（不包括左括号）添加到输出结果中。
   • 如果是运算符：
     • 比较当前运算符与栈顶运算符的优先级
     • 如果栈顶运算符优先级更高或相等,则弹出栈顶运算符并添加到输出结果中
     • 将当前运算符压入栈中
3. 处理剩余元素：遍历结束后，将栈中剩余的所有运算符弹出并添加到输出结果中。

完整代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_EXPR_LEN 100
// 定义栈结构
typedef struct {
    char data[MAX_EXPR_LEN];
    int top;
} Stack;
// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}
// 判断栈是否为空
int isEmpty(Stack *s) {
    return s->top == -1;
}
// 判断栈是否已满
int isFull(Stack *s) {
    return s->top == MAX_EXPR_LEN - 1;
}
// 压栈
void push(Stack *s, char value) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        exit(1);
    }
    s->data[++(s->top)] = value;
}
// 弹栈
char pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        exit(1);
    }
    return s->data[(s->top)--];
}
// 查看栈顶元素
char peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        exit(1);
    }
    return s->data[s->top];
}
// 获取运算符优先级
int precedence(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '^':
            return 3;
        default:
            return 0;
    }
}
// 中缀转后缀
void infixToPostfix(char *infix, char *postfix) {
    Stack s;
    initStack(&s);
    int i, j = 0;
    char ch;
    for (i = 0; infix[i] != '\0'; i++) {
        ch = infix[i];
        // 如果是数字或字母（支持变量），直接添加到输出
        if (isalnum(ch)) {
            postfix[j++] = ch;
        }
        // 如果是左括号，压入栈中
        else if (ch == '(') {
            push(&s, ch);
        }
        // 如果是右括号，弹出栈中元素直到遇到左括号
        else if (ch == ')') {
            while (!isEmpty(&s) && peek(&s) != '(') {
                postfix[j++] = pop(&s);
            }
            if (!isEmpty(&s) && peek(&s) == '(') {
                pop(&s); // 弹出左括号但不添加到输出
            }
        }
        // 如果是运算符
        else {
            while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(ch)) {
                postfix[j++] = pop(&s);
            }
            push(&s, ch);
        }
    }
    // 弹出栈中剩余的所有运算符
    while (!isEmpty(&s)) {
        postfix[j++] = pop(&s);
    }
    postfix[j] = '\0'; // 添加字符串结束符
}
int main() {
    char infix[MAX_EXPR_LEN], postfix[MAX_EXPR_LEN];
    printf("请输入中缀表达式: ");
    fgets(infix, MAX_EXPR_LEN, stdin);
    infix[strcspn(infix, "\n")] = '\0'; // 去除换行符
    infixToPostfix(infix, postfix);
    printf("后缀表达式: %s\n", postfix);
    return 0;
}

示例运行

输入：

a+b*c

输出：

后缀表达式: abc*+

输入：

(a+b)*c

输出：

后缀表达式: ab+c*

输入：

a+b*(c^d-e)^(f+g*h)-i

输出：

后缀表达式: abcd^e-fgh*+^*+i-

代码说明

1. 栈操作：实现了基本的栈操作（初始化、压栈、弹栈、查看栈顶等）。
2. 优先级处理：precedence函数定义了不同运算符的优先级。
3. 表达式处理：
   • 数字和变量直接输出
   • 括号处理确保运算顺序
   • 运算符根据优先级决定何时压入或弹出栈
4. 边界情况：处理了栈满、栈空等异常情况。

这个实现支持基本的四则运算和括号,也可以扩展支持更多运算符和函数调用。