栈是常用的数据结构。尽管一般的面试里不会让你直接写一个栈的实现，不过跟栈有关的编程题还是有的。
定义
首先看一下栈的定义。栈是一个集合，具有下面的2种基本操作
push: 把元素加入集合，这个过程我们叫做压入
pop: 把最后加入集合的元素从集合中移除，这个过程我们叫做推出
所以栈在移除元素的时候是遵循LIFO(last in, first out)，也就是后进先出的原则的。
下图演示了依次将1, 2, 3, 4, 5, 6加入到栈中并推出的过程。
使用python list来实现栈
我们主要是实现pop和push操作，另外再实现is_empty()方法来判断栈是否为空。
栈为空的意思是栈内没有任何元素了。
我们使用python的list来实现栈，这样比较简单。
class Stack:
def __init__(self):
self.data = []
def __len__(self):
return len(self.data)
def push(self, elm):
self.data.append(elm)
def pop(self):
return self.data.pop()
def is_empty(self):
return self.__len__() == 0
import unittest
class StackTestCase(unittest.TestCase):
def test_push_and_pop(self):
s = Stack()
s.push(1)
self.assertEqual(len(s), 1)
self.assertEqual(s.pop(), 1)
self.assertEqual(len(s), 0)
self.assertTrue(s.is_empty())
s.push(1)
s.push(2)
self.assertEqual(len(s), 2)
self.assertEqual(s.pop(), 2)
self.assertEqual(s.pop(), 1)
if __name__ == '__main__':
unittest.main()
可以看出,push()实际就是调用list.append()实现的，而pop()则是调用list.pop()来实现。
小贴士: 我们可以在命令行中使用pydoc list来查看list的文档
题目
看一下这道编程题。
请使用代码实现判断表达式中小括号是否匹配的功能。如果匹配返回True，否则返回False。比如(x * (y -z)) + 1中，小括号是匹配的。而(a + b) * c - d)中小括号是不匹配的。
这是经典的栈使用场景。
我们的思路是
遍历表达式中的每一个字符
如果是左括号，将左括号压入栈
如果是右括号，则判断栈是否为空，不为空则推出，为空就证明右括号没有匹配的项目，返回False
遍历结束之后判断栈是否为空，不为空则返回False，否则返回True
完整代码实现如下
class Stack:
def __init__(self):
self.data = []
def __len__(self):
return len(self.data)
def push(self, elm):
self.data.append(elm)
def pop(self):
return self.data.pop()
def is_empty(self):
return self.__len__() == 0
def parenthese_match(exp):
s = Stack()
for char in exp:
if char == '(':
s.push(char)
elif char == ')':
if s.is_empty():
return False
else:
s.pop()
else:
pass
if s.is_empty():
return True
else:
return False
import unittest
class StackTestCase(unittest.TestCase):
def test_push_and_pop(self):
s = Stack()
s.push(1)
self.assertEqual(len(s), 1)
self.assertEqual(s.pop(), 1)
self.assertEqual(len(s), 0)
self.assertTrue(s.is_empty())
s.push(1)
s.push(2)
self.assertEqual(len(s), 2)
self.assertEqual(s.pop(), 2)
self.assertEqual(s.pop(), 1)
def test_parenthese_match(self):
exp_match0 = '(x * (y -z)) + 1'
exp_match1 = '()()()'
exp_match2 = '(((())))'
exp_not_match0 = '(a + b) * c - d)'
exp_not_match1 = '('
exp_not_match2 = ')'
exp_not_match3 = '()(()'
exp_not_match4 = '(((((((())))))))('
self.assertTrue(parenthese_match(exp_match0))
self.assertTrue(parenthese_match(exp_match1))
self.assertTrue(parenthese_match(exp_match2))
self.assertFalse(parenthese_match(exp_not_match0))
self.assertFalse(parenthese_match(exp_not_match1))
self.assertFalse(parenthese_match(exp_not_match2))
self.assertFalse(parenthese_match(exp_not_match3))
self.assertFalse(parenthese_match(exp_not_match4))
if __name__ == '__main__':
unittest.main()
代码其实逻辑很简单，大家可以根据我的测试用例来还原一下代码的具体工作流程。只有知道代码是如何运行的才能完全理解代码的作用。
比如对于表达式'('，上述代码工作的过程就是
遍历表达式
将(压入栈
遍历结束
判断栈是否为空，不为空，返回False
另外我写了测试用例去测试parenthese_match()函数，这种测试方式叫做白盒测试，也叫单元测试。
可以看到我的测试用例覆盖了代码的所有分支，用例设计策略是分支覆盖。
单元测试是机器去运行的，是自动化的。如果将来我的parenthese_match()方法内部逻辑有所修改，这些用例也是可以复用的。
思考
上面代码里我只实现了小括号的匹配判断，如果我们要实现小括号，中括号和大括号的匹配判断，应该如何修改代码呢？
