概念

教科书对stack / queue 一般都会同时进行介绍, 同时记忆比较好记.
stack 是后进先出. 后面进来的元素, 弹出的时候反而先走.
queue 是排队(所以中文翻译成队列) , 先进先出. 可以想象成排队买游戏机的人, 喊到他了就高高兴兴交钱去了.

图示

stack 可以用洗碗这个场景来记忆. 洗碗的时候, 我们都是一边洗一边把碗叠起来, 如下图:

图片来自于网络

碗全部洗完之后, 要把它们挪到柜子里. 之前越是靠后的碗, 越是先被挪走, 如下图:

图片来自于网络

很好记.

主要操作

增加元素, 弹出元素, 似乎没什么特别可说的? 如果用C/Java 实现会涉及到"幽灵内存"问题. 不过现在编程一般都是直接使用语言本身内建的数据结构, 所以作为一个不需要考试的中年人, 我就不用C/Java 来写了, 偷懒用Python.

代码

class MyStack:

    """
    用python实现stack 会少了个很重要的概念: capacity resize , 因为python本身的list 是动态数组, 不需要处理扩容.
    """

    def __init__(self):
        self.data_list = []

    def get_size(self):
        return len(self.data_list)

    def push(self, data):
        self.data_list.append(data)

    def pop(self):
        if self.get_size() < 1:
            return None

        return self.data_list.pop()

    # 查看当前对象(即最后一个), 但不删除
    def peek(self):
        if self.get_size() < 1:
            return None

        return self.data_list[-1]

    def is_empty(self):
        return self.get_size() < 1

    def __repr__(self):
        return self.data_list.__str__()

python的list 其实已经实现了stack的功能, 所以这个代码真是偷懒到极致啊.

回答年轻时候的疑惑

在学校学习数据结构的时候, 我一直不太明白既然很多现代编程语言已经有了这些数据结构, 为什么我们要重写一遍? 现在, 我穿越回去告诉自己:

从"以后项目是否会需要自己手写这些最基础的数据结构" 这个角度来看, 没有必要. 重写一遍的目的, 是让大脑记下动手的经验, 让自己对相关知识的记忆更牢靠. 很多概念如果只是死记硬背不动手, 很快就会忘记.

另一个原因是, 在java/python这类语言里都实现了动态列表, 内存的分配不用你管, 所以用来写数据结构比较方便, 但不利于了解指针和内存泄露这些概念. 如果想让基础更扎实,那么最好重写一遍.

<算法4> 这本书里有java实现的stack, 也提到了幽灵内存的概念, 所以java版本就不写了. 在最后写完python会再写个C版本练练手.

应用-计算表达式

在很多实际应用中, 用stack 处理会达到很巧妙的类似魔法的效果. 这里举3个应用的例子: 实现计算表达式, 迷宫闯关和遍历树. 遍历树会在后面再写, 这里就写计算表达式.

这个例子是从<算法4> 这本书看来的, 当时拍案叫絕啊. 结果自己用python默写出来又翻车了.

需求

写一个程序, 能够计算以下3个字符串表达式的结果:

1. 15 + 21
2. 8 * ( 11 - ( 7 + ( 3 + 5 ) ) )

有问题的代码

#! /usr/bin/python
# -*- coding: UTF-8 -*-

"""

    作者: 小肥巴巴
    简书: https://www.jianshu.com/u/db796a501972
    邮箱: imyunshi@163.com
    github: https://github.com/xiaofeipapa/algo_example

    您可以任意转载, 恳请保留我作为原作者, 谢谢.

"""
from stack_v_1 import MyStack


def cal_each(before, last, opt):
    before = float(before)
    last = float(last)

    if opt == '+':
        return before + last
    elif opt == '-':
        return before - last
    elif opt == '*':
        return before * last
    elif opt == '/':
        return before / last

    else:
        raise Exception('不支持的操作: ', opt)


def calculator(input_str):
    """
    计算 数值表达式
    :param input_str:
    :return:
    """

    opt_list = ['+', '-', '*', '/']

    opt_box = MyStack()  # 存放操作符
    val_box = MyStack()  # 存放值

    step = 0
    for i in range(0, len(input_str)):
        val = input_str[i].strip()
        if not val:
            continue

        """
            运算规则, 当val 是 ) 时, 舍弃进入下一个循环
            当val 是 ) 开始计算
            当val 是操作符或者值时, 进入各自的stack
            更详细见图形分析
        """

        if val == '(':
            pass

        elif val in opt_list:
            opt_box.push(val)
        elif val == ')':

            # 开始计算, 弹出最近的操作符, 最近的两个数
            opt = opt_box.pop()

            """
            1) 弹出的先后顺序很重要, 应该后入的在后(减法和除法都是从左到右)
            2) 不能用 python的eval, 否则就没达到锻炼目的
            """
            last = val_box.pop()
            before = val_box.pop()

            result = cal_each(before, last, opt)
            if val_box.is_empty():
                print('--- 计算结果: ', result)
                return result

            # 否则推到stack 里准备下一个运算
            val_box.push(result)

        else:
            # 正常的值, 推入
            val_box.push(val)

        step += 1
        print('--- 第 %d 步: ' % step)
        print('--- val_box: ', val_box)
        print('--- opt_box: ', opt_box)
        print('\n\n')

    # -------- end for
    raise Exception('不可能到这里, 程序设计有问题')


def test_it():

    str_1 = '8 * ( 11 - ( 7 + ( 3 + 5 ) ) )'
    calculator(str_1)

    # 意外"惊喜": 这个程序不识别11, 如何识别多位数?
    # 需要先对表达式进行一次扫描.


if __name__ == '__main__':
    test_it()

代码解说

在python里, 其实直接 eval 就可以计算, 不过既然是练习当然要自己动手. 而且练熟了这种思路会对以后工作很有帮助. 举个例子, 某个生产厂希望你能写一个简单的规则程序, 实现有限的操作指令的组合, 达到"智能"的效果. 这类规则程序的算法一般就是计算器的算法改动版.

在这个算法实现里, 原书作者巧妙地用两个stack 分别保存操作符和计算值. 我在代码里加了print, 可以一步步看到两个stack 是怎么一步步存储数据的:

# 待计算的表达式:  8 * ( 11 - ( 7 + ( 3 + 5 ) ) )

--- 第 1 步: 
--- val_box:  ['8']
--- opt_box:  []



--- 第 2 步: 
--- val_box:  ['8']
--- opt_box:  ['*']



--- 第 3 步: 
--- val_box:  ['8']
--- opt_box:  ['*']



--- 第 4 步: 
--- val_box:  ['8', '1']
--- opt_box:  ['*']

在值的检查判断里, 左括号"(" 是被省略的, 右括号才是真正计算的开始:

elif val == ')':

            # 开始计算, 弹出最近的操作符, 最近的两个数
            opt = opt_box.pop()

            """
            1) 弹出的先后顺序很重要, 应该后入的在后(减法和除法都是从左到右)
            2) 不能用 python的eval, 否则就没达到锻炼目的
            """
            last = val_box.pop()
            before = val_box.pop()

            result = cal_each(before, last, opt)
            if val_box.is_empty():
                print('--- 计算结果: ', result)
                return result

            # 否则推到stack 里准备下一个运算
            val_box.push(result)

当遇到右括号的时候, 从值stack 连续弹两个数出来进行, 操作符opt_stack里弹一个操作符, 三者进行操作. 由于stack 是后进先出的特性, 所以这个计算必然是最内层(靠右)的计算. 操作完之后, 压回到stack, 下次再弹出的必然也是它, 符合需求.

翻车在哪

思路没有问题, 那么这段程序翻车在哪? 主要在两个地方:

1. 原书里, 所有表达式的输入用命令行进行, 所以可以确保每一次输入都是完整的数字. 当我把输入放在字符串的时候, 数字 11 被循环拆分为两个1进行计算, 导致了bug.
2. 在弹出值进行操作的时候只考虑到二元操作符, 所以每次都弹两个值. 类似 sqrt 这种一元操作符, 其实只需要一个值.

解决办法: 第二个问题好解决, 麻烦的是第一个. 但是我想了想还是解决吧, 太多算法的示例像是玩具, 还不如在复习算法的时候就写点实用代码.

修改版

修改版如下:

#! /usr/bin/python
# -*- coding: UTF-8 -*-

"""

    作者: 小肥巴巴
    简书: https://www.jianshu.com/u/db796a501972
    邮箱: imyunshi@163.com
    github: https://github.com/xiaofeipapa/algo_example

    您可以任意转载, 恳请保留我作为原作者, 谢谢.

"""
from my_statck import MyStack
import math


def handle_temp_value(opt_box, temp_opt, val_box, temp_value):

    # 处理数值
    if len(temp_value) > 0:
        val_box.push(''.join(temp_value))
        temp_value.clear()

    # 处理操作符
    if len(temp_opt):
        opt_box.push(''.join(temp_opt))
        temp_opt.clear()


def cal_each(opt_box, val_box):

    """
    1) 弹出的先后顺序很重要, 应该后入的在后(减法和除法都是从左到右)
    2) 不能用 python的eval, 否则就没达到锻炼目的
    """

    opt = opt_box.pop()

    if opt not in ['+', '-', '*', '/', 'sqrt']:
        raise Exception('不支持的操作: ', opt)

    # 弹出最近的数
    last = float(val_box.pop())

    if opt == 'sqrt':
        result = math.sqrt(last)

    else:

        # 弹出前一个数
        before = float(val_box.pop())

        if opt == '+':
            result = before + last
        elif opt == '-':
            result = before - last
        elif opt == '*':
            result = before * last
        else:
            result = before / last

    val_box.push(result)
    return result


def calculator(input_str):
    """
    计算 数值表达式
    :param input_str:
    :return:
    """

    opt_list = ['+', '-', '*', '/']

    opt_box = MyStack()         # 存放操作符
    val_box = MyStack()         # 存放值

    # 增加两个容器来处理多位数和操作符
    temp_value = list()         # 临时容器, 保存多位数
    temp_opt = list()           # 临时容器, 保存字符串

    step = 0
    for i in range(0, len(input_str)):
        val = input_str[i].strip()
        if not val:
            continue

        """
            运算规则, 当val 是 ) 时, 舍弃进入下一个循环
            当val 是 ) 开始计算
            当val 是操作符或者值时, 进入各自的stack
            更详细见图形分析
        """

        # 先处理数值. 数值有可能是小数
        if val == '.' or val.isdigit():
            temp_value.append(val)

        elif val.isalpha():
            temp_opt.append(val)

        else:

            # 处理临时数据
            handle_temp_value(opt_box, temp_opt, val_box, temp_value)

            if val == '(':
                pass

            elif val in opt_list:
                opt_box.push(val)

            elif val == ')':

                result = cal_each(opt_box, val_box)

        step += 1
        # print('--- 第 %d 步: ' % step)
        # print('--- val_box: ', val_box)
        # print('--- opt_box: ', opt_box)
        # print('\n\n')

    # -------- end for
    # 处理临时数据
    handle_temp_value(opt_box, temp_opt, val_box, temp_value)

    if opt_box.is_empty():
        result = val_box.pop()
    else:

        while not opt_box.is_empty():
            result = cal_each(opt_box, val_box)

    print('==== 最终计算结果: %0.4f' % result)


def test_it():

    str_1 = '8 * ( 11 - ( 7 + ( 3 + 5 ) ) )'
    calculator(str_1)

    str_1 = ' 15 + sqrt(9) - (20 + 2 )'
    calculator(str_1)

    str_1 = ' 15 + 21'
    calculator(str_1)


if __name__ == '__main__':
    test_it()

修改版多考虑了两个场景:

1. 计算值可能是多位数据, 所以要加一个临时容器进行处理.
2. 操作符也有可能是单词而不是加减乘除单个字符, 所以也要加个容器处理.

这样设计的好处是一边扫描字符串一边进行计算, 效率高, 不好的地方是难以扩展: 如果用户的输入不规范怎么办? 怎么先进行处理? 是不是又要在主程序里加一堆变量?

所以更好的做法是将主程序拆分成两部分: 一部分进行数据清洗, 确认数据没有问题. 另一部分进行逻辑计算. 不过这已经涉及到具体业务, 而不是复习算法了, 就有待各位自己把玩了.

写首歪诗来记住

程序员的特点是一周之后会忘记自己的代码. 一大段程序就像一大段文章, 原封不动记下来是不可能的, 所以要提炼并记忆一些要点, 根据这些优点复写其他部分. (想想大厂面试要手写算法, 还是有点道理的)

于是乎, 献上歪诗一首:

清洗识别多位数,    # 清洗数据, 识别一元操作符和单词操作符
两个容器放在前.    # 用两个stack 分别记录操作符和值
右括号才是计算.    # 遇到)才开始计算
弹值顺序有先后.    # 某些操作符有顺序要求, 先谈哪个值很重要

搞定!