堆栈
概念
在生活中,我们可以用叠盘子这个经典的场面来理解堆栈,先洗好的盘子放在下面,后洗好的盘子放盘子堆的最上面,一个一个垒起来。用的时候,从上面一个一个取出来用。用一个歇后语说就是:砌墙的砖头--后来居上。
一句话总结就是:“先进后出,后进先出。”
实现
其实pyhton的list数据类型就带有堆栈属性,那么我们直接封装成类
class Stack(object):
__data = []
def __init__(self):
pass
def push(self, data):
self.__data.append(data)
def pop(self):
if self.__data:
return self.__data.pop()
>>> from data_structure import Stack
>>> a=Stack()
>>> a.push(1)
>>> a.push(2)
>>> a.push(3)
>>> a.pop()
3
>>> a.pop()
2
>>> a.pop()
1
>>> a.pop()
实战:
给定一个化学式(以字符串形式给出),返回每个原子的计数。原子元素始终以大写字母开头,然后是零个或多个小写字母,代表名称。如果计数大于1,则可以跟随1个或多个表示该元素计数的数字。如果计数为1,则不跟随数字。例如,H2O和H2O2是可能的,但H1O2是不可能的。连接在一起的两个公式将生成另一个化学式。例如,H2O2He3Mg4也是一个化学式。
放在括号中的公式以及一个计数(可选添加)也是一个公式。例如,(H2O2)和 (H2O2)3是化学式。
给定一个化学式,以以下形式将所有元素的计数输出为字符串:第一个名称(按排序顺序),然后是其计数(如果该计数大于1),然后是第二个名称(按排序顺序) ),然后是其计数(如果该计数大于1),依此类推。
分析:
这道题的核心就是要把括号拆分出来,把(H2O2)3
拆分成H2O2H2O2H2O2
在这样拆分完括号的基础上,就能方便的统计化学元素的个数了。拆分括号就能很好的用到堆栈。
这里我们还要考虑到括号套括号的情况,即((H2O)2)5
这种,但默认传入参数都是正确的化学式,即不考虑)H2O(
等之类的情况,换句话说,这里默认所有括号都是成对且正确的。
我们从左到右遍历化学式,遇到(
括号就开始把括号里的数据压入堆栈,遇到)
就将数据取出来,直到取到(
然后乘以)
后面的数字即可。
func为主函数,主要处理整个遍历化学表达式和压站出站过程
find_num函数寻找)后的数字 也就是找到例子中的
find_string函数把展开的无括号的表达式统计其中元素个数。
以K4(ON(SO3)2)2为例
主函数func从头遍历 压栈进result 直到遇到第一个)
然后出栈,直到第一个( 然后得到SO3 乘以)后面的数字2 得到SO3SO3 再压入栈
此时表达式就变成了K4(ONSO3SO32)2
然后跳过被乘了的数字2 (tail_num 变量存储的) 继续遍历之后的字符串
def find_num(string):
# 寻找“)”后面的数字
num = ""
for i in string:
if i.isdigit():
num += i
else:
break
if not num:
num = '1'
return num
def find_string(list_string):
# 把展开后的不带括号的分子式 处理为最后的结果
result = dict()
element = ""
num = ""
for i, key in enumerate(list_string):
if key.isupper():
if element:
if not num:
num = "1"
result[element] = result.get(element, 0) + int(num)
num = ""
element = key
elif key.islower():
element += key
elif key.isdigit():
num += key
if element:
if not num:
num = "1"
result[element] = result.get(element, 0) + int(num)
return result
def func(string):
print(string)
result = list()
result_dict = dict()
tail_num = []
for i, key in enumerate(string):
if key == ')':
string_son = ""
last_value = result.pop()
while last_value != "(":
string_son += last_value
try:
# 出栈
last_value = result.pop()
except:
print('出现意外,没有对应的括号匹配')
break
tail_string = string[i+1:]
num = find_num(tail_string)
# num 为)后面的数字,赋值给全局变量tail_num 以便在入栈的时候跳过
tail_num = list(num)
# 展开括号
result += list(string_son[::-1] * int(num))
else:
if key.isdigit():
if key in tail_num:
tail_num.remove(key)
# 跳过)后面的数字
continue
else:
tail_num = []
# 压栈
result.append(key)
print(result)
return find_string(result)
网友评论