数据结构——编程实现中缀表达式转成后缀表达式

中缀表达式：运算符在操作数中间 例如3+4,3*4

后缀表达式：运算符在操作数的后面 例如3 4+，3 4*

计算机在运算时，要把中缀表达式转成前缀表达式（波兰式）或后缀表达式（逆波兰式），因为计算机遍历中缀表达式时的时间复杂度太大

举例：3+4*2-2/(1+1)+5=3+8-1+5=15

转成后缀表达式为：3 4 2 *+2 1 1 +/ -5+

计算机运算过程：计算机逐个遍历，直到遍历到运算符，遍历到运算符后将该运算符的前两个操作数（双目运算符）进行运算

3 4 2 *+2 1 1 +/ -5+下一步为3 8 + 2 2 / - 5 +

笔试/填空题求解方法：

加括号，放后面

中缀表达式 ：3+4*2-2/(1+1)+5

在不改变优先级的前提下加括号

（（（3+（4*2））-（ 2 /  ( 1 + 1 ) ））+ 5 ）

把运算符放在对应括号的后面

（（（3（4 2）*）+（ 2  ( 1  1 ) +）/ ）- 5 ）+

得到后缀表达式：

           3   4  2   *    +    2     1  1   +   /     - 5     +

同理后缀表达式转成中缀表达式：加括号，放前面

算法实现：

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

#define MAX 100  

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

// 栈操作函数  
void initStack(Stack* s) {  
    s->top = -1;  
}  

int isFull(Stack* s) {  
    return s->top == MAX - 1;  
}  

int isEmpty(Stack* s) {  
    return s->top == -1;  
}  

void push(Stack* s, char element) {  
    if (!isFull(s)) {  
        s->data[++s->top] = element;  
    } else {  
        printf("栈满，无法压入元素 %c\n", element);  
    }  
}  

char pop(Stack* s) {  
    if (!isEmpty(s)) {  
        return s->data[s->top--];  
    }  
    return '\0'; // 返回空字符表示栈为空  
}  

char peek(Stack* s) {  
    if (!isEmpty(s)) {  
        return s->data[s->top];  
    }  
    return '\0';  
}  

// 判断运算符优先级  
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 j = 0;  

    for (int i = 0; infix[i] != '\0'; i++) {  
        char current = infix[i];  

        if (isalnum(current)) { // 如果是数字或字母，直接添加到后缀表达式  
            postfix[j++] = current;  
        } else if (current == '(') {  
            push(&s, current);  
        } else if (current == ')') {  
            while (!isEmpty(&s) && peek(&s) != '(') {  
                postfix[j++] = pop(&s);  
            }  
            pop(&s); // 弹出 '('  
        } else { // 运算符  
            while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(current)) {  
                postfix[j++] = pop(&s);  
            }  
            push(&s, current);  
        }  
    }  

    // 弹出栈中剩余的运算符  
    while (!isEmpty(&s)) {  
        postfix[j++] = pop(&s);  
    }  

    postfix[j] = '\0'; // 添加字符串结束符  
}  

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

    printf("请输入中缀表达式: ");  
    scanf("%s", infix);  

    infixToPostfix(infix, postfix);  
    printf("后缀表达式为: %s\n", postfix);  

    return 0;  
}