"""
注意，这里只考虑了输入表达式中，参与运算的书都是正数的情况
"""
class Linked_Stack:
class Node:
def __init__(self,value,next=None):
self.value=value
self.next=next
"""
LIFO栈的实现(利用链表)
"""
def __init__(self):
"""
创建一个空栈
"""
self._items=None
self._size=0
def push(self,value):
"""
添加一个元素入栈
:return:
"""
self._items=self.Node(value,self._items)
self._size+=1
def pop(self):
"""
一个元素出栈
:return:
"""
if self.isEmpty():
raise KeyError("The stack is empty")
item_value=self._items.value
self._items=self._items.next
self._size-=1
return item_value
def peek(self):
if self.isEmpty():
raise KeyError("The stack is empty")
item_value=self._items.value
return item_value
def isEmpty(self):
"""
判断栈是否为空
:return:
"""
return self._items==None
def __extensionts(self):
"""
扩展的功能函数
:param item:
:return:
"""
tempList=[]
def visitNode(node):
if not node is None:
visitNode(node.next)
tempList.append(node.value)
return tempList
visitNode(self._items)
return tempList
def __getitem__(self, key):
"""
支持对容器 self[key] 操作
:param key:
:return:
"""
result_list=self.__extensionts()
return result_list[key]
def __iter__(self):
"""
支持迭代操作
:return:
"""
result_list=self.__extensionts()
return iter(result_list)
def __str__(self):
"""
利用list的str实现
:return:
"""
result_list=self.__extensionts()
return str(result_list)
def size(self):
"""
返回
:return:
"""
return self._size
class Evaluate:
"""
利用栈计算
"""
def expression_splite(self,expression):
"""
将传入表达式解析为 表达式解析单元列表
:param expression:
:return:
"""
#去除字符串表达式首尾的特殊字符
expression=expression.strip()
#表达式解析结果列表
result=[]
number_item="" #用于存储拼接出来的数字单元
#遍历表达式中每一个元素
for cursor_index in range(0,len(expression)):
#当前元素的值
item=expression[cursor_index]
#如果当前元素为操作符,就将操作符直加入操作符栈
if item in ["(",")","+","-","*","/"]:
#如果是开头出现的"(",就只将"("加入结果列表
if item=="(" and cursor_index==0:
result.append(item)
#如果遇到其他运算符，或者"("，就将他们前面的拼接的数字单元加入结果集合中
else:
#如果当前拼接出来的运算数不为空
if number_item!="":
#将拼接出来的运算数加入栈
result.append(float(number_item))
number_item=""
#将运算符加入栈
result.append(item)
#如果当前元素是数字，那就拼接数字,与符号
elif item in ["0","1","2","3","4","5","6","7","8","9","."]:
number_item+=item
#如果当前元素是最后一个元素,就将最后一个元素加入结果集中
if cursor_index==len(expression)-1:
result.append(float(number_item))
#返回 表达式 字符串解析结果
return result
def generate_postfix_expression(self,expression):
"""
将输入的中缀表达式转化为后缀表达式
:param expression:
:return:
"""
#获取表达式列表
linked_list=self.expression_splite(expression)
#存储操作符的栈
oper_stack=Linked_Stack()
#存储后缀表达式处理结果的栈
postfix_expression_stack=Linked_Stack()
#操作符 优先级 列表
oper_dict={'*':2,'/':2,'+':1,'-':1}
for item in linked_list:
#如果当前元素是操作符,处理操作符
if item in ['(',')','+','-','*','/']:
#如果当前操作符栈为空，就当前操作符加入操作符栈中
if oper_stack.isEmpty():
oper_stack.push(item)
#如果当前操作符栈不为空，进行相应处理
else:
#如果当前元素为 '(‘,就将'('如栈
if item=='(':
oper_stack.push("(")
#如果当前元素是右括号,执行出栈操作，并将弹出栈的元素加入后缀表达式栈，知道弹出栈的是左括号，括号不加入后缀表达式栈
elif item==")":
oper=oper_stack.pop()
while oper!="(":
postfix_expression_stack.push(oper)
oper=oper_stack.pop()
#如果当前元素是运算符
else:
#弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
#弹出所有大于等于运算符栈的栈定元素(如果有右括号，则截止到右边括号)出现,并将他们加入
oper=oper_stack.peek()
while oper!="(" and oper_dict[oper]>=oper_dict[item]:
#栈顶元素出栈
oper=oper_stack.pop()
postfix_expression_stack.push(oper)
#获取新的栈顶元素的值
oper=oper_stack.peek()
#将当前元素item 加入操作符栈中
oper_stack.push(item)
#如果当前元素是数字,就将数字入后缀表达式栈
else:
postfix_expression_stack.push(item)
#处理完成表达式列表中每个元素后，将操作符栈的所有元素出栈并加入 后缀表达式栈
while not oper_stack.isEmpty():
oper=oper_stack.pop()
postfix_expression_stack.push(oper)
#返回后缀表达式栈
return postfix_expression_stack
def calculate_expression(self,expression):
"""
计算表达式的值
:param expression:
:return:
"""
#获取后缀表达式列表
postfix_expression_stack=self.generate_postfix_expression(expression)
#关于后缀表达式栈的缩影
cursor_postfix_expression=0
#操作数堆栈
number_stack=Linked_Stack()
#处理栈中的每个元素
while cursor_postfix_expression<postfix_expression_stack.size():
#获取当前栈索引所指向的栈中元素
item=postfix_expression_stack[cursor_postfix_expression]
#如果当前元素是运算符
if item in ["+","-","*","/"]:
#将参与运算的两个元素入栈,注意：这里一定要是 Arg_01_item 运算符 Arg_02_item,因为，Arg_02_item是栈顶元素也就是后如栈的(运算符右边的数)，Arg_01_item是先入栈的(运算符左边的数)
Arg_02_item=number_stack.pop()
Arg_01_item=number_stack.pop()
if item=="+":
val=Arg_01_item+Arg_02_item
elif item=="-":
val=Arg_01_item-Arg_02_item
elif item=="*":
val=Arg_01_item*Arg_02_item
elif item=="/":
val=Arg_01_item/Arg_02_item
else:
pass
#将运算后的结果加入运算符栈中
number_stack.push(val)
#如果当前元素是数字
else:
#就将数字加入运算数栈
number_stack.push(item)
#索引自加1
cursor_postfix_expression+=1
#返回最终运算结果,也就是运算数栈中的最后一个元素
return number_stack.pop()
def check_expression_split():
"""
测试 表达式 元素解析列表
:return:
"""
expression_01="((2+18)/12+144/6.89)/90.28"
expression_list_01=Evaluate().expression_splite(expression_01)
print(expression_01," >>>>>>>> ",expression_list_01)
expression_02="89+(89/33.3-12*(3+23)*4)"
expression_list_02=Evaluate().expression_splite(expression_02)
print(expression_02," >>>>>>>> ",expression_list_02)
def check_stack():
"""
测试 链表栈 的运行是否正常
:return:
"""
stack_linked=Linked_Stack()
for _ in range(10,20):
stack_linked.push(_)
print("0>>>>>>>>>>:",stack_linked.size())
print("-----"*10)
for _ in stack_linked:
print("1>>>>>>>>>>:",stack_linked.peek())
print("-----"*10)
for _ in range(0,10):
print("1_1>>>>>>>>:",stack_linked[_])
print("-----"*10)
for _ in stack_linked:
print("2>>>>>>>>>>:",_)
print("-----"*10)
print("3>>>>>>>>>>>>>:",stack_linked.isEmpty())
print("-----"*10)
for _ in range(0,10):
pop_value=stack_linked.pop()
print("4>>>>>>>>>>:",pop_value)
print("-----"*10)
print("5>>>>>>>>>>:",stack_linked.isEmpty())
def check_postfix_expression():
"""
检查后缀表达式的输出结果
:return:
"""
expression_01="(2+18)/12"
expression_list_01=Evaluate().generate_postfix_expression(expression_01)
print(expression_01," >>>>>>>> ",expression_list_01)
expression_02="((2+18)/12+144/6.89)/90.28"
expression_list_02=Evaluate().generate_postfix_expression(expression_02)
print(expression_02," >>>>>>>> ",expression_list_02)
expression_03="89+(89/33.3-12*(3+23)*4)"
expression_list_03=Evaluate().generate_postfix_expression(expression_03)
print(expression_03," >>>>>>>> ",expression_list_03)
def check_calculation():
"""
检查计算的结果(运用后缀表达式)
:return:
"""
expression_01="(2+18)/12"
expression_list_01=Evaluate().generate_postfix_expression(expression_01)
val=Evaluate().calculate_expression(expression_01)
print(expression_01,"=",eval(expression_01)," >>>>>>>> ",expression_list_01,"=",val)
expression_02="((2+18)/12+144/6.89)/90.28"
expression_list_02=Evaluate().generate_postfix_expression(expression_02)
val=Evaluate().calculate_expression(expression_02)
print(expression_02,"=",eval(expression_02)," >>>>>>>> ",expression_list_02,"=",val)
expression_03="89+(89/33.3-12*(3+23)*4)"
expression_list_03=Evaluate().generate_postfix_expression(expression_03)
val=Evaluate().calculate_expression(expression_03)
print(expression_03,"=",eval(expression_03)," >>>>>>>> ",expression_list_03,"=",val)
if __name__=="__main__":
check_expression_split()
print("-"*1000)
check_stack()
print("-"*1000)
check_postfix_expression()
print("-"*1000)
check_calculation()
“”“
输出结果
((2+18)/12+144/6.89)/90.28 >>>>>>>> ['(', '(', 2.0, '+', 18.0, ')', '/', 12.0, '+', 144.0, '/', 6.89, ')', '/', 90.28]
89+(89/33.3-12*(3+23)*4) >>>>>>>> [89.0, '+', '(', 89.0, '/', 33.3, '-', 12.0, '*', '(', 3.0, '+', 23.0, ')', '*', 4.0, ')']
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
0>>>>>>>>>>: 10
--------------------------------------------------
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
--------------------------------------------------
1_1>>>>>>>>: 10
1_1>>>>>>>>: 11
1_1>>>>>>>>: 12
1_1>>>>>>>>: 13
1_1>>>>>>>>: 14
1_1>>>>>>>>: 15
1_1>>>>>>>>: 16
1_1>>>>>>>>: 17
1_1>>>>>>>>: 18
1_1>>>>>>>>: 19
--------------------------------------------------
2>>>>>>>>>>: 10
2>>>>>>>>>>: 11
2>>>>>>>>>>: 12
2>>>>>>>>>>: 13
2>>>>>>>>>>: 14
2>>>>>>>>>>: 15
2>>>>>>>>>>: 16
2>>>>>>>>>>: 17
2>>>>>>>>>>: 18
2>>>>>>>>>>: 19
--------------------------------------------------
3>>>>>>>>>>>>>: False
--------------------------------------------------
4>>>>>>>>>>: 19
4>>>>>>>>>>: 18
4>>>>>>>>>>: 17
4>>>>>>>>>>: 16
4>>>>>>>>>>: 15
4>>>>>>>>>>: 14
4>>>>>>>>>>: 13
4>>>>>>>>>>: 12
4>>>>>>>>>>: 11
4>>>>>>>>>>: 10
--------------------------------------------------
5>>>>>>>>>>: True
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(2+18)/12 >>>>>>>> [2.0, 18.0, '+', 12.0, '/']
((2+18)/12+144/6.89)/90.28 >>>>>>>> [2.0, 18.0, '+', 12.0, '/', 144.0, 6.89, '/', '+', 90.28, '/']
89+(89/33.3-12*(3+23)*4) >>>>>>>> [89.0, 89.0, 33.3, '/', 12.0, 3.0, 23.0, '+', '*', 4.0, '*', '-', '+']
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(2+18)/12 = 1.6666666666666667 >>>>>>>> [2.0, 18.0, '+', 12.0, '/'] = 1.6666666666666667
((2+18)/12+144/6.89)/90.28 = 0.24996147019035977 >>>>>>>> [2.0, 18.0, '+', 12.0, '/', 144.0, 6.89, '/', '+', 90.28, '/'] = 0.24996147019035977
89+(89/33.3-12*(3+23)*4) = -1156.3273273273273 >>>>>>>> [89.0, 89.0, 33.3, '/', 12.0, 3.0, 23.0, '+', '*', 4.0, '*', '-', '+'] = -1156.3273273273273
”“”
栈_01_栈的应用:表达式求值
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
