中缀表达式转前缀或后缀表达式

​ 前缀(后缀)表达式可以在不使用"()"时保证表达式不产生歧义,更适合计算机计算。

此处以后缀为例:

​ *a+b = ab+ a-b*c = abc -

方法:

1.创建栈
2.从左向右顺序获取中缀表达式

​ a.数字直接输出

​ b.运算符

​ 情况一：遇到左括号直接入栈，遇到右括号将栈中左括号之后入栈的运算符全部弹栈输出，同时左括号出栈但是不输出。

​ 情况二：遇到乘号和除号直接入栈，直到遇到优先级比它更低的运算符，依次弹栈。

​ 情况三：遇到加号和减号，如果此时栈空，则直接入栈，否则，将栈中优先级高的运算符依次弹栈（注意：加号和减号属于同一个优先级，所以也依次弹栈）直到栈空或则遇到左括号为止，停止弹栈。（因为左括号要匹配右括号时才弹出）。

​ 情况四：获取完后，将栈中剩余的运算符号依次弹栈输出

例:比如将:2*(9+6/3-5)+4转化为后缀表达式 2 9 6 3 / +5 - * 4 +

中缀转后缀代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>  // 提供 isdigit 函数
#include <string.h> // 提供 strlen 函数

#define MAX 100  // 栈的最大容量

char stack[MAX];  // 栈
int top = -1;     // 栈顶指针

// 判断操作符优先级
int precedence(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    }
    return 0;
}

// 判断是否是操作符
int isOperator(char ch) {
    return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}

// 将操作符压入栈中
void push(char op) {
    if (top < MAX - 1) {
        stack[++top] = op;
    } else {
        printf("Stack overflow\n");
    }
}

// 从栈中弹出操作符
char pop() {
    if (top != -1) {
        return stack[top--];
    } else {
        printf("Stack underflow\n");
        return '\0';
    }
}

// 查看栈顶操作符
char peek() {
    if (top != -1) {
        return stack[top];
    }
    return '\0';
}

// 中缀转后缀
void infixToPostfix(char *infix) {
    char postfix[MAX] = {0};
    int i, j = 0;
    for (i = 0; i < strlen(infix); i++) {
        char ch = infix[i];

        if (isdigit(ch) || isalpha(ch)) {  // 是操作数直接输出
            postfix[j++] = ch;
        } else if (ch == '(') {            // 左括号压栈
            push(ch);
        } else if (ch == ')') {            // 遇到右括号，弹出操作符直到左括号
            while (top != -1 && peek() != '(') {
                postfix[j++] = pop();
            }
            pop(); // 弹出左括号但不加到后缀表达式中
        } else if (isOperator(ch)) {       // 遇到操作符
            while (top != -1 && precedence(peek()) >= precedence(ch)) {
                postfix[j++] = pop();
            }
            push(ch);
        }
    }

    while (top != -1) {  // 处理剩余的操作符
        postfix[j++] = pop();
    }

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

int main() {
    char infix[MAX];
    printf("Enter infix expression: ");
    scanf("%s", infix);
    infixToPostfix(infix);
    return 0;
}

中缀转前缀代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define MAX 100

char stack[MAX];
int top = -1;

// 判断操作符优先级
int precedence(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    }
    return 0;
}

// 判断是否是操作符
int isOperator(char ch) {
    return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}

// 将操作符压入栈中
void push(char op) {
    if (top < MAX - 1) {
        stack[++top] = op;
    } else {
        printf("Stack overflow\n");
    }
}

// 从栈中弹出操作符
char pop() {
    if (top != -1) {
        return stack[top--];
    } else {
        printf("Stack underflow\n");
        return '\0';
    }
}

// 查看栈顶操作符
char peek() {
    if (top != -1) {
        return stack[top];
    }
    return '\0';
}

// 反转字符串
void reverse(char *exp) {
    int len = strlen(exp);
    for (int i = 0; i < len / 2; i++) {
        char temp = exp[i];
        exp[i] = exp[len - i - 1];
        exp[len - i - 1] = temp;
    }
}

// 中缀转前缀
void infixToPrefix(char *infix) {
    char prefix[MAX] = {0};
    int len = strlen(infix);
    
    // 反转中缀表达式
    reverse(infix);
    
    for (int i = 0; i < len; i++) {
        if (infix[i] == '(') {
            infix[i] = ')';
        } else if (infix[i] == ')') {
            infix[i] = '(';
        }
    }
    
    int j = 0;
    for (int i = 0; i < len; i++) {
        char ch = infix[i];

        if (isdigit(ch) || isalpha(ch)) {  // 是操作数直接输出
            prefix[j++] = ch;
        } else if (ch == '(') {            // 左括号压栈
            push(ch);
        } else if (ch == ')') {            // 遇到右括号，弹出操作符直到左括号
            while (top != -1 && peek() != '(') {
                prefix[j++] = pop();
            }
            pop(); // 弹出左括号但不加到前缀表达式中
        } else if (isOperator(ch)) {       // 遇到操作符
            while (top != -1 && precedence(peek()) > precedence(ch)) {
                prefix[j++] = pop();
            }
            push(ch);
        }
    }

    while (top != -1) {  // 处理剩余的操作符
        prefix[j++] = pop();
    }

    // 反转前缀表达式
    reverse(prefix);

    printf("Prefix: %s\n", prefix);
}

int main() {
    char infix[MAX];
    printf("Enter infix expression: ");
    scanf("%s", infix);
    infixToPrefix(infix);
    return 0;
}