1.栈
先进后出
Stack通常的操作：
Stack()建立一个空的栈对象push()压入栈pop()出栈peek()查看顶层元素isEmpty()判断是否为空size()返回元素个数
1.1 实现一个简单的栈
借助list实现简单的栈
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
ret = self.stack[-1]
self.stack = self.stack[0:-1]
return ret
def peek(self):
if not self.isEmpty():
return self.stack[-1]
else:raise Exception("栈为空")
def isEmpty(self):
return len(self.stack) == 0
def size(self):
return len(self.stack)
def __str__(self):
return self.stack.__str__()
if __name__ == '__main__':
stack = Stack()
print(stack.isEmpty())
stack.push("hello")
print(stack)
print(stack.isEmpty())
print(stack.peek())
print(stack.pop())
print(stack)
out;
True
['hello']
False
hello
hello
[]
1.2 栈的应用：后缀表达式
-
计算后缀表达式：
从左到右遍历后缀表达式，遇到数字压入栈，遇到符号出栈两个数字，然后将计算的结果压入栈。
-
将中缀表达式转换为后缀表达式：
规则： 从左到右遍历中缀表达式中的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号则要分为两种情况： 1）是括号时，如果是左括号，直接将左括号入栈，如果是右括号则栈顶元素依次出栈并输出，直到有一个左括号出栈（出栈的左括号不输出到后缀表达式）。 2）是运算符号时，如果栈顶符号为左括号，则直接将这个运算符号入栈。栈顶符号不为左括号时，如果该运算符号优先级比栈顶运算符号高则入栈，比栈顶符号低或者相等时则栈顶元素依次出栈并输出直到栈为空或者栈顶为左括号为止，==然后将这个符号入栈==。 最后将栈顶符号依次出栈并输出，得到的结果即为最终的后缀表达式。
在编写算法的时候可以将上述两步合并为一步：
用一个栈 data 保存运算数字，一个栈 opt 保存运算符号。
从左到右遍历中缀表达式，如果是数字就入栈 data，如果是符号，以下四种情况直接将符号入栈 opt：
-
栈为空；
-
栈顶为左括号；
-
该符号为左括号；
-
该运算符号优先级比栈顶符号高。
如果是右括号，则执行一次计算 步骤：从 opt 出栈一个运算符号，从 data 出栈两个数字进行一次运算并将结果入栈 data。重复执行该计算步骤，直到 opt 栈顶为左括号，然后将该左括号出栈；如果该符号优先级低于 opt 栈顶符号或 者与栈顶符号优先级相同时，重复执行与之前相同的计算步骤，直到 opt 栈为空，若中途 opt 栈顶符 号为左括号则停止执行计算步骤。中缀表达式遍历完成后，继续执行之前的计算步骤直到 opt 栈为空。
def compare(opt1, opt2):
"""
比较优先级大小，opt1优先级高True，opt2优先级高False
:param opt1:
:param opt2:
:return: opt1优先级高True，opt2优先级高False
"""
return opt1 in ["*", "/"] and opt2 in ["+", "-"]
def getValue(data:Stack,opt:Stack):
"""
计算方法，从data中取出两个数字，从opt中取出一个符号，进行计算后压入data栈
:param data:数字栈
:param opt:符号栈
:return:
"""
op = opt.pop()
num1 = data.pop()
num2 = data.pop()
if op == "+":
ret = num2 + num1
elif op == "-":
ret = num2 - num1
elif op == "*":
ret = num2 * num1
elif op == "/":
ret = num2 / num1
data.push(ret)
def solution(s:str, data:Stack, opt:Stack):
i = 0
while i < len(exp):
# 如果是数字，就进入data栈。
if s[i].isdigit():
start = i
while True:
if i+1 < len(s) and s[i + 1].isdigit():
i += 1
else:
data.push(int(s[start:i + 1]))
break
# 如果是符号，就进入opt栈，需要进行情况讨论。
else:
# 栈顶符号位(或栈为空，直接入栈
if opt.isEmpty() or opt.peek() == "(":
opt.push(s[i])
# 符号是(或者优先级高于栈顶元素，直接入栈
elif s[i] == "(" or compare(s[i],opt.peek()):
opt.push(s[i])
# 符号是)则开始进行运算
elif s[i] == ")":
while True:
if opt.peek()=="(":
opt.pop()
break
getValue(data,opt)
# 符号栈不为空，且本次符号优先级不大于栈顶符号优先级，则进行计算，最后进栈本符号
else:
while not opt.isEmpty() and not compare(s[i],opt.peek()):
if opt.isEmpty() or opt.peek()=="(":
break
getValue(data,opt)
opt.push(s[i])
i += 1
while not opt.isEmpty():
getValue(data,opt)
return data.pop()
if __name__ == '__main__':
exp = "(9+((3-1)*3+10/2))*2"
data = Stack()
opt = Stack()
print(solution(exp, data, opt))