表达式求值数据结构代码
时间: 2023-12-04 12:40:57 浏览: 41
以下是使用栈实现表达式求值的Python代码:
```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]
def size(self):
return len(self.items)
def infix_to_postfix(infix_expr):
prec = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}
op_stack = Stack()
postfix_list = []
token_list = infix_expr.split()
for token in token_list:
if token.isnumeric():
postfix_list.append(token)
elif token == '(':
op_stack.push(token)
elif token == ')':
top_token = op_stack.pop()
while top_token != '(':
postfix_list.append(top_token)
top_token = op_stack.pop()
else:
while (not op_stack.is_empty()) and (prec[op_stack.peek()] >= prec[token]):
postfix_list.append(op_stack.pop())
op_stack.push(token)
while not op_stack.is_empty():
postfix_list.append(op_stack.pop())
return ' '.join(postfix_list)
def postfix_eval(postfix_expr):
operand_stack = Stack()
token_list = postfix_expr.split()
for token in token_list:
if token.isnumeric():
operand_stack.push(int(token))
else:
operand2 = operand_stack.pop()
operand1 = operand_stack.pop()
result = do_math(token, operand1, operand2)
operand_stack.push(result)
return operand_stack.pop()
def do_math(op, op1, op2):
if op == '*':
return op1 * op2
elif op == '/':
return op1 / op2
elif op == '+':
return op1 + op2
else:
return op1 - op2
```
其中,`infix_to_postfix`函数将中缀表达式转换为后缀表达式,`postfix_eval`函数对后缀表达式求值,`do_math`函数实现四则运算。