python中stack在实际中的简单应用之平衡符号

　　很多书籍都在讲stack的概念和使用方法，等我们把概念熟悉后，发现不知道在什么场景下使用

该结构体，这里就列几个实用的例子，让大家了解一下stack在实际中的用处和厉害之处。

　　由于stack中的特点是可以成对的pop和push的，针对成对出现的东西，是有用武之地的，特别是

处理一些平衡符号方面，是有很大用处的。下面这个例子就是使用stack判断平衡符号是否成对出现的

　　

import timeit

from timeit import Timer

class Stack:

        def __init__(self):

                self.items = []

        def is_empty(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)

s = Stack()

def par_checker(symbol_string):

        s = Stack()

        balanced = True

        index = 0

        while index < len(symbol_string) and balanced:

                symbol = symbol_string[index]

                if symbol == "(":

                        s.push(symbol)

                else:

                        if s.is_empty():

                                balanced = False

                        else:

                                s.pop()

                index = index + 1

        if balanced and s.is_empty():

                return True

        else:

                return False

print "start sample checker:"

print(par_checker('((()))'))

print(par_checker('((())'))

def matches(open,close):

        opens = "([{"

        closes = ")]}"

        return opens.index(open) == closes.index(close)

def par_gen_checker(symbol_string):

        s = Stack()

        balanced = True

        index = 0

        while index < len(symbol_string) and balanced:

                symbol = symbol_string[index]

                if symbol in "([{":

                        s.push(symbol)

                else:

                        if s.is_empty():

                                balanced = False

                        else:

                                top = s.pop()

                                if not matches(top,symbol):

                                        balanced = False

                index = index + 1

        if balanced and s.is_empty():

                return True

        else:

                return False

print "start general checker:"

print(par_gen_checker('([{}])'))

print(par_gen_checker('({})'))

print(par_gen_checker('({))'))

　　测试结果：

start sample checker:

True

False

start general checker:

True

True

False