#!/usr/bin/env python
# -*- coding: utf-8 -*-

# learn <<Problem Solving with Algorithms and Data Structures>>
# Release 3.0
# chengang882 @ 2016-12-20
# 它可以检查常用的语法里，({[]})这些符号是否是正常闭合的
# Completed implementation of a stack ADT

class Stack(object):
    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)


def par_checker(symbol_string):
    s = Stack()
    balanced = True
    index = 0
    pure_symbol = []
    for symbol in symbol_string:
        if symbol not in "(){}[]":
            continue
        else:
            pure_symbol.append(symbol)
    pure_symbol_string = ''.join(pure_symbol)
    print pure_symbol_string
    while index < len(pure_symbol_string) and balanced:
        symbol = pure_symbol_string[index]
        print index, symbol, balanced, "###"
        
        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 += 1
    if balanced and s.is_empty():
        return True
    else:
        return False

def matches(open, close):
    opens = "([{"
    closes = ")]}"
    return opens.index(open) == closes.index(close)
    
if __name__ == "__main__":
    text_sample ="""
    class Stack(object):
    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)
    """
    print(par_checker("()()[]()[]()()()()()[()]()()"))
    print(par_checker(text_sample))

>>> 
()()[]()[]()()()()()[()]()()
0 ( True ###
1 ) True ###
2 ( True ###
3 ) True ###
4 [ True ###
5 ] True ###
6 ( True ###
7 ) True ###
8 [ True ###
9 ] True ###
10 ( True ###
11 ) True ###
12 ( True ###
13 ) True ###
14 ( True ###
15 ) True ###
16 ( True ###
17 ) True ###
18 ( True ###
19 ) True ###
20 [ True ###
21 ( True ###
22 ) True ###
23 ] True ###
24 ( True ###
25 ) True ###
26 ( True ###
27 ) True ###
True
()()[]()[]()()()()()[()]()()
0 ( True ###
1 ) True ###
2 ( True ###
3 ) True ###
4 [ True ###
5 ] True ###
6 ( True ###
7 ) True ###
8 [ True ###
9 ] True ###
10 ( True ###
11 ) True ###
12 ( True ###
13 ) True ###
14 ( True ###
15 ) True ###
16 ( True ###
17 ) True ###
18 ( True ###
19 ) True ###
20 [ True ###
21 ( True ###
22 ) True ###
23 ] True ###
24 ( True ###
25 ) True ###
26 ( True ###
27 ) True ###
True