371_尚硅谷_Go核心编程_数据结构和算法-栈的计算表达式(1).avi原创

那现在呢，我们看一下这个就是我们讲的这个站。那么这个站讲完了过后呢，你得你得把它用一下，就是用到一个实际的一个场景里边去。那么用一个什么场景来说呢？我们来举这么一个例子啊，同学们看。用站实现一个综合的计算器。那么这个计算器我们也分阶段来走，就是分阶段来实现这个呢，首先第一个就是说大家一定要先把他的一个思想把它整出来，然后再来走代码。如果说没有这个思想的话，这个代码写出来过后，同学们也很难理解，那么我的思路是什么样子的呢？大家看啊，我们就针对一个比较简化的一个东西，就是三加二乘以六再减去二，我们怎么做？我先把我的思路分析一下。我先把我的一个思路分析一下，同学们看。

那么假设这个是啊，一个表达式啊，同学们，这是一个表达式。这是一个表达式，那么这个表达式我们人是怎么算的呢？你们先不用去想机器怎么算，你先来做，如果你是一个人，你是怎么算的？当你说的时候，我是一个人。我不是先加先乘除后加减吗？对的，你看你说的是先乘除后加减，你怎么知道先乘哪一个。后后加了一个呢，是因为你的眼睛很厉害，你一下就把它全部扫描了。张老师，我是假设我不给你看后面这一半。我就给你看一个三，你知道对三怎么处理吗？你不知道怎么处理？我就是给你一个加我，我就这么说吧，即使我给到你这样一个表达式，我就把这个前面这个三加二给你了，你敢肯定是先做三加二吗？你不敢肯定。

因为你不知道后面运算符的优先级到底高不高，比如说我只给这个表达式，我就给你看这一半，我请你计算，你能计算吗？你计算不了。因为你不知道三加二是先先计算呢，还是干别的活，因为你不知道二后面这个运算符的优先级是比这个三，比这个加高还是比这个加。D。甚至是相同的。你不知道。所以说对人来说呢，这个算式其实挺容易一眼就看出来应该怎么算。但是对计算机来说，其实它。他就像一个瞎子一样，他不知道你后面是什么东西，因此呢，这里面这个逻辑就要同学们去设计这个算法了，就说你的算法是什么样子的呢。来，我说一下我的算法。我说一下我的算法。

当然，我的算法并不代表所有人的算法啊，我先说一句话，因为每个人都有自己的算法，张三有张三的算法，李四有李四的算法，对吧，王五有王五算法，每个人的算法不一样。那么我就针对这个算式，我是这样来思考的，我怎么思考呢？我先做两个站。我先设计两个站。哎，我先设计两个站，这两个站呢，长这样一个德行啊，同学们看，这是一个站。OK，这是一个站。那么我再设计另外一个站。我再设计一个站，这也是个站，那么我们知道矩形运算的时候，最重要的就是两种，两种特性的符号，一种是数，一种是运算符。对吧，所以说呢，我把这个呢叫做速债。

对，我把这个叫做速战，听我说我先把这个东西描述清楚啊，不然的话，你你不知道这个他为什么是这样子就可以了。所以说，所以说这个地方呢，听课的难度就是在于怎么设计这个算法。哎，那么这个呢，我把它叫做符号站。符号站啊，当然可能有些地方它它的叫法可能有稍微的差异一点哈，那现在我开始来进行模拟，我是一个电脑哈，我认我认为我我现在已经变成一个电脑了，那我怎么做呢？我认为我有一个指针。我认为我有一个指针叫index。好，我我认为我一个只能开始扫描了。这个指针呢，就是第一步，第一步我们刚才已经说明了设计。或者要创建都可以啊，创建两个站。两个站一个呢，我们叫做数站，叫number。Number sta。

还有一个呢，叫操作服站，叫凹。Star。两个站。两个站，那么这个数站呢？显然大家很清楚的知道，数站就是存放数据，存放数的就number sta，这个存放的是什么呢？存放数。存放这个数，而我们的这个oper sta呢，是存放操作符的。操作符，OK，现在我思路开始走了，再设计第三个，设计一个index，这个就是我们的index，一个指一个变量，或者你把它理解成是一个指针都可以，说白了它就是个一个变量。那么我们在设计index这个呢？初始化给它一个零，它是干什么的呢？它是用来扫描我们这个表达式的，也就是说我把这个看成一个表达式。比如说我给他取个名字叫这个东西。它是一个表达式，那表达式呢，它其实说白了就是一个字符串，目前就是字符串，所以说我们这还有一个式express，这个是表达计算表达式吧，计算。

计算表。答，四。那么它是一个什么呢？是一个字符串。是一个字符串，好，我开始扫描啊，Index扫描了，先扫到，如果我发现它是一个数字。它是一个数，那么没有什么可说的，直接把它扔进树上，就说我的逻辑是这样子的啊，如果发现是一个数字。注意你看这个算法，如果扫描时。如果我们扫描发现是。发现是一个数字。数字则直接。入速战。直接入这个站，为什么呢？因为你一个数，你不知道后面它有什么运算符，你可先把它保存起来。

你保存到哪个地方，你就保存站里面去。所以说我先把它入占了，那就说相当于说这个三就被我干劲就放到这个站里面去了，相当于说我在这加了一个三。这张不好放啊，同学们现在呢，老师用这么一个。新的一个东西。把它放进去三。好，显然是在占地。那这个时候大家应该想象到，在我们站里面呢，有一个top指向了三，这个大家应该脑海里面有一个这样的，呃，有有这么一个印象啊，我我现在先说算法。加进去，也就是说如果发现一个数字直直接入这个数站，那么问题来了，如果你发现是一个运算符怎么办呢？好，这边都是相对复杂一点的啊，如果。如果发现是一个运算符，运算符注意听啊，我在单插一句话就说这个数字呢，我们这只考虑的是。

一个数，那将来你这个数是多位的，你还要重新再考虑，比如说399。那你还得还复杂一点，还得考虑拼接的问题，但是我们先简化，就是你一定记住一句话，就说你在做一个东西的时候，你先考虑一个简单的，不要先考虑复杂的，你考虑复杂的你你一时半会是不是就就就堵在这个地方动不了了。对就动不了了，好，那现在呢，我们就考虑这个具体的啊，三加二好，如果发现是运算符里面呢，逻辑又分这么几个。第一个逻辑。说老师你怎么知道呢？我肯定被扣了的啊，如果我临时让我想，我肯定想不出来。谁也上不了，谁上来临时写根本写不了，你你就是搞个搞开发，搞个两年，你让马上写一个，他写不出来啊，因为这个东西你不备课，你肯定是肯定是实际上我想了想了的，我测了很多遍，我才我才上来这样讲的嘛，对吧，所以说呢，我们这个思路肯定是老师事先想好的，不然的话，临时给你们分析，我也分析不出来。

好，那么我现在呢，如果发现是个运算符，我就要考虑你这个符号站当前是个什么情况，如果符号站是个空站，好，那那说明你现在扫到扫描到一个运算符，那后面这个数没进去，你你没法弄，所以说如果如果是运符号站是个空站，这个运算符就直接入站。注意听啊，如果运算如就说如果这个这个这个op。是个空战。是空战啊，它是空的。是一个是一个空战。空空站诶别写错了啊，是个空战，它如果是一个空战啊，同学们，那这个没有什么可说的，你这个符号呢，就直接扔进去。因为他只有一个数，你现在没法干什么事儿说直接助战。

好，第二个问题来了。那如果说你这个oper它不是一个空战。那你这个符号就是这个加号，现在假设扫描到加号了啊，这样讲起来比较容易，那如果说呃，那现在这个情况已经满足了，我们现在先把家放进去啊，同学们先把家放进去，那也就是说此时此刻你应该响应到这个三已经满足我这个条件，就把它放进去了，这样我讲课比较容易讲。因为如果我我在讲课的时候，我没有一个具体的场景。那我这个课没法讲，你们也听不懂，好现在您可以想到，因为我说oper sta是个空站，就直接入战，相当于一放到这个符号站里面去了啊，注意这个呢，也是我们编译器在底层，它在做运算的时候，它也是这种原理啊，所以大家听完了过后呢，对大家理解这个，理解这个东西还是非常有帮助的，好紧接着他又扫描这个二。扫描二呢，刚才也讲了，如果发现是数字直接入树上，所以说这个地方又进去了一个数二。

啊，这个大家大家可以看到这个结果后面是正确的啊好二也入账了。诶。二入账了啊同学们二入账，那么二一旦入战了，大家可以想象到我们这个站站呢就指向了二。好，紧接着它扫描到一个星号了。那么这个星号实际上就是乘号，那乘号现在呢，发现是一个运算符了，但是呢，这个oper sta它不是一个空站。这个时候你要考虑问题了，你得考虑你这个扫描到的这个预算符的优先级，跟这个站顶，就是现在这个站里面这个运算符的优先级哪个高哪个低。对，那么这个逻辑就应该是这样子的啊，如果。注意听这句话。如果发现。发现当前就是这个符号站的offer。Oper大赞。

占顶的，占顶的运算符的优先级，优先级大于等于如果，如果它的优先级是大于等于当前。当前我准备入站的这个运算符的优先级，大家看能不能听懂啊，就是大于等于当前准备。准备入站的这个运算符。运算。服的优先级，优先级。这。如果我发现就符号站的那个那个那个运算符的优先级大于等于当前准备入账的，那说明你要你要赶紧计算。你要赶紧，你不计算的话，后面就完蛋了，但这个逻辑到时候还要优化啊，就说我们现在考虑一个这个情况，因为它里面情况还有很多，比如说你加小括号，大括号，中括号，那还是比较麻烦的，好待会我们说好，如果是这像头就干什么呢，如果是就就从注意听，就从这个符号，就从这个，就把这个符号站里面这个数取出来。

就从符号站。符号站。符号站A，符号站取出就泡泡出，泡泡出来，泡泡出并从。并从速战。必从这个数战。也弹出两个数也。也泡泡出两个数，泡泡啊，它也泡泡数，但要泡两个数啊，两个数，两个数。数进行预算，进行预算。运算运算的结果，再重新把它压入到速站啊，运算后的结果，运算后的结果结果干什么呢？再重新。

再重新压入。压入到啊，再重新入站，入站到速站。那么也就是说目前这个情况应该怎么做呢？就要从这个二把它弹出来，把三弹出来，注意你弹了两个数出来过后，这个占。已经空了，那也就是说你现在应该是弹了一个二，弹了一个三，注意弹的时候是二先弹出来，三后弹出来，这个很重要，因为待会儿如果它是减法的话，你要注意是谁减谁的问题。啊，那么弹出来过后呢，这两个数相当于说弹出来我的指针到这来了，这两个数还在不在站在里面了，还在，只是你认为它已经没有了。再说一遍啊，这两个二和三并没有删除它，只是占呢已经到这来了，只是说没有了啊数你肯定没有把它清空啊，这个时候把这个加号也弹出来了，加号一弹出来过后呢，二加三这个得到结果再重新入账等于几啊，我现在没有弹啊，对不起啊，我这说错了。

我我现在这个情况还不是一样的啊，说错了啊，因为我这个这个加号星号的运算符呢，它是高于现在还不能谈啊，现在不能还还不还跟我说的情况还不一样，因为目前我这个当前占的优先级是低于这个这个乘法的，所以说我这个逻辑还还不适用于现在这个逻辑，还不适用逻辑，那就是下面这个逻辑了。下面这个逻辑是什么呢？就说如果发现。如果发现op sta占领的运算部的优先级小于你，就是否则啊，就直接写个否则。否则就是反过来逻辑嘛，否则否则的话呢，就是这个运算符就直接入账。注意听啊，否则这个运算符就直接入账，否则运算符，运算符就直接直接入账。因为现在我的情况是这样子的啊，就是呃，因为你这个星这个星号的这个乘法的优先级是高于家的嘛。

肯定是高于他的，所以说这个时候呢，没有没有什么犹豫的机会了啊，那就直接把这个乘号给我入账进去啊，因因为他满足的是这个条件，跟我上面那个还还不一样哈，还不一样，所以说我现在呢，应该把这个乘乘号入战。入站的话呢，应该是这样入账。注意听啊，这个逻辑还是有点，呃，不是不是困难，他是有点绕好入账了。入战这个地方就指向他了。好，紧接着呢，他继续扫描。扫描到六，注意扫描到六的时候呢，他又满足这个条件了，如果发现这个数字，这个没什么可说的，直接入账六入账。六入战了。好，我再分析这个东西啊，同学们，六六因为是个数字，没有什么可商量的，直接把这个六入占。

那你这个地方呢，就指向了他。指向了它。紧接着同学们可以看到，现在扫描到。减好了，哎，同学们现在这个情况呢，就满足刚才我们说的这个情况了。因为目前呢，我们发现这个占顶的这个运算符的优先级是大于减法的。大于减法的，OK，好，根据刚才说的这个逻辑，因为你是大于等于当前准备入账的，现在呢，把这个六和二弹出来。把这个六和二弹出来，就是弹出来谈一个，再谈一个，好，我知道这了，那谈了一个六和二啊，大家想象高时间肯定用个变量来接收，也就是现在我们谈到了一个六和二。现在我们已经弹出来一个六和二，注意听六和二被你弹出来了啊，六二弹出来了，六二弹出来过后呢，紧接着这个地方弹就就说从符号位把它弹出来。

并从数站弹两个，那么这个星号也弹出来了，他们弹出来进行一个加进进行运算，运算过后等于12。等于12过后，同学们注意听啊，等于12，把这个12重新入到数站里面去看，运算后把结果入占到这个数站，那也就是说这个这个是十几呢？这个变成12了。12，你这个站点再往上面走一下。那么暂停走一下，过后你当前这个符号，这个符号还是要继续入战的，我这还少了一句话。就说你预算完了过后，你当前这个符号你还没做处理呢，你还没做处理呢，所以说这个时候呢，符号位。符号。符号仍然入账，再入再入哪里呢？再入这个符号位站。符号位、符号站。好，这两个逻辑是反过来的啊，就是呃，如果是个空站就直接入站，如果发现这个情况，相当于说这这两个是一组情况，它是一副else的关系。

我这个地方应该这样写就好了。这就是相当于这是一种逻辑啊，这是一种逻辑啊，是空战的逻辑，这是第二种逻辑，是站里面有东西的情况，站里面有东西孔里面呢，分成第一种和第二种。好这样子大家看起来就轻松了一点了啊，2.2.2，好这样子的，就说就这样的一个情况，就说不符号符号位不是空战的时候，有这两个逻辑啊，有这两个逻辑，好大家看一下，如果operating不是空战里面的两个逻辑。啊，不是空战。好，那么现在呢，同学们看啊，你运输网络把12运入占了，信号也弹出来了，现在呢，把符号再入符号符号站，那现在你符号是什么呢？是减法。是减法，所以说这个减法呢，就入到这个位置，入到这个位置的话呢，因为你现在占点是在这儿，所以相当于把它给覆盖了。紧接着你往这边上面走拢一下。

好，走完了以后。哎，走完了以后又继续扫描，扫描的一个二，扫描到二的话呢，这个时候它满足扫描式数字直接入账，那就是这个地方呢，六直接被覆盖掉了。因为你是占领嘛。好，进入到这里面去了，好这个时候他再扫描。没了。也就是说，他在扫描之后，他发现他已经什么都没有了。他一什么都没有的话呢，这个逻辑应该怎么走了呢？各位同学看下一个逻辑。就是说如果扫描到这最后一个逻辑啊，第七个逻辑就说如果扫描全部完毕，那么下面的逻辑应该这么走了。如果扫描。扫描全部就是扫描表达式。表达式完毕，完毕则应该依次从这个站数站里面弹出两个数，再从数符号站弹出一个数，进行这个运算，就运算一次，入站，入数站，这个弹一个就是弹一个符号位，弹两个数，结果再入站，再弹一个符号位。

再再谈两个数，再运算，再入算，最后留在这个数站的就是。最终的结果。啊，那么说如果扫描完毕，那么依次就这样子说啊，就依次。从符号位符号站取出或者弹出啊，取出这个符号符号。然后，然后从。从速战速战。速战。取出两个两个数，两个数进行运算。进行运算。呃，运算后的结果。运运运算啊，运算后的结果进行运算。

运算后的结果的入数战。入入什么呢？入数战直到什么呢。入这个数站。直到我们这个符号占为空。直到。知道符号位。符号位占。符号符号站啊，符号站为空就结束了。那么我们看是不是这个道理啊，现在开始谈东西了，弹一个二，弹一个12，注意弹的时候是后面这个数减去前面这个数啊，那你这个时候怎么谈的呢？又弹了一个二出来。弹了一个二，再紧接着弹了一个12出来。好，谈了一个二和12啊，谈了一个22，但是呢，这个地方在运算的时候，咱们咱们一定要知道啊，一定是后面这个数对前面这个数操作啊，所以说你在谈的时候，你要在运算的时候，你要这么去12减去一个二。

那么这个时候这个减号也被弹出来了，好，这个时候这个结果是多少呢？等于十，等于十过后把这个十再入站，相当于把这个给覆盖掉了，站点又上去了。占点右上去过后再把这个，因为你这个符号位还有个加号嘛，紧接着再把十和13取出来。再把十和三取出来，那么再把这个符号取出来，符号取出来过后呢，就是加法。加法完了过后，好整个13 13做完了以后，因为你把这个十刚才弹出来啊，弹出来这个指针计算到这来了，那么一加啊啊，你你刚才把两个都弹出来了啊，它它当时这个十和13弹出来过后，这个速战的这个占点其实已经到负一了，然后呢，你把它加起来过后，这个是13再把入战。好，最后你入入站的时候，你这个自然就会上去，因为这个指针会往上走吗？好，这个时候只有一个数了，这个时候他再取取的时候已经没有了，因为符号站已经为空了，最后这个结果就是13算出来了，最后结果呢，的确按我们这个分析，它就是13。

好，这个是。整个。整个我们操作的一个就说计算机，包括我们人分析这个算式的一个流程。这是一个算法的流程，大家看能不能理解啊，好好的想一想，那下呃，这样子啊，那等一下等一下。好，思路的分析，同学们，关于整个这个算法，包括思路分析呢，我们就分析到这儿了，好，关于这个算法的分析，包括我的思路，我就分析到这儿了。