用Python创建顺序栈的结构、出栈、入栈、取栈顶元素算法: 2. 创建判断表达式括号匹配、判断运算符、运算符优先级和两数运算的函数: 3.实现中缀表达式求值算法:
时间: 2023-12-27 11:02:51 浏览: 81
我用Python写的一些算法
5星 · 资源好评率100%
1. 创建顺序栈的结构、出栈、入栈、取栈顶元素算法:
顺序栈可以使用Python中的列表来实现。定义一个空列表来表示空栈,使用append()方法实现入栈操作,使用pop()方法实现出栈操作并返回被移除元素。使用[-1]索引来取栈顶元素。
以下是示例代码:
```python
class Stack():
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[-1]
```
2. 创建判断表达式括号匹配、判断运算符、运算符优先级和两数运算的函数:
可以使用栈来实现表达式求值。先将操作数压入栈中,当遇到运算符时,取出相应的操作数按照运算符计算,将结果再次压入栈中。最后栈中剩余的操作数即为最终结果。
以下是示例代码:
```python
def is_operator(c):
return c in ['+', '-', '*', '/']
def operator_priority(operator):
return {'+': 1, '-': 1, '*': 2, '/': 2}[operator]
def calculate(num1, num2, operator):
if operator == '+':
return num1 + num2
elif operator == '-':
return num1 - num2
elif operator == '*':
return num1 * num2
elif operator == '/':
return num1 / num2
def evaluate_expression(expression):
stack_num = []
stack_operator = []
for c in expression:
if c.isdigit():
stack_num.append(int(c))
elif is_operator(c):
while stack_operator and operator_priority(stack_operator[-1]) >= operator_priority(c):
num2 = stack_num.pop()
num1 = stack_num.pop()
operator = stack_operator.pop()
result = calculate(num1, num2, operator)
stack_num.append(result)
stack_operator.append(c)
elif c == '(':
stack_operator.append(c)
elif c == ')':
while stack_operator and stack_operator[-1] != '(':
num2 = stack_num.pop()
num1 = stack_num.pop()
operator = stack_operator.pop()
result = calculate(num1, num2, operator)
stack_num.append(result)
stack_operator.pop()
while stack_operator:
num2 = stack_num.pop()
num1 = stack_num.pop()
operator = stack_operator.pop()
result = calculate(num1, num2, operator)
stack_num.append(result)
return stack_num[0]
```
3. 实现中缀表达式求值算法:
实现中缀表达式求值算法的思路与上述样例类似。在算法中,需要将中缀表达式转为后缀表达式,在后缀表达式中进行求值。
以下是示例代码:
```python
def infix_to_postfix(expression):
stack_operator = []
postfix = []
for c in expression:
if c.isdigit():
postfix.append(c)
elif is_operator(c):
while stack_operator and stack_operator[-1] != '(' and operator_priority(stack_operator[-1]) >= operator_priority(c):
postfix.append(stack_operator.pop())
stack_operator.append(c)
elif c == '(':
stack_operator.append(c)
elif c == ')':
while stack_operator and stack_operator[-1] != '(':
postfix.append(stack_operator.pop())
stack_operator.pop()
while stack_operator:
postfix.append(stack_operator.pop())
return postfix
def evaluate_infix_expression(expression):
postfix = infix_to_postfix(expression)
stack = []
for c in postfix:
if c.isdigit():
stack.append(int(c))
elif is_operator(c):
num2 = stack.pop()
num1 = stack.pop()
result = calculate(num1, num2, c)
stack.append(result)
return stack[0]
```
阅读全文