学点算法之栈的学习与应用

在学习前,脑海中对这个词只有一个印象:客栈

栈是什么

栈(有时称为“后进先出栈”)是一个项的有序集合,其中添加移除新项总发生在同一端。

这段话初学者是懵逼的,别急,往下看。

对栈的一般操作:

  • Stack() 创建一个空的新栈。 它不需要参数,并返回一个空栈。
  • push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。
  • pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。
  • peek() 从栈返回顶部项,但不会删除它。不需要参数。 不修改栈。
  • isEmpty() 测试栈是否为空。不需要参数,并返回布尔值。
  • size() 返回栈中的 item 数量。不需要参数,并返回一个整数。

例如,s 是已经创建的空栈,下图展示了栈操作序列的结果。栈中,顶部项列在最右边。

自己在心里过一遍就很好理解了

Python实现栈

其实看到上面那张图,就想起了Python中 list 的一些用法,append、pop等,下面是使用 Python 来实现栈,也非常简单:

class Stack:
     def __init__(self):
         self.items = []

     def isEmpty(self):
         return 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)

pythonds/basic/stack.py

栈的应用:简单括号匹配(一)

有一些正确匹配的括号字符串:

(()()()())

(((())))

(()((())()))

对比那些不匹配的括号:

((((((())

()))

(()()(()

具有挑战的是如何编写一个算法,能够从左到右读取一串符号,并决定符号是否平衡。

为了解决这个问题,我们需要做一个重要的观察。从左到右处理符号时,最近开始符号必须与下一个关闭符号相匹配。此外,处理的第一个开始符号必须等待直到其匹配最后一个符号。结束符号以相反的顺序匹配开始符号。他们从内到外匹配。这是一个可以用栈解决问题的线索。

from pythonds.basic.stack import Stack

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol == "(":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()

        index = index + 1

    if balanced and s.isEmpty():
        return True
    else:
        return False

print(parChecker('((()))'))
print(parChecker('(()'))

output

True
False

一旦你认为栈是保存括号的恰当的数据结构,算法是很直接的。

从空栈开始,从左到右处理括号字符串。如果一个符号是一个开始符号,将其作为一个信号,对应的结束符号稍后会出现。另一方面,如果符号是结束符号,弹出栈,只要弹出栈的开始符号可以匹配每个结束符号,则括号保持匹配状态。如果任何时候栈上没有出现符合开始符号的结束符号,则字符串不匹配。最后,当所有符号都被处理后,栈应该是空的。

如果有和我一样不能很好理解的,使用pycharm的debug模式,可以一步步来,看看程序就近在做什么。

括号配对问题(二)

来看看第二种匹配问题。Python程序里存在很多括号:如圆括号、方括号和花括号,每种括号都有开括号和闭括号。

from pythonds.basic.stack import Stack

pares = "()[]{}"
def pare_theses(text):
        i, text_len = 0, len(text)
        while True:
            while i < text_len and text[i] not in pares:
                i += 1
            if i >= text_len:
                return
            yield text[i], i
            i += 1

def check_pares(text):
    open_pares = "([{"
    opposite = {')': '(', ']': '[', '}': '{'} # 表示配对关系的字典
    s = Stack()
    for pr, i in pare_theses(text):
        if pr in open_pares:  # 开括号,压进栈并继续
            s.push(pr)
        elif s.pop() != opposite[pr]:  # 不匹配就是失败,退出
            print('Unmatching is found at', i, 'for', pr)
            return False
        # else 是一次括号配对成功,什么也不做,继续
    print("All paretheses are correctly matched.")
    return True

check_pares('([]{}]')
check_pares('([]{})')

output

Unmatching is found at 5 for ]
All paretheses are correctly matched.

生成器(回忆一下):

  • 用 yield 语句产生结果
  • 可以用在需要迭代器的地方
  • 函数结束导致迭代结束

参考

http://interactivepython.org/runestone/static/pythonds/BasicDS/TheStackAbstractDataType.html http://www.math.pku.edu.cn/teachers/qiuzy/ds_python/courseware/index.htm

原文发布于微信公众号 - Python爬虫与算法进阶(zhangslob)

原文发表时间:2018-02-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小李刀刀的专栏

Unicode编解码函数

在用XMLHTTP进行远程数据传输的时候,如果涉及到不同编码,比如从oblog向我的博客发送一个trackback ping,数据中包含的中文字符就会出现乱码。...

36450
来自专栏ImportSource

Java8真不用再搞循环了?

Java8以后真的不用循环了?真的不用了? 好吧,本文分享的内容是java8之前和java8之后一些代码的不同写法,我们会先介绍java8之前和java8之后不...

2.8K110
来自专栏我是攻城师

Apache Pig学习笔记之内置函数(三)

47940
来自专栏绿巨人专栏

TypeScript中的怪语法

13430
来自专栏架构说

Leetcode 200 Number of Islands 岛的个数

1. 遍历每一个结点,如果某结点是陆地且未访问过,岛数目加1,修改未访问标志位,然后把该点放入队列中,以备扩展岛屿使用,进入2 2. 队列不为空时,取出点,然...

32430
来自专栏光变

3.1 ASM-方法-结构

ASM-方法-结构 本章将会介绍如果使用ASM core API生成或者转换Java编译后的method。 本将开始会展示编译后的method,然后使用很多说...

17620
来自专栏决胜机器学习

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(三)——运用栈实现括号匹配 (原创内容,转载请注明来源,谢谢) 栈在数据结构上是一种特殊的线性表,其限制是仅允许在表的一端进行插入和删除运算,...

45260
来自专栏Java技术分享圈

杨老师课堂之Excel VBA 程序开发第六讲根据部门列创建工作表

方式1:本节课件下载地址:链接: https://pan.baidu.com/s/1rf5pRmZ95fjVbz70KYi6Aw 密码: q9yk

10140
来自专栏GreenLeaves

C# Encoding

之前做公司项目的时候,对于C#编码这块总是一知半解,所以打算通过这篇笔记对C#编码(Encoding)进行彻底的扫盲,关于编码和字符集的基础知识,请参考字符集和...

29770
来自专栏听雨堂

获得定长字符串

        C#中的字符串是Unicode编码,length是Unicode的Char的个数。所以,假如一个字符串中中英文混杂,又想获得一个固定宽度的字符串...

26060

扫码关注云+社区

领取腾讯云代金券