04.3 中缀转后缀

moye Lv6
  2024-07-18 14:35:09 2024-07-18 14:35:09 创建   2025-12-11 14:39:48 2025-12-11 14:39:48 更新      

中缀表达式转后缀表达式与栈的妙用

1. 中缀表达式与后缀表达式

1.1 中缀表达式的特点

中缀表达式是日常最常见的数学表达形式，其中运算符位于两个操作数之间，例如：3 + 4 * 5。

1.2 后缀表达式的特点

后缀表达式是将运算符置于操作数之后的形式，例如：3 4 5 * +。

2. 中缀表达式转后缀表达式

2.1 转换规则

中缀表达式转后缀表达式的转换规则如下：

  1. 从左至右遍历中缀表达式的每个元素。
  2. 如果是操作数，直接输出到后缀表达式。
  3. 如果是运算符：
    • 如果栈为空，或者栈顶元素是左括号 “(“，直接将运算符压入栈。
    • 如果运算符优先级高于栈顶运算符，直接将运算符压入栈。
    • 否则，将栈顶运算符弹出并输出到后缀表达式，然后重复比较直到满足前两个条件。
  4. 如果是左括号 “(“，将其压入栈。
  5. 如果是右括号 “)”，将栈中的运算符依次弹出并输出到后缀表达式，直到遇到左括号 “(“。
1
2
3
4
1) 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2) 从左至右扫描中缀表达式；
3) 遇到操作数时，将其压s2；
4) 遇到运算符时，比较其与s1栈顶运算符的优先级：
1
2
3
4
5
6
7
8
9
1.如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
2.否则，若优先级比栈顶运算符的高，也将运算符压入s1；
3.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较；
5) 遇到括号时：
(1) 如果是左括号“(”，则直接压入s1  
(2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6) 重复步骤2至5，直到表达式的最右边
7) 将s1中剩余的运算符依次弹出并压入s2
8)  依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

2.2 转换实例

以中缀表达式 3 + 4 * 5 为例，转换过程如下：

1
2
1. 输入：3 + 4 * 5
2. 输出：3 4 5 * +

3. 利用栈求值后缀表达式

3.1 求值规则

利用栈求值后缀表达式的规则如下：

  1. 从左至右遍历后缀表达式的每个元素。
  2. 如果是操作数，压入栈。
  3. 如果是运算符，从栈中弹出两个操作数，进行运算，并将结果压入栈。

3.2 求值实例

以后缀表达式 3 4 5 * + 为例，求值过程如下：

1
2
3
4
5
6
7
8
1. 输入：3 4 5 * +
2. 栈操作：
   - 遇到 3，压入栈： [3]
   - 遇到 4，压入栈： [3, 4]
   - 遇到 5，压入栈： [3, 4, 5]
   - 遇到 *，弹出 5 和 4，计算结果 20，压入栈： [3, 20]
   - 遇到 +，弹出 20 和 3，计算结果 23，压入栈： [23]
3. 最终结果：23

4. 示例：Python 实现中缀转后缀与求值

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
class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    def size(self):
        return len(self.items)

def infix_to_postfix(infix_expr):
    stack = Stack()
    postfix_expr = []
    operators = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0}

    for token in infix_expr.split():
        if token.isdigit():
            postfix_expr.append(token)
        elif token == '(':
            stack.push(token)
        elif token == ')':
            while stack.peek() != '(':
                postfix_expr.append(stack.pop())
            stack.pop()  # 弹出左括号
        elif token in operators:
            while stack.size()

 > 0 and operators[token] <= operators.get(stack.peek(), 0):
                postfix_expr.append(stack.pop())
            stack.push(token)

    while not stack.is_empty():
        postfix_expr.append(stack.pop())

    return ' '.join(postfix_expr)

def evaluate_postfix(postfix_expr):
    stack = Stack()
    operators = set(['+', '-', '*', '/'])

    tokens = postfix_expr.split()
    for token in tokens:
        if token.isdigit():
            stack.push(int(token))
        elif token in operators:
            operand2 = stack.pop()
            operand1 = stack.pop()
            if token == '+':
                stack.push(operand1 + operand2)
            elif token == '-':
                stack.push(operand1 - operand2)
            elif token == '*':
                stack.push(operand1 * operand2)
            elif token == '/':
                stack.push(operand1 / operand2)

    return stack.pop()

# 示例
infix_expression = "3 + 4 * 5"
postfix_expression = infix_to_postfix(infix_expression)
result = evaluate_postfix(postfix_expression)
print(f"中缀表达式：{infix_expression}")
print(f"后缀表达式：{postfix_expression}")
print(f"求值结果：{result}")

4. 示例：Java 实现中缀转后缀与求值

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
package org.example;  
  
import java.util.ArrayList;  
import java.util.List;  
import java.util.Objects;  
import java.util.Stack;  
import java.util.stream.Collectors;  
  
public class PolandNotation {  
  
//    1 + ( ( 2 + 3 )× 4) - 5转成中缀表达式，对字符串操作麻烦，所以先转成list  
    //操作list，转成后缀表达式  
  
  
    public static void main(String[] args) {  
  
        String expression = "1+((2+3)*4)-5";  
        System.out.println("中缀表达式是：" + toInfixExpressionList(expression));  
        System.out.println("后缀表达式是：" + parseSuffixExpressionList(toInfixExpressionList(expression)));  
  
        System.out.println("expression = " + calculate(parseSuffixExpressionList(toInfixExpressionList(expression))));  
        //定义逆波兰表达式（3+4）*5-6  3 4 + 5 * 6 -  
        String suffixExpression = "3 4 + 5 * 6 - ";  
        // suffixExpression放入arraylist中  
        // suffixExpression传递给一个方法，遍历ArrayList,配合栈，完成计算  
        List<String> rpnList = getListString(suffixExpression);  
        System.out.println("rpnlist = " + rpnList);  
  
        int res = calculate(rpnList);  
        System.out.println(res);  
    }  
  
    public static List<String> parseSuffixExpressionList(List<String> ls) {  
        Stack<String> s1 = new Stack<String>();  
//        Stack<String> s2 = new Stack<String>();//保存中间结果  
  
        List<String> s2 = new ArrayList<String>();  
//        遍历ls,  
        for (String item : ls) {  
            if (item.matches("\\d+")) {  
                s2.add(item);  
            } else if (item.equals("(")) {  
                s1.push(item);  
            } else if (item.equals(")")) {  
                while (!s1.peek().equals("(")) {  
                    s2.add(s1.pop());  
  
                }  
                s1.pop();//消除括号  
            } else {  
                //当item的运算符优先级小于等于s1栈顶运算符优先级，  
                //s1栈顶运算符弹栈 压入s2中，  
                while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {  
                    s2.add(s1.pop());  
                }  
                s1.push(item);  
            }  
        }  
//        将s1中剩余的运算符依次弹出并压入s2  
        while (s1.size() != 0) {  
            s2.add(s1.pop());  
        }  
  
        return s2;  
    }  
  
    public static List<String> toInfixExpressionList(String s) {  
        ArrayList<String> ls = new ArrayList<String>();  
        int i = 0;//用于遍历s  
        String str1;//对多位数进行拼接  
        char c;//每遍历一个字符就放入c  
        do {  
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {//非数字  
                ls.add("" + c);  
                i++;  
            } else {  
                //是数字，考虑多位数，需要拼接  
                str1 = "";  
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {  
                    //取出的仍然是数字  
                    str1 += c;  
                    i++;  
                }  
                ls.add(str1);  
            }  
        } while (i < s.length());  
//        for(String item :ls){  
//            if (item.equals(" ")){  
//                ls.remove(item);  
//            }  
//        }  
//        ls.removeIf(str -> str.isEmpty());  
//        ls.stream().map(s -> s.replaceAll("\n",",").trim()).collect(Collectors.toList());  
//        ls.stream().map(s1 -> s1.replaceAll("\n", ",").trim()).collect(Collectors.toList());  
        return ls;  
    }  
  
    //将逆波兰表达式，依次将数字和运算符放入Array List中  
    public static List<String> getListString(String suffixExpression) {  
        //分割suffixExpression  
        String[] s = suffixExpression.split(" ");  
        ArrayList<String> list = new ArrayList<>();  
        for (String ele : s) {  
            list.add(ele);  
        }  
        return list;  
    }  
  
    public static int calculate(List<String> ls) {  
        //创建一个栈  
        Stack<String> stack = new Stack<>();  
        // 遍历ls  
        for (String item : ls) {  
            // 正则表达式取数  
            if (item.matches("\\d+")) {  
                stack.push(item);  
            } else {  
                int num1 = Integer.parseInt(stack.pop());  
                int num2 = Integer.parseInt(stack.pop());  
                int res;  
                if (item.equals("+")) {  
                    res = num1 + num2;  
                } else if (item.equals("-")) {  
                    res = num2 - num1;  
                } else if (item.equals("*")) {  
                    res = num2 * num1;  
                } else if (item.equals("/")) {  
                    res = num1 / num2;  
                } else {  
                    throw new RuntimeException("运算符有误");  
                }  
                stack.push(res + "");  
            }  
        }  
        return Integer.parseInt(stack.pop());  
    }  
}  
  
//返回运算符对应的优先级  
class Operation {  
    public static int ADD = 1;  
    public static int SUB = 1;  
    public static int MUL = 2;  
    public static int DIV = 2;  
  
    public static int getValue(String operation) {  
        int result = 0;  
        switch (operation) {  
            case "+":  
                result = ADD;  
                break;  
            case "-":  
                result = SUB;  
                break;  
            case "*":  
                result = MUL;  
                break;  
            case "/":  
                result = DIV;  
                break;  
            default:  
//                throw new RuntimeException("不存在");  
                System.out.println("不存在");  
                break;  
        }  
        return result;  
    }  
}

5. 总结

通过栈的巧妙运用，可以高效地将中缀表达式转换为后缀表达式，并在后缀表达式上进行求值。这种方法简化了表达式的处理逻辑，使得程序更容易理解和实现。

  • 标题: 04.3 中缀转后缀
  • 作者: moye
  • 创建于 : 2024-07-18 14:35:09
  • 更新于 : 2025-12-11 14:39:48
  • 链接: https://www.kanes.top/2024/07/18/04.3 中缀转后缀/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
04.3 中缀转后缀
  1. 1. 中缀表达式转后缀表达式与栈的妙用
    1. 1.1. 1. 中缀表达式与后缀表达式
      1. 1.1.1. 1.1 中缀表达式的特点
      2. 1.1.2. 1.2 后缀表达式的特点
    2. 1.2. 2. 中缀表达式转后缀表达式
      1. 1.2.1. 2.1 转换规则
      2. 1.2.2. 2.2 转换实例
    3. 1.3. 3. 利用栈求值后缀表达式
      1. 1.3.1. 3.1 求值规则
      2. 1.3.2. 3.2 求值实例
    4. 1.4. 4. 示例：Python 实现中缀转后缀与求值
    5. 1.5. 4. 示例：Java 实现中缀转后缀与求值
    6. 1.6. 5. 总结