编程笔试题(四)栈

乙醇 创建于 7 个月 之前

最后更新时间 2019-02-22

栈是常用的数据结构。尽管一般的面试里不会让你直接写一个栈的实现,不过跟栈有关的编程题还是有的。

定义

首先看一下栈的定义。栈是一个集合,具有下面的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()方法内部逻辑有所修改,这些用例也是可以复用的。

思考

上面代码里我只实现了小括号的匹配判断,如果我们要实现小括号,中括号和大括号的匹配判断,应该如何修改代码呢?

我要留言

暂无评论