00:00
同学们,那现在呢,我们已经有这样一个站了,对吧,那这个站它有什么用处呢?刚才我们讲过站它可以去计算一个表达式的一个结果,也就是说现在呢,我们希望使用站来完成我们最先前提出的这个问题,是不是就说我们学这个数据结构?占这个数据结构,它的价值在什么地方,那现在呢,我们就来完成,当我们接收到一个字符串,接收到一个表达式的时候呢,我们可以把这个表达式的结果给它计算出来。就是这么一个题,好,那现在呢,同学们看到我这里有一个关于站实现综合计算器的这么一个要求。那现在还是老规矩,我们首先先来分析如何使用站来实现这个综合计算器。的一个功能,或者说如何使用站来计算一个表达式的这么一个结果。
01:03
OK,好,现在呢,我们打开这个,呃,Excel我们来分析一下。我们来分析一下,还是先说思路。使用站啊,完成完成计算,计算一个表达式的这个结果能理解我的意思吧,好,现在呢,我们这个思路大致是这样子的,同学们大致是这样子的,首先呢,我会有两个站,注意听,好注意听,这有第一个站一个站。这是第二一个站。这是第二个站,那么第一个站呢?我们假定它为竖站。速速战。所谓速债呢,就是专门存放数。专门存放这个数据的,比如说待会儿呢,我们这有个表达式,我这个表达式粘过来。好,假如这个表达式是这样一个表达式是七。
02:02
七乘以二再乘以二再减五加一减五再加二再减四,这么一个表达式能理解好,那么我第一个站呢,是专门存放这个数据的,就是数的。对存放数的,那我这儿还有一个站。我这儿还有一个站,比如说这个站呢,我们把它叫做符号站。能理解我的意思啊,符号转是用来存放符号的,就是运算符的,能理解。好,也就现在呢,我会在在我的程序中创建两个站,一个是数站,而一个是符号站,那假如说这个数站呢,我们叫做number啊,这个就名字后面再去定吧,啊比如说比如说这个叫做number stock。对吧,存放数据的,那么这个符号这呢,我们比如说op。Offer就是操作符的一个站,假定啊这样子命名的,那当我有这两个站了过后呢,我怎么来完成这个。
03:08
这个计算怎么去得到一个表达式的结果呢?好,我们来说一下这个思路,谈一下思路就是使用站,使用站完成表达式的计算任务,首先呢,我先谈谈自己的一个思路,追星先把思路搞清楚,第一步。呃,我会先创建一个index。我会有个index。这相当于是一个指针啊,我先创建一个什么呢?啊,通过或者要这样写啊,通过一个index。Index一个,呃,一个值,一个值,这个值呢,其实可以理解成是一个用来进行对字符串进行扫描的一个索引。啊,一个索引可以认为是个索引。
04:00
啊,可以认为是个索引。这个时候应该什么呢?来便利来便利啊,我们的这一个表达式。表达式,这个表达式呢,比如说就这个表达式哈,呃,那它第一步,第一步就是通过这个index来扫描,那么我们怎么扫描呢?看我的看我的这个思路,如果我们发现发现通发现index。呃,我们发现index扫描到或者得到了。这样写啊,我们发现这个发现是一个数字。数字,比如说我通过这这个索引,这个索引比如说是index,我通过这个index呢,发现第一个是七。七我们发现是个数字怎么办呢?好,就直接就直接入数站。速战。能理解我的意思吧,就是如果我发现通过这个index我去扫描,我发现这个表达式扫描到的是一个数字,那么我就把这个数字呢,直接加到我的数站里面去,比如说现在我扫描一个七,我就直接先把它放在这个数站里面去,当然它是在占底。
05:15
是不是也就是说,也就是说他刚刚进来的时候呢,其实它是在这个位置。是不是我们以前我们前面讲站的时候是这个逻辑吧。好,如果发现是数字,我们就直接入数站,那如果我们发现,如果发现扫描到。我们扫描,扫描到的是什么呢?扫描到的是一个符号。就是那个操作符运算符,那么这个时候呢,情况就有两种,情况就分就分如下情况来解决,情况来解决第一种,第一种如果我们发现当前操作符号站是空的,就直接入账,注意听啊,如果发现当前的符号站。
06:04
符号站为空,追星为空。那么就就直接直接入站,比如说现在我把七处理完了过后,我这个index往后面挪了一下,发现是一个运算符,运是一个乘号,那这个时候我发现我的。符号站是空的,那怎么办呢?我就直接把这个星号入站了。也就把我的这个乘乘号入站,那入站以后,我这边这个站呢,也会有一个站点。是不是啊,同学们前面是不是这样讲的呀。那现在有一个问题,就是说如果我们发现这个符号站不为空。那怎么办呢?好,如果注意听啊,如果符号站,符号站有什么呢?有操作符。有操作符,那这个时候我们就要进行比较了,就进行比较。
07:04
就进行最近啊进行比较,比较什么呢?如果发现啊,如果什么呢,如果当前的。啊,操作操作服的优先级,优先级它不是运算符不是有个优先级吗?就是谁的运算优先级高,就说如果当前的操作符的优先级小于,注意听啊,小于或者等于或者等于伏等于这个占中的占中的。占中的这个操作符。就说我我目前我这个准备入站的这一个操作符,它小于或等于站中的这个操作符,就是我我的优先级是等于你或者是小于零,这个时候大家知道怎么办呢?好,这时就需要。
08:01
就需要从我把这个往这边挪一挪啊,往这边挪就往这边往下面压一下。就需要从从数站中,数站中泡出,泡出两个数。两个数。两个数对,然后再从什么呢?再注意听啊,再从。啊,再从这个符号站中,符号站中泡出,泡出一个什么呢?这个符号就是运算符啊,运算符将进行,然后进行运算,进行运算,进行运算将得到的啊,将得到的这个结果就是运算的结果。在干什么呢?将运算的结果再入。就是进行预算过后将得到的结果入数战。入这个数站,入完数站以后不要着急,还有一个动作,还要把当前的这个操作符,操作符入符号站啊,还需要然后啊。
09:09
因为你你现在得到的这个符号是不是还没有入账,你只是从这个符号站。弹出了一个符号,再从数字弹出来两个数字进行运算嘛,那你扫描的这个操作符是不是还没有,还没有处理啊,对不对,然后注意听啊,然后将。将呃。将现在扫描到的这个操作符,就是,然后将当前的这个操作符。当前的操作,操作符入什么站呢?入符号站,大家理解我在说什么事情吗?可能有点听着有点懵,是不是不着急啊,待会我们一步一步步的演示,那么当我这个做完了以后呢,好,第四一步,第四一步,第四一步呢。就是我这还有个逻辑就是。如果符号站为空,我们就入入站,如果符号有符号站有符号就应比较。
10:05
比较的话,如果是我当前这个符号小于零或者等于你,我就弹出两个数,然后进行算,再再入账,那如果说如果说我当前这个符号站的优先级大于你怎么办呢?我就直接入直接入这个符号站啊,注意听,还有刚才有个逻辑要再加上如果当前的啊,如果这样啊,如果在这个逻辑上啊,就是如果符号在里面有有符号的情况下,我们直接这样写。这样写。啊。你刚才这样比较的是不是是这个情况啊。是不是这个情况,同学们?是这个情况吧。那么如果说如果我把这个呢,粘下来啊。我把这个粘到这来,同学们看这个逻辑啊,如果当前的符号的优先级大于。
11:02
注意听这句话大于。就是大于。大于占中的这个操作服,就是就是我现在扫描的这个操作服务的优先级大于现在占中,占中当时占领的了,肯定是啊站中的那个操作符,那么就怎么呢?就直接入站,不计算就直接直接入什么站呢?符号站。能理解这意思啊,好,当我整个这个预算结束以后。第四一步我们应该怎么办呢?我把这个标成黑色的。因为我们前面都是黑色嘛,第四一步,呃,当扫描完毕过后,当这个表达式扫描扫描完毕,这是要干什么呢?就顺序的顺序的从什么呢,速战。数站和符号站。符号站中弹出啊呃,就是从数站和符号中,符号站中泡出,泡出相应的相应的这个数和符号符号并运算。
12:13
运算,那么运算完了过后呢,最后注意听啊,最后最后在符合在这个数战中,最后应该是什么情况啊,注意听最后速战。速战只会只只有一个数字,只有一个数字就是我们的结果。就是就是这个表达式的结果。表达式的结构。能理解吧,好所老师,你这个说的东西我都已经蒙圈了,不知道你在说什么,不着急,我们来看一个案例,就是用我这个思路,我们来走一个案例,大家理解一下,一下就明白了,这样子啊,因为这个表达式太长了,我我来验证我的这个思路呢,太慢,我把这个稍微的改一改好不好,我把它改成一个比较简单的。
13:02
呃,一个表达式,比如说就这个表达式吧。三。加二乘以六再减去啊,我我用这个表达式来进行一个验证。啊,来进行一个验证,大家看一下。好,我们用这个index进行扫描。Index进行扫描,我把这个呢,呃,稍微的放大一点,这样大家看起来清晰一点好吧。我们看的是下面这个,下面这个表达式啊,下面这个表达式,来跟着老师思路验证一下,我们验证一下,我把这个往下挪一挪,我们验证一个。好,验证什么呢?我们来验证这个,这个结果是怎样得到,得到最后结果的,好我们来看第一步。首先这个index它初始化肯定为零,开始扫描发现第一个是数,我们怎么办?直接用树站没有问题吧,那就说第一个三加进去了,当前这个地方应该是没有东西的啊,最先显这个是空的山进去了,三往下一挪是不是符号符号,现在如果发现是一个符号怎么办?发现当前符号上为空,是不是就直接入账,那也就说三下面这个加号直接入账。
14:20
是不是可以了,然后紧接着又发现是一个数数,怎么办,直接入账,是不是这边又入了一个二。上去一下,然后再发现有一个乘法。来,如果符,如果发现呃符号在有操作符,就进行比较当前。当前这个是扫描到一个乘法,乘法的优先级是比加法的优先级高还是低?是不是高啊,看这如果发现当前操作服的优先级大于站中的操作服的优先级,就直接入符号站,也就是说这个时候我们应该怎么办?是不是应该把这个。
15:01
乘法入战,当然一入战过后呢,这边移动一下。是这意思吧,紧接着我们再进行扫描,发现是个六六,是不是一个数字,数字没什么可说的,直接入账。能理解吧,那么占比倒出来了,发现是一个减法。好,同学们再往下面一扫描。注意听啊,发现是不是一个减号,我问大家减号是不是当前操作服的优先级小于或者等于占中的优先级,是不是它小于满足这个条件。是不满足这个条件,满足这个条件的话呢,这个减减法先不要马上入账。那该怎么办呢?从数站泡不出两个数,再从符号当中泡不出一个符号进行运算,那大家想你泡出两个数,一个是六,一个12这个,这个地方是不是泡泡出来是一个乘法,但它泡泡完了过后,是不是应该应该这样子的泡一个这个。这泡泡出来两个,两个,那占你在这两个一相加,是不是此时此刻这个六和二被泡泡出来,乘法被抛出来进运算,是不是等于12,等于12过后。
16:12
进行算将得到结果入数站,也就是说六六乘以二过后呢,这边入数站这个结果应该是12同时占顶往上移动。因为站着操作,它会自动往上移。而这个乘法运算完了过后是不是还有。把这个结果做完了以后,再将当前的符号站符号入符号站,就是你这个减法你还没有加进去是不是,所以说往上移动一下,移动一下,因为它把这个符号入符号站以后,是不是相当于把这个乘法的符号给重新覆盖成减减法了。能理解我的意思吧,紧接着它是不是又往下面扫描,发现又是一个二,怎么办,又入我们的。
17:01
这一个竖站往上移动。这时当扫描完毕,就顺序的从数站和符号中,符号当中抛出相应的数和符号并行运算。大家看,此时此刻。是不是从上面弹两个数,一个是二,一个是12,从这边弹一个减法,显然这个时候弹的时候呢,是用后面弹出来这个数据减掉前面这个数据,应该因为有一个顺序的问题。是不是?是吧,所以说这个地方要注意,你在弹的时候呢,一定是在做减法的时候,是后面弹出来这个数减去前面弹出来这个数。那整个弹完了过后是不是这样子,先弹两个,这边弹完,弹完以后12。12减去二这样子一一做运算,是不是变成十了,变成十以后这个移上去。这个没有动啊,指到这儿的,然后是不是,嗯,是不是现在符号站里面还有两个数啊,要是不是要继续弹,又弹出十和三,再弹出这个符号站站点的。
18:10
这个符号当前是不是加号,那加号它弹这个符号弹出两个数过后,其实已经到了。这个位置,然后13再把这个弹下来,弹下来过后是不是这边弹出一个加法加号十和13进行一个相加的处理,变成13。它一变成13以后,是不是这个就挪到上面去了。是不是这个道理?好,挪到上面去,虽然上面仍然有一个石,因为从站着来说呢,你并没有把它给给给给覆盖,所以它在这,但是我们的占顶,就说这个树的占顶,其实呢,只有一个13了。因为你你在访问的时候,你是不是以这个站点来访问的,虽然你这个死还在上面,但是你访问不到,而且他也告诉你,你的站点就在这个位置,因此当这样做完了之后,数字中数站中最后一个数字就是表达式的结果,即13。
19:06
各位,是不是我们就验证完毕了?大家看,嗯,这个思路能不能理解了,也就是说我们来实现用站来完成一个表达式计算的思路呢?就根据刚才的这套思路给同学们。讲解起来了,理解了吧,好,如果理解了,理解了过后呢,下面我们准备用代码将其实现,就说先说思路,再说代码,好,思路我们先分析到这里,大家先理解一下,下面呢,我们就准备用代码将这刚才老师分析的过程予以实现。好,实现的代码我们放在下一个视频。
我来说两句