什么是栈
在数据结构中栈和队列可以理解为一种容器。它们也是一种简单的缓存结构，只支持数据的存储和访问。栈中的元素之间相互没有任何和的具体关系，只有时间的相互顺序。栈的相关操作包括数据元素的存入、访问、删除等。
Python中栈的实现
class Stack:
def __init__(self):
self.__items = []
def is_empty(self):
return self.__items == []
def push(self, item):
self.__items.append(item)
def peek(self):
if not self.is_empty():
return self.__items[-1]
else:
return None
def pop(self):
if not self.is_empty():
return self.__items.pop()
else:
return None
def size(self):
return len(self.__items)
栈的实际应用
给定一个列表，对这个列表进行反转
思路： 把要反转的列表中的元素一个个压入到栈中，然后再将栈中的数据一个个推出到一个新列表中，就得到了一个反转后的列表了
from stack import Stack
def reverse_list(l1):
s = Stack()
l2 = []
for i in l1:
s.push(i)
while not s.is_empty():
l2.append(s.pop())
return l2
数字的进制转换
思路：对要转换的数字进行相应进制的整除取余，将得到的余数压入栈中，不停的进行整除取余压入栈中，最后从栈中把元素一个个推出就得到了相应进制的数了
from stack import Stack
def base_conversion(num, base):
digits = "0123456789ABCDEF"
rem_stack = Stack()
while num > 0:
rem = num % base
rem_stack.push(rem)
num = num // base
rem_str = ""
while not rem_stack.is_empty():
rem_str = rem_str + digits[rem_stack.pop()]
return rem_str
检查括号的匹配
思路：
1、顺序扫描被检查字符串中的字符
2、跳过无关的字符
3、遇到开括号压入栈
4、遇到闭括号时与弹栈元素匹配，检查是否匹配
5、匹配成功继续，否则匹配失败
def check_bracket(symbol_str):
bracket_stack = Stack()
balance = True
index = 0
while index < len(symbol_str) and balance:
symbol = symbol_str[index]
if symbol in "([{<":
bracket_stack.push(symbol)
elif symbol in ")]}>":
if bracket_stack.is_empty():
balance = False
else:
top = bracket_stack.pop()
if not matches(top, symbol):
balance = False
index = index + 1
return balance and bracket_stack.is_empty()
def matches(open, close):
opens = "([{<"
closes = ")]}>"
return opens.index(open) == closes.index(close)
表达式转换
计算一个表达式时，编译器通常使用后缀表达式，这种表达式不需要括号。比如，中缀表达式 2 + 5 * 6 转换成后缀表达式后应该为：2 5 6 * +
思路：
1、建立一个栈来存储待计算的操作数；
2、遍历字符串，遇到操作数则压入栈中，遇到操作符号则出栈操作数(n次)，进行相应的计算，计算结果是新的操作数压回栈中，等待计算
3、按上述过程，遍历完整个表达式，栈中只剩下最终结果；
def infix_to_postfix(infix_expression):
prec = {
"*": 3,
"/": 3,
"+": 2,
"-": 2,
"(": 1
}
op_stack = Stack()
postfix_list = []
infix_list = infix_expression.split()
for token in infix_list:
if token in '0123456789' or token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ': # 如果是操作数
postfix_list.append(token)
elif token == "(": # 如果是左开括号
op_stack.push(token)
elif token == ")": # 如果是右闭括号
top_token = op_stack.pop()
while top_token != "(":
postfix_list.append(top_token)
top_token = op_stack.pop()
else: # 如果是操作符
while (not op_stack.is_empty()) and (prec[op_stack.peek()] >= prec[token]): # 判断当前操作符和栈顶操作符的优先级哪个高
postfix_list.append(op_stack.pop())
op_stack.push(token)
while not op_stack.is_empty():
postfix_list.append(op_stack.pop())
return "".join(postfix_list)
if __name__ == '__main__':
print(infix_to_postfix("12 + 5 * 6 - 8"))
执行代码输出结果如下：
>>> 1256*+8-
计算后缀表达式的值
思路：将表达式拆分成一个列表，然后从左到右扫描，发现是数字，就压入表达式栈中，遇到操作符，就从表达式栈中弹出两个操作数，进行运算操作。
def calc_postfix_expression(postfix_expression):
op_stack = Stack()
expression_list = postfix_expression.split()
for token in expression_list:
if token in "0123456789":
op_stack.push(int(token))
else:
op = token
op2 = op_stack.pop()
op1 = op_stack.pop()
result = do_math(op, op1, op2)
op_stack.push(result)
return op_stack.pop()
def do_math(op, op1, op2):
if op == "+":
return op1 + op2
elif op == "-":
return op1 - op2
elif op == "*":
return op1 * op2
elif op == "/":
if op2 == 0:
return "error"
return op1 / op2
if __name__ == '__main__':
print(calc_postfix_expression("12 5 6 * + 8 -"))
执行代码输出结果如下：
>>> 34
