建立顺序栈,实现入栈、出栈、获取栈顶元素操作,并利用顺序栈实现表达式的求解
时间: 2024-05-14 19:17:55 浏览: 79
基于顺序栈的复杂表达式的求解
以下是基于 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 evaluate_expression(expression):
stack = Stack()
for char in expression:
if char.isdigit():
stack.push(int(char))
else:
right_operand = stack.pop()
left_operand = stack.pop()
if char == '+':
result = left_operand + right_operand
elif char == '-':
result = left_operand - right_operand
elif char == '*':
result = left_operand * right_operand
elif char == '/':
result = left_operand / right_operand
stack.push(result)
return stack.pop()
```
其中 Stack 类实现了基本的栈操作,evaluate_expression 函数利用栈来求解表达式。这个函数首先创建一个空栈,然后遍历整个表达式。如果当前字符是数字,则将其转换为整数并入栈。否则,弹出栈顶的两个元素,计算它们的运算结果并将结果入栈。最终,栈中剩下的就是整个表达式的求解结果。
例如,对于表达式 "3 4 + 5 * 6 -",其后缀表达式对应的栈操作如下:
| 字符 | 操作 | 栈 |
|------|----------------------------------|------|
| 3 | 入栈 | [3] |
| 4 | 入栈 | [3, 4] |
| + | 弹出栈顶两个元素,计算结果入栈 | [7] |
| 5 | 入栈 | [7, 5] |
| * | 弹出栈顶两个元素,计算结果入栈 | [35] |
| 6 | 入栈 | [35, 6] |
| - | 弹出栈顶两个元素,计算结果入栈 | [29] |
因此,evaluate_expression("3 4 + 5 * 6 -") 的返回值为 29。
阅读全文