与队列一样，我们以列表为基础实现栈。
这里，我们将列表的最后一个元素作为栈顶。
栈的结构和功能都很简单，实现并不复杂，代码如下：
class Stack(object):
# Stack() 创建一个空的新栈。
def __init__(self):
self.items = []
# push(new_item)将一个新的元素添加到栈顶。
def push(self, new_item):
self.items.append(new_item)
# 返回栈顶元素，但不会弹出它。
def top(self)：
return self.items[-1]
# 弹出并返回栈顶元素
def pop(self):
return self.items.pop()
# 返回栈是否为空。栈空返回true，否则返回false。
def isEmpty(self):
return [] == self.items
# 返回栈的长度，即栈中元素的个数。
def size(self):
return len(self.items)
括号匹配问题
括号匹配问题是栈应用的入门级问题，虽然简单，但却很好的体现了栈在实际引用中的灵活性性和高效性。
以下是三个正确的括号匹配字符串：
(()()()())
(((())))
(()((())()))
以下是三个不正确的括号匹配字符串：
((((((())
()))
(()()(()
用栈解决这一问题的有效思路：
从空栈开始，从左到右遍历字符串。
如果一个符号是一个左括号，将其作为一个匹配需求入栈，其对应的右括号稍后应当会出现。
如果符号是右括号，弹出栈，只要弹出栈的左括号与该右括号相匹配。
最后，当所有符号都被处理后，栈应该是空的。
简单的实现代码如下：
class Stack(object):
# Stack() 创建一个空的新栈。
def __init__(self):
self.items = []
# push(new_item)将一个新的元素添加到栈顶。
def push(self, new_item):
self.items.append(new_item)
# 返回栈顶元素，但不会弹出它。
def top(self):
return self.items[-1]
# 弹出并返回栈顶元素
def pop(self):
return self.items.pop()
# 返回栈是否为空。栈空返回true，否则返回false。
def isEmpty(self):
return [] == self.items
# 返回栈的长度，即栈中元素的个数。
def size(self):
return len(self.items)
# 检查小括号的匹配是否正确。checking_string为传入的待检查的字符串。
def Parentheses_check(checking_string):
stack = Stack() #创建一个新的栈用于保存未被匹配的左括号
for checking_char in checking_string : #从左到右，逐个遍历字符串中的字符
if checking_char == '(': #当前符号为左括号
stack.push(checking_char) #将左括号这一匹配需求入栈
else : #当前符号为右括号
if stack.isEmpty(): #栈中的已没有匹配需求，返回匹配失败，字符串有误
return False
else: #栈中有匹配需求，弹出这个需求进行匹配
stack.pop()
if stack.isEmpty(): # 遍历过后所有匹配需求都被满足，则返回true
return True
else: #遍历后依然存在没被满足的匹配需求，则返回false
return False
def main():
string_list = ['(()()()())','(((())))','(()((())()))','((((((())','()))','(()()(()']
for checking_string in string_list:
print("%s ---- %s"%( Parentheses_check(checking_string), checking_string))
print("-----------------")
if __name__ == "__main__":
main()
运行结果如下：
True ---- (()()()())
-----------------
True ---- (((())))
-----------------
True ---- (()((())()))
-----------------
False ---- ((((((())
-----------------
False ---- ()))
-----------------
False ---- (()()(()
-----------------
结果是正确的。
多种括号的匹配问题
之前所做的任务仅包含小括号的匹配，但事实上，这种算法也可以很轻松的推广到多种符号的匹配上。例如，以下三个字符串可以正确的匹配：
{ { ( [ ] [ ] ) } ( ) }
[ [ { { ( ( ) ) } } ] ]
[ ] [ ] [ ] ( ) { }
以下三个字符串不能正确的匹配：
( [ ) ]
( ( ( ) ] ) )
[ { ( ) ]
基于同样的思路，只需要对“匹配”这一操作做下扩展，便可以解决多括号匹配的问题。
简单的代码实现如下：
class Stack(object):
# Stack() 创建一个空的新栈。
def __init__(self):
self.items = []
# push(new_item)将一个新的元素添加到栈顶。
def push(self, new_item):
self.items.append(new_item)
# 返回栈顶元素，但不会弹出它。
def top(self):
return self.items[-1]
# 弹出并返回栈顶元素
def pop(self):
return self.items.pop()
# 返回栈是否为空。栈空返回true，否则返回false。
def isEmpty(self):
return [] == self.items
# 返回栈的长度，即栈中元素的个数。
def size(self):
return len(self.items)
# 检查多种括号的匹配是否正确。
# checking_string为传入的待检查的字符串。
# left_list和right_list分别为左侧符号列表和右侧符号列表，两列表在索引上一一对应。
def Multi_parentheses_check(checking_string, left_list, right_list):
stack = Stack() #创建一个新的栈用于保存未被匹配的左括号
for checking_char in checking_string : #从左到右，逐个遍历字符串中的字符
if checking_char in left_list: #当前符号为左括号
stack.push(checking_char) #将左括号这一匹配需求入栈
else : #当前符号为右括号
if stack.isEmpty(): #栈中的已没有匹配需求，返回匹配失败，字符串有误
return False
else: #栈中有匹配需求，弹出这个需求进行匹配
need_match = stack.pop()
if left_list.index(need_match) != right_list.index(checking_char): #索引相同，意味着匹配通过,否则匹配失败
return False
if stack.isEmpty(): # 遍历过后所有匹配需求都被满足，则返回true
return True
else: #遍历后依然存在没被满足的匹配需求，则返回false
return False
def main():
left_list = ['(','[','{']
right_list = [')',']','}']
string_list = ['{{([][])}()}','[[{{(())}}]]','[][][](){}','([)]','((()]))','[{()]']
for checking_string in string_list:
print("%s ---- %s"%( Multi_parentheses_check(checking_string,left_list,right_list), checking_string))
print("-----------------")
if __name__ == "__main__":
main()
运行结果如下：
True ---- {{([][])}()}
-----------------
True ---- [[{{(())}}]]
-----------------
True ---- [][][](){}
-----------------
False ---- ([)]
-----------------
False ---- ((()]))
-----------------
False ---- [{()]
-----------------
结果也是正确的。
通过对匹配功能的修改，可以实现更复杂的一对一匹配。
网友评论