1. 栈的定义
后进先出的数据格式——LIFO
2. 用法
类代码如下
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
def is_empty(self):
return self.items == []
比较简单就不交代了，就是增删查的一些内容
3 经典例子
- 字符消消乐 Leetcode-1
代码：
def removeDuplicates(self, s: str) -> str:
stack = []
s = list(s)
for i in s:
if not stack:
stack.append(i)
elif i == stack[-1]:
stack.pop()
else:
stack.append(i)
# 字符串化
res = ''.join(stack)
return res
- 引号消除 Leetcode-20
# 栈的类
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)
def is_empty(self):
return self.items == []
class Solution:
# 匹配符号直接采用匹配顺序
def match(self, target, test):
a, b = '{[(', '}])'
return a.index(target) == b.index(test)
def isValid(self, s: str) -> bool:
f = Stack()
i = 0
flag = 1
while i < len(s) and flag == 1:
# 左边符号就放入栈
if s[i] in '{[(':
f.push(s[i])
# 不是左边符号，分为两种情况，要么是右边符号，要么不符合要求
else:
if f.is_empty():
flag = 0
else:
top = f.pop()
if not self.match(top, s[i]):
flag = 0
i = i + 1
if f.is_empty() and flag == 1:
return True
else:
return False
- 十进制转16进制 Letcode-405
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)
def is_empty(self):
return self.items == []
class Solution:
# 匹配符号直接采用匹配顺序
def toHex(self, num: int) -> str:
digits = '0123456789abcdef'
res_stack = Stack()
if num == 0:
return '0'
#采用了反码的定义
if num < 0:
num += 2 ** 32
if num > 0:
while num > 0:
rem = num % 16
res_stack.push(rem)
num = num // 16
res = ''
while not res_stack.is_empty():
res = res + digits[res_stack.pop()]
return res
-
中缀转前、后缀表达式（leetcode 150 && 224 && 227 && 772）
定义：
image.png
中缀转后缀
image.png
中缀转前缀
image.png
①leetcode 150 计算后缀
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
def is_empty(self):
return self.items == []
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
lst = Stack()
token = ['/','+','-','*']
for i in tokens:
if i not in token:
lst.push(i)
else:
a = lst.pop()
b = lst.pop()
# 注意python中负数除法与文中不一致，python中-1/2=-1；文中-1/2=0；引入函数operator.truediv
if i == '/':
res = int(operator.truediv(int(b),int(a)))
else:
res = eval(b+ i + a)
lst.push(str(res))
return int(lst.pop())
②leetcode 224 && 227 && 772 中缀转后缀，并计算
首先是个位数的加减乘除：
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)
def is_empty(self):
return self.items == []
def middle_to_post(s):
res_lst = []
tokens = Stack()
lst = s.replace(' ', '')
# 建立顺序表
sequence = {'(': 1, '+': 2, '-': 2, '*': 3, '/': 3, '^': 4}
for i in lst:
# 如果是数字或者字母，直接加入输出表中
if i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or i in '0123456789':
res_lst.append(i)
# 如果是左括号，加入栈中
elif i == '(':
tokens.push(i)
# 右括号，则把左括号前的运算符都加到输出表中，同时最后的左括号也删除
elif i == ')':
while tokens.peek() != '(':
res_lst.append(tokens.pop())
tokens.pop()
# 如果是运算符
else:
# 如果比栈顶的大，直接加入栈中
# 如果小于或等于栈顶，把栈中所有比该运算符大或等于的都输出来，加到输出表中，直到栈顶比它大，或者空了
while not tokens.is_empty() and sequence[i] <= sequence[tokens.peek()]:
res_lst.append(tokens.pop())
tokens.push(i)
# 把运算符加在后面
while not tokens.is_empty():
res_lst.append(tokens.pop())
return res_lst
# 计算符，本来eval也可以用，但是题目中禁止使用
def do_math(a, b, op):
if op == '+':
return a + b
elif op == '-':
return a - b
elif op == '*':
return a * b
elif op == '/':
return a / b
else:
return a ** b
# 计算后缀表达式
def calculate(s: str) -> int:
tokens = middle_to_post(s)
print(tokens)
# 使用一个栈用于压入计算的数
op_stack = Stack()
for token in tokens:
if token in '0123456789':
op_stack.push(int(token))
elif token in '+-*/^':
b = op_stack.pop()
a = op_stack.pop()
op_stack.push(do_math(a, b, token))
return op_stack.pop()
思考了下多位数的情况：224 && 227 && 772均成功AC
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)
def is_empty(self):
return self.items == []
def middle_to_post(s):
res = []
res_lst = Stack()
tokens = Stack()
lst = s.replace(' ', '')
print(lst)
# 建立顺序表
sequence = {'(': 1, '+': 2, '-': 2, '*': 3, '/': 3, '^': 4}
for i in lst:
# 如果是数字或者字母，直接加入输出表中
if i.isdigit():
if not res_lst.is_empty() and type(res_lst.peek()) is int:
res_lst.push(res_lst.pop() * 10 + int(i))
else:
res_lst.push(int(i))
continue
elif not i.isdigit() and len(res_lst.items) >= 1:
res.append(res_lst.pop())
# 如果是左括号，加入栈中
if i == '(':
tokens.push(i)
# 右括号，则把左括号前的运算符都加到输出表中，同时最后的左括号也删除
elif i == ')':
while tokens.peek() != '(':
res.append(tokens.pop())
tokens.pop()
# 如果是运算符
else:
# 如果比栈顶的大，直接加入栈中
# 如果小于或等于栈顶，把栈中所有比该运算符大或等于的都输出来，加到输出表中，直到栈顶比它大，或者空了
while not tokens.is_empty() and sequence[i] <= sequence[tokens.peek()]:
res.append(tokens.pop())
tokens.push(i)
if len(res_lst.items) >= 1:
res.append(res_lst.pop())
# 把运算符加在后面
while not tokens.is_empty():
res.append(tokens.pop())
return res
# 计算符，本来eval也可以用，但是题目中禁止使用
def do_math(a, b, op):
if op == '+':
return a + b
elif op == '-':
return a - b
elif op == '*':
return a * b
elif op == '/':
return a / b
else:
return a ** b
# 计算后缀表达式
def calculate(s: str) -> int:
tokens = middle_to_post(s)
print(tokens)
# 使用一个栈用于压入计算的数
op_stack = Stack()
for token in tokens:
if isinstance(token, (int, list)):
op_stack.push(token)
elif token in '+-*/^':
b = op_stack.pop()
a = op_stack.pop()
op_stack.push(do_math(a, b, token))
return op_stack.pop()
