1. 棧的定義
后進(jìn)先出的數(shù)據(jù)格式——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 == []
比較簡(jiǎn)單就不交代了，就是增刪查的一些內(nèi)容
3 經(jīng)典例子
- 字符消消樂(lè) 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
- 引號(hào)消除 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:
# 匹配符號(hào)直接采用匹配順序
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:
# 左邊符號(hào)就放入棧
if s[i] in '{[(':
f.push(s[i])
# 不是左邊符號(hào)猬错，分為兩種情況窗看，要么是右邊符號(hào)，要么不符合要求
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
- 十進(jìn)制轉(zhuǎn)16進(jìn)制 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:
# 匹配符號(hào)直接采用匹配順序
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
-
中綴轉(zhuǎn)前倦炒、后綴表達(dá)式（leetcode 150 && 224 && 227 && 772）
定義：
image.png
中綴轉(zhuǎn)后綴
image.png
中綴轉(zhuǎn)前綴
image.png
①leetcode 150 計(jì)算后綴
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中負(fù)數(shù)除法與文中不一致显沈，python中-1/2=-1；文中-1/2=0逢唤；引入函數(shù)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 中綴轉(zhuǎn)后綴拉讯，并計(jì)算
首先是個(gè)位數(shù)的加減乘除：
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:
# 如果是數(shù)字或者字母，直接加入輸出表中
if i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or i in '0123456789':
res_lst.append(i)
# 如果是左括號(hào)鳖藕，加入棧中
elif i == '(':
tokens.push(i)
# 右括號(hào)魔慷，則把左括號(hào)前的運(yùn)算符都加到輸出表中，同時(shí)最后的左括號(hào)也刪除
elif i == ')':
while tokens.peek() != '(':
res_lst.append(tokens.pop())
tokens.pop()
# 如果是運(yùn)算符
else:
# 如果比棧頂?shù)拇笾鳎苯蛹尤霔Ｖ? # 如果小于或等于棧頂院尔，把棧中所有比該運(yùn)算符大或等于的都輸出來(lái)蜻展，加到輸出表中，直到棧頂比它大邀摆，或者空了
while not tokens.is_empty() and sequence[i] <= sequence[tokens.peek()]:
res_lst.append(tokens.pop())
tokens.push(i)
# 把運(yùn)算符加在后面
while not tokens.is_empty():
res_lst.append(tokens.pop())
return res_lst
# 計(jì)算符纵顾，本來(lái)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
# 計(jì)算后綴表達(dá)式
def calculate(s: str) -> int:
tokens = middle_to_post(s)
print(tokens)
# 使用一個(gè)棧用于壓入計(jì)算的數(shù)
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()
思考了下多位數(shù)的情況：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:
# 如果是數(shù)字或者字母隧熙，直接加入輸出表中
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())
# 如果是左括號(hào)片挂，加入棧中
if i == '(':
tokens.push(i)
# 右括號(hào)幻林，則把左括號(hào)前的運(yùn)算符都加到輸出表中贞盯，同時(shí)最后的左括號(hào)也刪除
elif i == ')':
while tokens.peek() != '(':
res.append(tokens.pop())
tokens.pop()
# 如果是運(yùn)算符
else:
# 如果比棧頂?shù)拇螅苯蛹尤霔Ｖ? # 如果小于或等于棧頂躏敢，把棧中所有比該運(yùn)算符大或等于的都輸出來(lái)件余，加到輸出表中遭居，直到棧頂比它大俱萍，或者空了
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())
# 把運(yùn)算符加在后面
while not tokens.is_empty():
res.append(tokens.pop())
return res
# 計(jì)算符，本來(lái)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
# 計(jì)算后綴表達(dá)式
def calculate(s: str) -> int:
tokens = middle_to_post(s)
print(tokens)
# 使用一個(gè)棧用于壓入計(jì)算的數(shù)
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()
