创建顺序栈的结构、出栈、入栈、取栈顶元素算法: 2.创建判断表达式括号匹配、判断运算符、运算符优先级和两数运算的函数:
时间: 2023-07-10 22:33:03 浏览: 148
1. 创建顺序栈的结构、出栈、入栈、取栈顶元素算法:
```python
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
return self.stack.pop()
def peek(self):
return self.stack[-1]
def is_empty(self):
return len(self.stack) == 0
```
其中,`push` 方法用于入栈,`pop` 方法用于出栈,`peek` 方法用于取栈顶元素,`is_empty` 方法用于判断栈是否为空。
2. 创建判断表达式括号匹配、判断运算符、运算符优先级和两数运算的函数:
```python
def is_matching_parentheses(expr):
stack = Stack()
for char in expr:
if char in '({[':
stack.push(char)
elif char in ')}]':
if stack.is_empty():
return False
elif char == ')' and stack.peek() == '(':
stack.pop()
elif char == '}' and stack.peek() == '{':
stack.pop()
elif char == ']' and stack.peek() == '[':
stack.pop()
else:
return False
return stack.is_empty()
def is_operator(char):
return char in '+-*/'
def get_operator_precedence(char):
if char in '+-':
return 1
elif char in '*/':
return 2
else:
return -1
def evaluate(expr):
operand_stack = Stack()
operator_stack = Stack()
i = 0
while i < len(expr):
if expr[i].isdigit():
j = i
while j < len(expr) and expr[j].isdigit():
j += 1
operand = int(expr[i:j])
operand_stack.push(operand)
i = j
elif is_operator(expr[i]):
while not operator_stack.is_empty() and get_operator_precedence(operator_stack.peek()) >= get_operator_precedence(expr[i]):
operator = operator_stack.pop()
operand2 = operand_stack.pop()
operand1 = operand_stack.pop()
result = evaluate_operation(operand1, operand2, operator)
operand_stack.push(result)
operator_stack.push(expr[i])
i += 1
else:
i += 1
while not operator_stack.is_empty():
operator = operator_stack.pop()
operand2 = operand_stack.pop()
operand1 = operand_stack.pop()
result = evaluate_operation(operand1, operand2, operator)
operand_stack.push(result)
return operand_stack.pop()
def evaluate_operation(operand1, operand2, operator):
if operator == '+':
return operand1 + operand2
elif operator == '-':
return operand1 - operand2
elif operator == '*':
return operand1 * operand2
elif operator == '/':
return operand1 / operand2
else:
raise ValueError('Unknown operator: ' + operator)
```
其中,`is_matching_parentheses` 函数用于判断表达式中的括号是否匹配,`is_operator` 函数用于判断一个字符是否为运算符,`get_operator_precedence` 函数用于获取一个运算符的优先级,`evaluate` 函数用于计算表达式的值,`evaluate_operation` 函数用于对两个操作数进行指定的运算。
阅读全文