编程笔试题(四)栈
乙醇 创建于 8 months 之前
最后更新: less than a minute 之前
阅读数: 552
栈是常用的数据结构。尽管一般的面试里不会让你直接写一个栈的实现,不过跟栈有关的编程题还是有的。
定义
首先看一下栈的定义。栈是一个集合,具有下面的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()方法内部逻辑有所修改,这些用例也是可以复用的。
思考
上面代码里我只实现了小括号的匹配判断,如果我们要实现小括号,中括号和大括号的匹配判断,应该如何修改代码呢?