# 编程笔试题(四)栈




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

### 定义

首先看一下栈的定义。栈是一个集合，具有下面的2种基本操作

* push: 把元素加入集合，这个过程我们叫做压入
* pop: 把最后加入集合的元素从集合中移除，这个过程我们叫做推出

所以栈在移除元素的时候是遵循LIFO(last in, first out)，也就是后进先出的原则的。

下图演示了依次将1, 2, 3, 4, 5, 6加入到栈中并推出的过程。

![](http://ww1.sinaimg.cn/large/726a2979gy1g0f6k5w3mxj20jg0dl763.jpg)

### 使用python list来实现栈

我们主要是实现pop和push操作，另外再实现is_empty()方法来判断栈是否为空。

栈为空的意思是栈内没有任何元素了。

我们使用python的list来实现栈，这样比较简单。

```python

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

完整代码实现如下

```python

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()方法内部逻辑有所修改，这些用例也是可以复用的。

### 思考

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




原始封面

![课程图片](https://images.unsplash.com/photo-1513569771920-c9e1d31714af?w=300)