美文网首页
数据结构与算法

数据结构与算法

作者: 王大吉 | 来源:发表于2020-04-17 23:22 被阅读0次

    堆栈

    概念

    在生活中,我们可以用叠盘子这个经典的场面来理解堆栈,先洗好的盘子放在下面,后洗好的盘子放盘子堆的最上面,一个一个垒起来。用的时候,从上面一个一个取出来用。用一个歇后语说就是:砌墙的砖头--后来居上。

    一句话总结就是:“先进后出,后进先出。”

    实现

    其实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)
    

    相关文章

      网友评论

          本文标题:数据结构与算法

          本文链接:https://www.haomeiwen.com/subject/ygxsuhtx.html