04.2 波兰式
栈与前缀、中缀、后缀表达式的妙用
栈是一种基本的数据结构,而前缀、中缀和后缀表达式是数学中描述运算关系的三种不同形式。
1. 栈的基本概念
1.1 栈的特性
栈是一种遵循后进先出(Last In, First Out,LIFO)原则的数据结构。在栈中,元素的添加和删除操作只能在栈顶进行,而栈底的元素是最后被添加的,也是最后被访问的。
1.2 栈的实现方式
栈可以通过数组或链表来实现。使用数组时,需要维护一个指针指向栈顶元素;使用链表时,每个节点包含数据和指向下一个节点的引用。
示例(Python):
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 利用栈求值
在前缀表达式中,从右至左遍历表达式,遇到操作数就压入栈,遇到运算符就弹出栈顶的两个操作数进行运算,将结果再次压入栈。
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 利用栈进行转换与求值
通过栈,将中缀表达式转换为后缀表达式,然后再利用栈求值。具体转换过程可以使用栈来辅助实现。
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利用栈求值
后缀表达式的求值也可以利用栈来实现,遍历表达式,遇到操作数就压入栈,遇到运算符就弹出栈顶的两个操作数进行运算,将结果再次压入栈。
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利用栈求值
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
System.out.println("rpnlist = " + rpnList);
int res = calculate(rpnList);
System.out.println(res);
}
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;
}
//创建一个栈
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());
}
} ```