讲解在线视频

现在，我们来看栈的第一个应用：进制转换

给出的问题是：将一个10进制数N，转换成r进制数

对于这样的问题

很容易求解

采用的思想就是：不断地去

整除r，记录下

每次的商和余数，不断地除下去

直到商为0时停止

我们将得到的若干个余数输出，就行了

这里需要注意的是

我们

第一次得到的余数4

实际上，是作为数的最低位的

而最后一次得到的余数2，是作为数的最高位的

也就是说

对于10进制数1348

最后输出的8进制数，是2504

我们会发现一个规律，就是：后得到的余数要先输出

这里，我们特意强调了后和先，大家马上想到栈的特性

后进先出

所以，这时候，我们自然而然地想到用栈，来求解这个问题

具体的算法是：每一次求出的余数

我们都把它入到栈里面

先不输出

先入到栈里

所有的余数入到栈里面之后

也就是整除的操作

执行完毕之后

我们再从栈当中，取出栈顶元素

然后输出，直到栈为空为止

现在，我们来看算法的实现，将参数N(注意它是10进制数)，转换成r进制数

首先

我们初始化一个栈

我们在这里，把栈画出来

注意，我们这里画的栈并不是内存

而是

栈的逻辑结构

当N不等于0的时候

我们重复地做以下事情：将N对r的余数

我们第一次得到的余数是4，入栈

然后，N自除r，得到了的

商168，不等于0

继续回去执行循环；168对8的余数0，入栈，再计算商21

21

再对8的余数，是5，入栈

再自除8，得到余数2，入栈

这时候，商是0，while循环结束，结束之后

我们只需要依次取得栈顶

注意，我们这里画的是栈的逻辑结构

开口向上的容器，栈顶是在上面的

这时候，只要栈不为空

我们就从栈当中，弹出栈顶到e当中

然后，把e输出，就可以

第一次弹出2，第二次弹出5，第三次弹出0，第四次弹出4，最后栈为空了

第二个while循环就结束了，所有的

余数，我们都正确地输出了

再来看栈的第二个应用：括号匹配

我们给出的问题是

给定一个数学式子

这个数学式子当中，包含了各种各样的括号

或者给定一个源程序

我们知道，源程序当中，也能出现各种各样的括号

我们把数学式子或者源程序当中，所有出现的括号合在一起

也就是忽略掉那些非括号的部分

我们如何判断这些括号是否是合法的

或者说，是否是匹配的呢

我们给出几个具体的例子

第一个例子，很明显

它是合法的

这是一对括号

这是一对括号。第二个例子

也是合法的

最内层的一对括号

紧接着，这两个红色的括号也是合法的，最外层的一对括号

它们也是匹配的

我们再来看，第三种情况

这是匹配的

这是匹配的

这也是匹配的

这也是匹配的

第四种，很明显是非法的

至少，只有一个右括号

而左边有两个左括号

从这点上

我们就能看出，它是非法的

但是不是左右括号数相等

一定是合法的呢

我们看最后一种

它有两个左括号，也有两个右括号

但它却是非法的

因为

在内层的、后遇到的这个左圆括号对应的右圆括号出现之前，却先出现了右中括号

而左中括号是先于这个左圆括号出现的

所以，这种情况必然是非法的

从这个例子

我们可以看出，不能仅仅去统计左、右括号的个数是否相等

从而判断括号串是否合法

那我们怎么做呢

通过分析

我们会发现，那些后出现的左括号

后出现的左括号

期待与其匹配的右括号先出现，在这句话当中

又出现了后和先两个字眼

那我们马上就联想到栈

实际上，到现在，我们会发现

凡是问题当中，如果有后什么什么

先什么什么

或者，先什么什么、后什么什么

这样的描述

通常都是可以使用到栈的

因为，后进先出是栈的基本特性之一

为什么后出现的左括号，期待与其匹配的右括号先出现呢？我们来看第二个例子

第二个例子

你会发现，这个蓝色的左括号

它比前面两个左括号后出现

那么，它对应的右括号，一定是先于先出现的两个左括号对应的右括号先出现的

就是这句话描述的

后出现的、蓝色的左括号

它期待与其匹配的这个蓝色的右括号先出现

而最后一个非法的例子

后出现的、蓝色的左括号

它对应着的右括号，是比这个右中括号后出现的

违反了这一条

所以，它是非法的

下面，我们给出具体的算法步骤

如果我们依次读入括号串当中的每一个字符

遇到左括号

那么通通入栈，只要是左括号，通通入栈

因为，我们后面要遇到与之匹配的右括号

那么

如果读入的是右括号

这时侯，我们判断栈里面的栈顶

因为，栈当中存放的都是左括号

我们判断，读入的右括号和栈顶当中的左括号是否匹配

是否是相同类型的左右括号

如果是

那么，将栈当中的那个左括号出栈

现在，我们来看算法的具体实现

参数s代表括号串，它以结束标志结尾

将来，我们可以利用这个结束标志，作为判断循环是否应该结束的标记

首先，我们初始化了一个栈S

并且，计时器i的值是0

接着，进入循环

每次读入下标为i的

字符，注意，我们采用的是后置的自增

i的初值是0

我们应该先读入下标为0的那个字符

如果读进来的字符赋给c，这个c

它不等于结束标志

我们应该继续循环

如果读进来的c是左括号

这个伪码

很容易理解

当然

具体你得自己实现

如果c是左括号

我们直接将c入到S当中

如果c是右括号

我们假定，S当中只能出现左右括号

所以，这里else就表示c是右括号

如果是右括号

我们判断一下栈是否为空

如果栈已经是空了

这时候，我们直接返回0

我们用0来表示非法。这个算法

它的返回值是int型

如果是合法的

我们返回1；如果是非法的，返回0

那为什么这时候(栈是空的)就是非法的呢

因为，我们读进来的是一个右括号

右括号

应该有一个与之匹配的左括号出现

但这时候，栈已经空了

根本就没有左括号了

说明

肯定是非法的

如果栈非空

这时候，我们就要取出栈顶的左括号了

把它放到e里面

如果e和当前读进来的右括号是匹配的

它们是同一对左右括号

这时候，可以将栈里面的那个左括号弹出来

注意，栈里面放的都是左括号

将它弹出来

如果它们不匹配

读进来的右括号，和栈里面取出来的左括号不匹配

说明就是非法的

非法，实际上通过这两个return，就可以得到

也就是相应的条件

成立的时候，就可以得到非法的情况

那合法的情况呢

当这个循环结束的时候

如果栈是空的

也就是说，栈里面的所有的左括号都已经弹出来了

跟读进来的右括号相抵消掉了

这时候

括号串就是合法的

那么，最后循环结束的时候，栈是空的

那就是合法的

如果栈非空

那就是非法的

所以，我们直接return了isEmpty这个伪码

它的返回值

现在，我们来看具体的几个例子

我们在右边，画出一个栈它的运行情况

注意，我们这里画的不是内存

而是逻辑结构

栈顶元素往上放

对于第一个括号串

左括号直接入栈，左括号直接入栈，遇到了右括号

应该执行到这里

这时候，栈是非空的

再执行到这里，取得栈顶元素

栈顶元素

是左括号

注意，c是读进来的

第3个右括号

它们是匹配的

既然是匹配的

就将

栈顶弹出去

继续往下

我们再读入第4个字符

它是右括号

那么，跟刚才一样，取出

栈顶，它们也是匹配的

那么，弹出去，再读入

左花括号

入栈；再读入左圆括号，入栈

再读入右圆括号，取得栈顶

它们是匹配的，弹出去

然后，再读入最后一个右圆括号

取出栈顶，它们是匹配的，弹出去

所有的括号都读入完毕了

这时候，栈是空的

所以，它是合法的

现在，我们再来看第二个括号串

我们读入的第1个是左括号，入栈；第2个字符

也是左括号，入栈；第3个字符

是右括号

跟栈顶的左括号拿出来比较

它们是匹配的

出栈

这时候，循环结束了，栈是非空的

因为，有一个左括号

所以，直接可以说，是非法的

现在，我们来看最后一个括号串。读入

左中括号，入栈；第2个左括号，入栈

第3个是右括号，取出栈顶的左括号

栈顶是左圆括号

但读进来的c，是右中括号

它们是不匹配的

不匹配

执行到这里的else，直接返回非法

也就是说

读到第3个括号的时候

已经知道它是非法的了

无论后面是

什么括号，已经是非法的了

所以，没必要再往下循环了