04.2 波兰式

2024 年 7 月 18 日 星期四
1

04.2 波兰式

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

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

1. 栈的基本概念

1.1 栈的特性

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

1.2 栈的实现方式

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

示例（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 利用栈求值

在前缀表达式中，从右至左遍历表达式，遇到操作数就压入栈，遇到运算符就弹出栈顶的两个操作数进行运算，将结果再次压入栈。
python 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 利用栈进行转换与求值

通过栈，将中缀表达式转换为后缀表达式，然后再利用栈求值。具体转换过程可以使用栈来辅助实现。
python 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利用栈求值

后缀表达式的求值也可以利用栈来实现，遍历表达式，遇到操作数就压入栈，遇到运算符就弹出栈顶的两个操作数进行运算，将结果再次压入栈。
python 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利用栈求值
java 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 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 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());  
}

} ```

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...