栈 及 中缀表达式2后缀表达式 及 计算后缀表达式
上图:delete ------> pop
append------>push—压栈
show--------->peek
#栈实现
class NullStackError(BaseException):
def __init__(self):
super().__init__("Null Stack Error!!!!")
class MyStack():
def __init__(self, len= 0, list= None):
self.__len = 0
self.__list = list
def push(self, data):
self.__list.append(data)
self.__len += 1
def pop(self):
temp = None
if self.__len == 0:
raise NullStackError
else:
temp = self.__list.pop()
self.__len -= 1
return temp
def peek(self):
if self.__len == 0:
raise NullStackError
else:
return self.__list[-1]
def length(self):
return self.__len
#表达式:前缀表达式 中缀表达式 后缀表达式------操作符+-*/
# +*bca a+b*c abc*+
# *c+ab (a+b)*c ab+c*
# /e*-cd+ab (a+b)*(c-d)/e ab+cd-*e/
#低取高存 //符号入栈 ()//
#中缀表达式2后缀表达式
# 1)遇到操作数直接拼到字符串
# 2)遇到操作符
''' a,遇到左括号
b,遇到右括号
c,遇到-+
d,遇到*/
2,计算后缀表达式
'''
def middle2after(s = ""):
rule = {"-":1,"+":1,"*":2,"/":2}
str = ""
list = []
for item in s:
if item.isalnum():
str += item
else:
if item == "(":
list.append(item)
elif item == ")":
while list[-1] != "(":
str += list.pop()
list.pop()
elif item in "+-":
if len(list) == 0:
list.append(item)
else:
while len(list) != 0 and list[-1] != "(":
str += list.pop()
list.append(item)
elif item in "*/":
list.append(item)
else:
print("表达式有问题")
while len(list) != 0:
str += list.pop()
return str
str = middle2after("1+3*(4+2)")
print(str)
#计算后缀表达式--数字入,运算符出
def middle2after(s = ""):
rule = {"-":1,"+":1,"*":2,"/":2}
str = ""
list = []
for item in s:
if item.isalnum():
str += item
else:
if item == "(":
list.append(item)
elif item == ")":
while list[-1] != "(":
str += list.pop()
list.pop()
elif item in "+-":
if len(list) == 0:
list.append(item)
else:
while len(list) != 0 and list[-1] != "(":
str += list.pop()
list.append(item)
elif item in "*/":
list.append(item)
else:
print("表达式有问题")
while len(list) != 0:
str += list.pop()
return str
#-----------------------------------------------------------------------------------------
def cal(s=""):
stack = []
for item in s:
if item.isalnum():
stack.append(item)
else:
a = float(stack.pop())
b = float(stack.pop())
if item=="-":
c = b - a
elif item=="+":
c = b + a
elif item=="*":
c = b * a
elif item=="/":
c = b / a
else:
print('后缀表达式有问题')
stack.append(c)
return stack.pop()
str = middle2after("1+3*(4+2)/5+(6+7*8-9)")
print(cal(str))