使用栈解决实际面试问题
数据结构这门学了很多遍，基本概念都知道，而且还很熟。可就是在实际工作中找不到应用的地方。这个问题，应该是大部分人都遇到的问题。今天我们使用栈来解决一个实际问题。
假设你在面试过程中，面试官为你出了一个这样的面试题：括号的匹配问题。大家都知道，括号都是成对出现的。如果给定一个括号字符串：’(()(())())’，让你编写一个程序，检查这个括号字符串是否完全匹配。
我们的挑战就是编写一个算法，它从左到右读取一个括号字符串，然后判断其中的括号是否匹配。为了解决这个问题，需要注意到一个重要现象。当从左到右处理括号时，最右边的无匹配左括号必须与接下来遇到的第一个右括号相匹配，并且，在第一个位置的左括号可能要等到处理至最后一个位置的右括号时才能完成匹配。相匹配的右括号与左括号出现的顺序相反。这一规律暗示着能够运用栈来解决括号匹配问题。
一旦认识到用栈来保存括号是合理的，算法编写起来就会十分容易。栈的特性是先进后出，操作包括入栈和出栈等操作。
实现算法思路分析：
由一个空栈开始，从左往右依次处理括号。如果遇到左括号，便将其加入栈中，以此表示稍后需要有一个与之匹配的右括号。反之，如果遇到右括号，就调用出栈操作。只要栈中的所有左括号都能遇到与之匹配的右括号，那么整个括号串就是匹配的；如果栈中有任何一个左括号找不到与之匹配的右括号，则括号串就是不匹配的。在处理完匹配的括号串之后，栈应该是空的。
下面我们来编写具体实现代码，程序分为两部分：一部分为栈的数据结构实现，另一部分为检查括号是否匹配。
# 栈的实现
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def clear_empty(self):
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 parse_checker(symbol_string):
s = Stack()
balanced = True
index = 0
while index < len(symbol_string) and balanced:
sybol = symbol_string[index]
if sybol in "([{":
s.push(sybol)
else:
if s.is_empty():
balanced = False
else:
top = s.pop()
if not matches(top, sybol):
balanced = False
index = index + 1
if balanced and s.is_empty():
return True
else:
return False
def matches(o, c):
opens = "([{"
closes = ")]}"
return opens.index(o) == closes.index(c)
# 调用检查函数
k = '(()(())())'
parse_checker(k) # 完成匹配返回True,否则返回False上面的实例就是对栈的简单应用，栈的应用特别广泛，这只是小试牛刀。把学会的知识，应用到实际生活和工作中解决问题。是最好学习方式，也是成长最好的方法。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-05-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录