7

数据结构与算法的JavaScript实现及应用 – 栈 递归 汉诺塔

 3 years ago
source link: https://wuzhiwei.net/ds_app_stack/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

在这篇文章里，我将介绍栈的基本操作和它的一些应用。

我们将看到栈在括号匹配检测，表达式求值，函数调用上的应用。

递归是一种特殊的函数调用，由于递归在程序设计中十分重要且不容易理解，所以我将阐述我对递归的理解。

最后我们将看到利用栈和递归是怎么优雅的解决一个经典游戏：汉诺塔。

本文还将给出表达式求值和汉诺塔的HTML5演示。

关于本系列

开放源码Open-Source-Logo-35px.png

  • 本系列的所有代码均开源，托管在Github
  • 所有Demo均托管在JSFiddle，点击查看

栈即Stack，以下是维基百科的定义：

在计算机科学中，是一种特殊的串行形式的数据结构，它的特殊之处在于只能允许在链结串行或阵列的一端（称为堆栈顶端指标，英语：top）进行加入资料（英语：push）和输出资料（英语：pop）的运算。另外堆栈也可以用一维阵列或连结串行的形式来完成。

400px-Data_stack.svg

根据定义我们知道栈只有三种操作：入栈(push())，出栈(pop())，获取栈顶元素(top())。而且栈只能够操纵栈顶元素，即只能在一端进行操作。

由于栈具有后进入的元素率先弹出的性质，栈又被称为后进先出LIFO,LastInFirstOutLIFO,LastInFirstOut的结构。

栈的操作十分简单，我们可以用单链表LinkedListLinkedList和数组来实现栈。

然而在JavaScript中，Array自带pop(), push()的操作，而且我们可以利用Array[Array.length-1]来实现top()操作。所以没有必要去另外实现一个Stack类型，用Array表达即可。

栈的LIFO的特性使得其适于解决许多实际问题，以下我们选取它的三个应用来加以阐述。

括号匹配检测

我们平时在编辑器中写代码时，有些编辑器会自动检测括号是否前后匹配，不匹配的话则会报错提示。

利用栈的LIFO的特性，我们可以轻松实现这个功能。

算法的伪代码如下：

//新建一个栈 s
s = new stack()
//读取字符直至读完
while read to c != EOF:
    //如果字符是开放括号 如 '(' '[' '{'等， 入栈
    if c is opening:
        s.push( c )
    //如果字符是结束括号 如 ')' ']' '}'
    else if c is closing:
        //若栈为空或者栈顶元素与开放括号不匹配 则报错
        if s is empty or f s.pop() is not correspond to c:
            return error!  
//若最后栈不为空，报错
if s is not empty:
    return error!  
//如果没有返回报错，则返回正常
return ok

算法的原理为，遇到一个结束的括号时，我们总是要查找最后一个开放的括号是否与之匹配，若找不到开放的括号，或最后一个开放的括号不匹配，则报错。

由于总是而且仅需要寻找最后一个元素，所以我们将开放的括号入栈，匹配时则出栈。

由于栈的特性，这个算法简单明了，且消耗的时间复杂度为线性级Onn。

表达式求值

栈的强大特性，也使得其能够运用在表达式求值上。

设想一个表达式：2+4/(3-1)

这个表达式具备了三种类型的符号：

  1. 运算数：2 4 2 2
  2. 运算符：+ / –

计算它的算法如下：

//分配两个栈，ops为运算符栈，nums为数字栈
ops = new Stack, nums = new Stack
//从表达式中读取字符 直至结束
while read c in expression != EOF:
    //若为左括号，入运算符栈
    if c is '(':
        ops.push(c)
    //若为数字，入数字栈
    else if c is a number:
        nums.push(c)
    //若为操作符
    else if c is an operator:
        //若运算符栈的栈顶元素比c的优先级高或一样高，则进行单次运算
        while ops.top() is equal or precedence over c:
            op = ops.pop()
            opn2 = nums.pop()
            opn1 = nums.pop()
            //进行单次运算，并把运算数入数字栈
            nums.push( cal(op,opn1,opn2) )
    //若为右括号
    else if c is ')':
        //除非栈顶元素为左括号，否则运算符栈出栈并将计算结果入数字栈
        op = ops.pop()
        while op != '(':
            opn2 = nums.pop()
            opn1 = nums.pop()
            nums.push( cal(op,opn1,opn2) )
            op = ops.pop()
//返回数字栈的栈顶元素
return nums.top()

以下是表达式求值的DEMO：

我们在调试代码的时候，碰到函数报错时经常会发现如下类似的报错提示：

/Users/tim/Codes/JavaScript/dsaginjs/DSinJS/Stack/InfixExpression.js:59
    return prioty[a] ) prioty[b];
SyntaxError: Unexpected token )
    at Module._compile (module.js:439:25)
    at Object.Module._extensions..js (module.js:474:10)
    at Module.load (module.js:356:32)
    at Function.Module._load (module.js:312:12)
    at Function.Module.runMain (module.js:497:10)
    at startup (node.js:119:16)
    at node.js:902:3

其实我们只是在一处出错了，为什么会打印出这么多报错信息呢？

原因就在于解释器把报错的函数经过的所有调用函数的栈打印了出来。

在函数调用的时候，我们需要切换到被调用的函数上，但是一旦函数调用结束，我们还得回到原来的位置。

利用栈，我们可以有条不紊的实现这点，即在函数调用的时候，我们把当前函数的变量和上下文入栈，等函数调用结束，我们再出栈，获取之前的上下文和变量。

函数调用的一个特殊情况是自己调用自己，这种情况称之为递归。

最简单的示例，求解阶乘：

function factorial(n) {
    return n == 0 ? 1 : n * factorial(n-1);

递归是个很有用的利器，但是新手往往很难理解，以下来谈一谈我对递归的理解。

  1. 递归需要一个终止条件，否则会无限递归
  2. 每次递归需要将问题缩小，否则达不到终止条件，也会无限递归

很显然，递归是自己调用自己，这很像我们在理发店里面照镜子一样，如果没有终止条件，我们永远也不知道还有多少个自己。

盗梦空间-无限镜子反射

其实用递归来求解问题的本质是找到比原问题更小的问题，而且能用同样的方法来处理。另外我们需要确定递归在什么时候结束，也就是确定递归的终止条件。

比如求阶乘：

  • 我们怎么求3的阶乘? 3的阶乘等于3乘与2的阶乘
  • 我们怎么求2的阶乘? 2的阶乘等于2乘与1的阶乘
  • 我们怎么求1的阶乘? 1的阶乘等于1乘与0的阶乘
  • 我们怎么求0的阶乘? 我们不需要求0的阶乘，因为我们已知0的阶乘为1

通过这么分析问题，提出n的阶乘怎么求？

回答是：如果n为0，则返回1，否则返回n乘与n-1的阶乘。

于是我们便得到了阶乘的递归表达：

function factorial(n) {
    return n == 0 ? 1 : n * factorial(n-1);

阶乘的递归的终止条件是n == 0；缩小问题的方法则是发现了n-1的问题和n的问题是一致的。

显然，递归的基础是函数调用，而函数调用的基础是栈。所以每次递归的开销，则是需要不停的进行栈的push和pop操作，这样会耗费大量的空间，也可能会造成冗余运算。

解决的办法可能有：尾递归，动态规划。

汉诺塔是一个经典的游戏。

其维基百科的描述为：

有三根杆子A，B，C。A杆上有N个N>1N>1穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：

  1. 每次只能移动一个圆盘；
  2. 大盘不能叠在小盘上面。
汉诺塔

汉诺塔有很多解法，我认为最优雅的解法是递归法，如果你不了解汉诺塔的解法的话，在继续阅读前，请尝试用递归法来解决它。

好吧，我承认一开始我没想出来如何用递归法来解决它，但是看完了它的解法后，我觉得优雅而精妙。

汉诺塔的递归法伪代码如下：

//将n个盘子按规则从a柱子，移动到c柱子
hanoi( n, a, b, c )
    if( n > 0 )
        hanoi(n-1,a,c,b);
        //将a柱子的最上面的盘子移到c柱子
        c.push( a.pop() );
        hanoi(n-1,b,a,c);

整个算法的思路是：

  1. 将a柱子上的n-1个盘子暂时移到b柱子上
  2. a柱子只剩下最大的盘子，把它移到目标柱子c上
  3. 最后再将b柱子上的n-1个盘子移到目标柱子c上

问题的缩小策略是我们怎么把n个盘子从a移到c，同样适用于n-1个盘子从a移到c。

当n一直缩小到3时，我们先把最上面的两个盘子移动到b，然后把最大的盘子移动到c，然后再把b上的两个盘子移动到c。 当n一直缩小到2时，问题终于变得直观了，我们将最上面的盘子移到b，然后把最下面的盘子移到c，最后再把b的盘子移到c。 当n缩小到1时，我们直接将a最上面的盘子移到c就OK了。

这就是问题的终止条件。

该算法的时间复杂度为指数级O2n2n，推导详见Complexity for towers of Hanoi?。最少求解步骤为2^n-1。

汉诺塔的传说：

传说印度某间寺院有三根柱子，上串64个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题TowerofBrahmapuzzleTowerofBrahmapuzzle。

若传说属实，僧侣们需要2^64 − 1步才能完成这个任务；若他们每秒可完成一个盘子的移动，就需要5846亿年才能完成。整个宇宙现在也不过137亿年 -.-！

以下是汉诺塔的演示demo：


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK