04.2 波兰式

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

栈与前缀、中缀、后缀表达式的妙用

栈是一种基本的数据结构，而前缀、中缀和后缀表达式是数学中描述运算关系的三种不同形式。

1. 栈的基本概念

1.1 栈的特性

栈是一种遵循后进先出（Last In, First Out，LIFO）原则的数据结构。在栈中，元素的添加和删除操作只能在栈顶进行，而栈底的元素是最后被添加的，也是最后被访问的。

1.2 栈的实现方式

栈可以通过数组或链表来实现。使用数组时，需要维护一个指针指向栈顶元素；使用链表时，每个节点包含数据和指向下一个节点的引用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
示例（Python）：

```python
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)

2. 前缀表达式与栈

2.1 前缀表达式的特点

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

2.2 利用栈求值

在前缀表达式中，从右至左遍历表达式，遇到操作数就压入栈，遇到运算符就弹出栈顶的两个操作数进行运算，将结果再次压入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def evaluate_prefix(expression):
    stack = []
    operators = set(['+', '-', '*', '/'])

    tokens = expression.split()
    for token in reversed(tokens):
        if token.isdigit() or (token[0] == '-' and token[1:].isdigit()):
            stack.append(int(token))
        elif token in operators:
            operand1 = stack.pop()
            operand2 = stack.pop()
            if token == '+':
                stack.append(operand1 + operand2)
            elif token == '-':
                stack.append(operand1 - operand2)
            elif token == '*':
                stack.append(operand1 * operand2)
            elif token == '/':
                stack.append(operand1 / operand2)

    return stack[0]

3. 中缀表达式与栈

3.1 中缀表达式的特点

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

3.2 利用栈进行转换与求值

通过栈，将中缀表达式转换为后缀表达式，然后再利用栈求值。具体转换过程可以使用栈来辅助实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def infix_to_postfix(infix_expr):
    stack = []
    postfix_expr = []
    operators = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0}

    for token in infix_expr.split():
        if token.isdigit() or (token[0] == '-' and token[1:].isdigit()):
            postfix_expr.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            while stack and stack[-1] != '(':
                postfix_expr.append(stack.pop())
            stack.pop()  # 弹出左括号
        elif token in operators:
            while stack and operators[token] <= operators.get(stack[-1], 0):
                postfix_expr.append(stack.pop())
            stack.append(token)

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

    return ' '.join(postfix_expr)

4. 后缀表达式与栈

4.1 后缀表达式的特点

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

4.2 Python利用栈求值

后缀表达式的求值也可以利用栈来实现，遍历表达式，遇到操作数就压入栈，遇到运算符就弹出栈顶的两个操作数进行运算，将结果再次压入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def evaluate_postfix(expression):
    stack = []
    operators = set(['+', '-', '*', '/'])

    tokens = expression.split()
    for token in tokens:
        if token.isdigit() or (token[0] == '-' and token[1:].isdigit()):
            stack.append(int(token))
        elif token in operators:
            operand2 = stack.pop()
            operand1 = stack.pop()
            if token == '+':
                stack.append(operand1 + operand2)
            elif token == '-':
                stack.append(operand1 - operand2)
            elif token == '*':
                stack.append(operand1 * operand2)
            elif token == '/':
                stack.append(operand1 / operand2)

    return stack[0]

4.3 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
package org.example;  
  
import java.util.ArrayList;  
import java.util.List;  
import java.util.Stack;  
  
public class PolandNotation {  
    public static void main(String[] args) {  
        //定义逆波兰表达式（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);  
    }  
  
    //将逆波兰表达式，依次将数字和运算符放入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());  
    }  
}
  • 标题: 04.2 波兰式
  • 作者: moye
  • 创建于 : 2024-07-18 14:34:20
  • 更新于 : 2025-12-11 14:39:48
  • 链接: https://www.kanes.top/2024/07/18/04.2 波兰式/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
04.2 波兰式
  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. 后缀表达式与栈
      1. 1.4.1. 4.1 后缀表达式的特点
      2. 1.4.2. 4.2 Python利用栈求值
      3. 1.4.3. 4.3 Java利用栈求值