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

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

#define MAX_SIZE 100

typedef struct {
    char data[MAX_SIZE];
    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_SIZE - 1;
}

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

char pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\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 isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')';
}

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

void infixToPostfix(char *infix, char *postfix) {
    Stack s;
    initStack(&s);

    int i = 0;
    int j = 0;

    while (infix[i] != '#') {
        if (!isOperator(infix[i])) {
            postfix[j++] = infix[i++];
        } else if (infix[i] == '(') {
            push(&s, infix[i++]);
        } else if (infix[i] == ')') {
            while (!isEmpty(&s) && peek(&s) != '(') {
                postfix[j++] = pop(&s);
            }
            if (!isEmpty(&s) && peek(&s) != '(') {
                printf("Invalid expression\n");
                exit(1);
            } else {
                pop(&s);
            }
            i++;
        } else {
            while (!isEmpty(&s) && getPriority(infix[i]) <= getPriority(peek(&s))) {
                postfix[j++] = pop(&s);
            }
            push(&s, infix[i++]);
        }
    }

    while (!isEmpty(&s)) {
        postfix[j++] = pop(&s);
    }

    postfix[j] = '\0';
}

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

    scanf("%s", infix);
    infixToPostfix(infix, postfix);
    printf("%s\n", postfix);

    return 0;
}

该程序使用 C 语言实现了将中缀表达式转换为后缀表达式的算法，并使用了栈数据结构来存储运算符。程序首先定义了一个 Stack 结构体，用于表示栈，并定义了几个函数来实现栈的基本操作：initStack 初始化栈，isEmpty 判断栈是否为空，isFull 判断栈是否已满，push 将元素压入栈顶，pop 弹出栈顶元素，peek 获取栈顶元素。程序还定义了两个函数：isOperator 判断字符是否为运算符，getPriority 获取运算符的优先级。最后，infixToPostfix 函数实现了中缀表达式转换为后缀表达式的算法。该函数使用循环遍历中缀表达式，遇到操作数则直接输出，遇到左括号则压入栈，遇到右括号则弹出栈顶元素直到遇到左括号，遇到运算符则根据运算符的优先级和栈顶元素的优先级进行处理，最终将转换后的后缀表达式输出。该程序还包含了示例输入和输出，可以帮助读者理解程序的运行过程。

使用方法

将代码保存为一个 .c 文件（例如 infix_to_postfix.c）。
使用 C 编译器编译代码：gcc infix_to_postfix.c -o infix_to_postfix
运行程序：./infix_to_postfix
在程序运行时输入中缀表达式，以 '#' 结尾，程序会输出对应的后缀表达式。

示例输入和输出

输入：

a+b-a*((c+d)/e-f)+g#

输出：

ab+acd+e/f-*-g+