00:00
同学们,那么我们趁热打铁,我们把刚才这个代码继续完成下一步工作哈,下一步工作,呃,就是我们的第三步了,第三步。第三步,我要做件事情是什么事情呢?将得到的得到的一个中缀表达式。呃,表达式对应的这个list转成一个后缀。后缀表表后缀表达式对应的这个意思的,那说的再直接一点就是这个意思啊,我把我把我的思路,就我要干什么事先跟同学们讲清楚啊,我们刚才是不是已经得到了这个东西。是,是不是得到这个东西,这是一个中缀表达式对应的list,是不是现在呢,我们要把它得到一个什么呢?我们就要得到这样一个东西了。各位同学。这个是不是就是我们的后缀表达式,也就是说逆波兰表达式对应的字串啊,那么到时候我要得到一个什么呢?也要得到一个r list里面放的呢?是这个内容吗?
01:09
也就是说现在要开始真正的进行一个转换,他在这里面得到东西,就这个小括号呢,就被我消除掉了。小括号就被我消除掉了。同样这个地方应该是信号,也就现在我要完成这个事情。先明白我要干什么事啊,那怎么完成它的具体的步骤是刚才老师分析的这八步。看起来简单,但是代码还是要动动脑筋才能写出来的。来,各位同学开始写代码。那同样我把为了好看的,待会我要把这个拿过来,我要我要用一用啊,待会我好讲课。好,下面呢,我们先来把这个事情说清楚。现在我们先写一个方法,方法干什么呢?就是刚才我说的这个步骤。好的,同学们。好的,嗯,就这样一个事情,那现在我们开始写代码了,Public。
02:01
Public static static,然后呢,我们返回的是不是仍然是一个list,这个大家能理解吗?名字我就叫pass转换。后缀,后缀是S的意思,后缀expressione expression,好,然后呢,呃,List,把这个list也加上,这样好理解,就说转换成后缀表达式对应的list能理解好,同样这个时候我们接收的呢,就是刚才得到的这个中罪表达式对应的list。OK,同样我们写个A。好,那现在呢,根据刚才的讲解,是不是我应该定义两个站,按理说我应该定义定义两个站,所以说我们先来初始化站。把定义定义两个站,哪两个站呢?同学们看啊,Stock。我就用系统提供的站结构是俊第一个站叫S1,我们六一个这样的站。
03:05
没问题吧,有这样一个站,这是第一个站,这个站就是我们前面讲的什么站啊,符号站。明白,那么按理说,我们应该再来一个赞。叫S2。然后呢,这边就是我们所说的哪一个站呢,就是存放这个中间结果的这个站。存放存储啊,叫存储中间结果的这个站S2,但是我要给大家讲第二个这个站呢,我们没有必要用它。说老师那刚才不是讲的用了S2这个站吗?同学们还记不记得我们在用这个S2这个站的时候,大家还还有没有印象,在整个这个分析的分析的过程中,在整个这个分析过程中,我把这个标成一个颜色啊,标成一个别的颜色,非常好看。在整个这个这个分析的过程中,大家有没有发现S2这个所谓的S2这个站,他从来没有谈战这个操作,还记得吗?是不是一直往里面在加加加加呀。
04:09
还记不记得是不是在整个这个过程中,SS2其实一直都没有出站的操作,它是不停在往里面加东西。而且你加完了过后,后面还要逆续再输出,太麻烦了,所以说S2这个站呢,其实完全可以用一个release来替代。能理解我的意思吧,好,所以说我把这个写清楚啊,那么我这说一下说明说明,因为S2。S2这个站呢,在整个在整个转换过程中,过程中没有pop的操作。没有泡泡的操作,而且后面后面我们还需要还需要逆序输出。逆序输出太麻烦了。啊,因此比较麻烦,因此呢,比比较麻烦,麻烦这里呢,我们就不不不用这个占了,不用这个站不用这个结构了。
05:07
不用这个结构了,我们直接使用什么呢?直接直接使用list哦,我们直接使用这个来替代这个S2,就这能理解吧。用用这个list史的来填,因为list史的往里面加满了过后,你在按照正常顺序输出,不就是我们的这个逆波兰表达式了吗?那有些同学说老师那你为什么在讲的时候,你说用两个站,为什么这不说用那个,呃呢,因为很多书上,很多书上他出于讲课的原因呢,他在转换这个算法的时候,就是中缀转后缀表达式算法时候,他都是以两个站来来讲的。明白吧,所以说我这也用了两个站,但是在实际的过程中呢,咱们可以灵活的处理一下,因为你这个站实际上在整个过程中没有入站没没有出站的操作吗?没有意义,那只用一个list就可以搞定了。
06:03
OK,那所以说我这个呢,就换了啊,我就直接换了,我就不用这个玩意儿了,我直接用什么来处理呢?各位同学看清楚了啊,我把原因说清楚了。我我把原因已经说清楚了啊。不就完了,用于存储中间结果的这个list。完事了,那么这边呢,显然在用的时候应该是A。能理解啊,所以说这个是S1,这个是22,好,现在呢,我们继续往下走走思路了,那显然现在我们开始便利谁。是不是我们现在开始处理便利我们的这个LS,那便利的时候呢,我们有个户型文章墙,每次取出来是个是个SS啊,假设这个SS啊,就假设个item吧,每取出来是一个是一项好不好LS。OK,那么现在呢,我们在便利的时候,是不是应该根据前面的这个24567来操作了。
07:03
是不是好,那现在我们开始写代码了啊,具体跟着老师思路好,我先说如果是一个数怎么样就入站,入哪个站呢?当然是入我们这个S2,这个站没有吧,入S2啊入。就就加入啊,这样写叫加入到加入到S2能理解吧,那首先你怎么知道它是一个数呢?我们就用item点匹配。这里我仍然使用正则表达式,没问题吧?斜杠,斜杠D加。这说明它是一个数,如果它是一个数,那么我们就不啰嗦了,直接S2。点I注意啊,嗯,List是I,不不是那个push。好,然后呢,我们把谁加进去呢?把这个梦加进去就可以了。能理解哈,那现在呢,我们判判断,如果他是什么呢?OK。如果我们发现它是一个左括号,是不是也直接入账啊l if。
08:04
走一个啊,Item item.equals什么呀,如果它是这个符号,还记得是一个左括号,我们怎么处理。如果,如果它是一个左左括号,是不是直接。入到我们这一个S1这个这个站,这这个是真正入符号站啊,同学们看清楚了,那就是S一点我们的push。Push谁呀,Push谁啊,显然是我们的这一个,呃,小括号,把这个小括号放进去就可以了,Push谁push我们这个item一样的。搞进去了。是不是如果是左括号,咱们就直接进去,那紧接着我们继续来处理,继续来处理l if,如果我们发现同学们注意听啊,这个稍微有点绕了一口,如果我们发现它是一个一个右括号。同学们还记不记得,如果是个右括号,我们是不是应该?
09:03
项目处理啊。是不是这样处理,如果是右括号的话呢,我们要这样去处理好,我把这句话拿过来,我们把代码写一写啊,这面稍微有点绕了。跟上我的思路啊,如果是右括号,我们就这样去做,那怎么来处理呢,Well。啊,就是一直一直弹,那这个时候呢,我们要正面去写,大家看能不能看懂S1S1.p。啊,Pick pick这个这个方法我们前面说过,它就是查看一下S1占顶的内容,但是占顶的东西不弹出来,pick.c equals,只要他还没有到,没有到这个对应的。还没有看到我们的,诶不是啊,应该是没看到这个。没有看到这个左括号,我就不停的往里面加,怎么加,弹出就是依次弹出S1加到S2,还理解吧,那这句话一一句话就可以搞定S2.i的。
10:04
一点泡泡多简洁,一句话搞定了。大家看这句话什么意思啊,这句话意思是不是把S1站的内容弹出来,加入到S2,直到什么时候结束呢?直到碰到了一个。向左的括号啊,这个地方还少了一个这个分号啊,小的括号,那么最后是不是当我这个地方做完了以后,是不是还要把把这个小括号,就是对应到的这个小这个左括号还要把它弹出去啊,是不是,所以说这边还有一句话啊,S1.pop。这个就消掉了一对括号,这句话不能丢啊,很重要,这句话很重要啊,这句话干什么呢?将。将这个小括号弹出。弹出哪个呢?弹出一这个站是不是我们原先在讲的时候也是这样讲的,讲到这我们发现,诶还有还碰到一个小向左的小括号,直接把它。
11:04
谈掉这个就是,其实这里就是在在什么呢,消除。消除什么呢?消除括号,小括号。小括号。明白这意思吧,好,这个咱们就处理完了,紧接着还有一个逻辑最复杂的在这里。最复杂的在这里就说下面就是要考虑优先级的问题,因为我们前面讲的是括号,现在是不是这个地方也处理了,那还有这个二和三的逻辑没有处理。是这意思吧,好,下面呢,我们把这个代码处理处理。处理处理啊,那么现在呢,我们要这样去处理,就是当。当什么呢?当S1占顶。一站顶的运算符,这个有点说啊,运算符的U。呃,就是。呃,应该怎么写啊?若优先级小于等于。
12:04
就是当艾特蒙。Item的优先优优先级小于。啊,或者是等于占顶。站顶。运算符运算符的优先级。就说当我这个item的优先级小于等于你暂停的优先级的时候,我应该怎么样呢?就应该做这个工作。就应该做这个工作。是不是要做这样一个工作啊。是不是?因为上面这个是优先级比这个占点的优先级高嘛,那反过来三这个逻辑是我的优先级小于等于占顶的符号,优先级是不是我要反复的做这个事情。就是当I优米优先级小于等于SN小于等于S,当是S1了,S1这个占的优先级,那么将S1占领的运算符弹出并压入,当然这个不是加入了,是加入。
13:07
加入到S2中,然后反复的做这个工作,是不是这应该有个Y循环了。是不是有点绕啊,认真听讲啊,那么我就用个Y循环,Y循环首先如果S1这个size。啊,就是S一个站呢,它的大小还没有等于空,就说明还可以一直做,并且还要满足一个条件。满足怎样一个条件呢?就是。我们这个操作服的这个优先级要进行比较。谁的优先级高,谁的优先级低的问题。好,现在呢,我们发现这里有个问题。问题就是我们缺一个方法,我们缺少缺少啊,注意听啊,缺少一个比较。优先级高低高低的方法。
14:01
那这个方法是不是我们刚才没有写这个东西啊,那现在呢,老师要把这个优先级的。高低的这个方法给他加进去,我们需要加一个这样的这样的方法,好,现在呢,我我补一个类,我补一个类啊专门来。来来返回优先级高低的一个一个类,好,现在呢,我增加一个类。啊编写啊叫编写,编写一个类。这个类呢,我们取个名字就叫oper。Operation operation operation这个干什么呢?可以可以返回,返回一个运算符对应的对应的这个优先级。它的优先级。优先级,那我现在开始写了啊class。Operation写进去,那么现在我们先定义几个运算符,我们现在运算符其实就是有加减乘除嘛,对吧,我就定义一个static。
15:07
In爱的,比如说加,我认为它对应的优先级是一。对,然后呢,下面还有一个减。我把这个直接改了啊。Subb减对应优先级呢,我们认为也是一个加,我们再来一个乘乘呢,我们我用mull。标,那么这地方乘法的优先级我们认为是二高一点,还有一个运算符的优先级是div。除法,我们认为除法的优先级是二,没问题吧,好,现在呢,我们写一个方法。啊,写一个方法返回对应的优先级数字。你明白我的意思吧,因为我如果不不写这一个方法,在这判断太麻烦了,所以我就写一个,那就写public static,用一个静态方法get什么呢?Value。
16:04
Get value,好,你给我传进来一个。就是所谓的运算符吧,那么我在这里呢,有一个结果,Result初始化为零,然后呢,我用Switch语句给同学们做一个判断来了,啊,注意听讲,也就是说我根据你传进来的operation呢,返回一个数字,表示这个运算符对应的优先级。优先级的那个数,好,那这个K呢,显然就应该是我们的这个operation开始写了,如果说它传进来是一个加。OK,那么如果是叫,那么result result呢,其实我们就认为是一个爱的,这样好看啊,它的结果就是爱的,那你只写个一也是一样的,如果是一个减法,我就复制了。比较简单,如果它是一个减法,那么我们给它附一个sub。
17:01
S如果它是一个对吧,诶这个地方再复制一份,如果它是一个乘法。是这样一个东西,那么我们就给它附一个谬对应的值,二如果它是一个除法。如果它是一个除法追听,那么它对应的什么呢?诶,咱们就对应div对应的这个词。好,当整个这个处理完了,完了过后,这里完了过,假如说它不是加减乘除,那么我们给它一个默认值就是零,这个零呢,咱们上面已经有了啊,也不去管它了,这最好提示一个信息,或者抛一个异常也可以。啊,抛出一个印上使用你有,反正干脆我们就是不去管它,打一句话就行了,啊打句话,因为你的你的这个表达事情不会有这种错误的信息,他就说不存在,不存在该运算符。因为我们现在只处理加减乘除。
18:00
好,整个结束结束完了过后还有一个动作要干什么事情啊,是不是要将这个result返回。能理解啊,也就是说现在我增加这个类的作用是能够根据你传进来的这一个运算符,返回它对应的优先级的一个数字,能理解我的意思吗?应该不是很难吧,大家应该还是比较好理解好了,那现在讲到这儿呢,我们下面这一步就可以来写这个优先级的问题了,来回到刚才的代码。回到刚才,那是不是在这儿,我们是不是。啊,应该是在。在哪啊?Pass,是在这儿吧。好,现在呢,我们开始来比较,当他满足这个条件的时候,我们就不停的做这个,呃,工作好,那就开始写这个东西了,我就写operation。刚刚写的这个类。Operation。点什么呢?Get一个value。
19:03
Get一个value,我先取到S1这个站顶的。这个值注意啊,Pick只是查看一下S1占比的这个,呃,这个符号,但是没有取出来,如果他的这个优先级。对,我们看看啊,这个地方应该是到这儿没问题吧,好,如果它怎么样,大于等于。大于什么呢?Operation还是operation这个点get value等于谁的等于谁的,这个优先级呢?好,等于现在我拿到这个item的优先级,说现在占顶的比你的高。如果比我这个高,我怎么做呢?我怎么做呢,我让这个S2.i的S一点泡泡。是不是这个道理?为什么要做这个事情,大家想一想,因为你是反复的做错啊。
20:03
反复的做吗?只要这个条件满足,不停的走走走走走走。对吧,当然前提是S1SIZE要不等于零,如果等于零的话,就已经空了,你就不能再压了,你空的东西你在在你如果S1没有东西,你再泡泡不就出大问题了吗?而这个条件不要不要错了啊好这个时候,呃,当这个做完以后,是不是最后还是要把你当前扫描的的这个预算符再压入到一这个这个站。是不是还最后啊,别忘了还需要还需要将这个item最后当这个Y循环做完了以后,还需要将这个item压入。压入战中,也就是大家还记不记得我们刚才做分析的时候,最后那个最后我们做分析扫描的这个,扫描的这个这个减法的时候,是不是这个减法还是最终入入了账了。是这意思吧,别忘了啊啊,那么这个动作呢,不要忘了,就是S1S1.push谁呀it。
21:05
没事。完事。好,到此为止,我们现在已经把第一部分工作做完了。第一部分工做完了,也就是说整个这个for循环做完了以后呢,相当于我们把哪部分工作做完了。是不是有些东西,你你这这个整个扫描完毕了吗?但是你扫描完毕过后,第七步是不是还没做啊,你现在是不是还要做这样一些事情把。把什么呢?将S1中剩余的运算符依次加入到我们的或者加入到我们的S2中。因为原先是压入,现在又是加入了,并加入。有人说啊,加入到S2中,那加入到S2中这个代码肯定用过Y循环就可以了,那什么呢?只要S1SIZE,它不等于零。
22:01
只要这个不等于零,是不是我就不停的做这个工作,就是S2艾,我们S一点泡泡。能理解这个意思吧,这句话就是在完成这个工作,最后当整个工作做完以后,S2。就是我们的结果,而且呢,这个时候不需要逆序输出了。因为你本身添加的时候,这个顺序就是正确的顺序,注意啊,注意因为因为是存放到。存放诶,因为是存放到一个历史的中的,历史的它本身是有序的嘛,啊,因此因此因此正常输出按顺序输出,按顺序输出就是对应的逆波兰或者叫后缀。后缀表达式对应的list,那么我们来玩一把。看看老师这段代码是否正确呢?来看一看啊。
23:00
首先呢,刚才我们这个PAR这个方法已经写完了,Pass把谁放进去,把中最表达式对应的历史放进去。然后它会返回一个后缀表达式,对应的历史的,没有没有毛病吧,现在呢,我们将这个输出来看一下。写到这里呢,那叫后缀表达式。就是呃,后缀表。表达是对应的list。这个是上面这个是中队表达式对应的list。我们做一个比较,你们一看就明白了。好,这个是中缀啊,中缀表达式对应的list的,然后呢,我这做一个等再加,同样这边呢,我们加上这个。呃,这个就不要再取这个名字了。叫啊,这样写就行了,好吧,这样简洁一点,好,同学们,我们看看整个这个结果是不是它。
24:01
啊,当然不是他啊,应该是。咔。如果是这个东西好,说明我们就OK了,如果不是,那说明我们这个代码是有问题的,还得调代码。好运行之。我们运行完了过后,我们发现诶这个结果还非常的OK啊,你看这这个就不存在表达式,存在运算符,因为他做了一个处理嘛,他在这匹匹配的时候做了一个处理啊,那就也没什么大的问题,好你看最后这个结果是一,我们看这个跟我们想的是不是一样的啊,拿过来看一看。哦,同学们看,现在我们这还存在一个问题。出现什么问题呢?小括号我们没有消掉。小括号没有消掉,那如果小括号没有消掉的话呢,那我们这个地方还是存在一个小问题的。我们需要把这个小括号消掉,才可以拿来去使用,对吧,少了点东西,那么我们来谈谈,看看哪个地方出了问题,我们看一下。
25:00
哪个地方出了问题?看一下问题的所在吧,我们再执行下,看看问题哪里有问题啊。哦,大家看。嗯,问题是在哪里呢?有同学能看出来吗?小括号,那是不是小括号没这个小括号没有消除掉是吧?没消除掉,我看看代码在哪里有问题,那如果说这样的话,我们可以确定刚好来带大家看一下这个错误的调试啊,我们回到这,肯定代码是在转换的过程中出了问题了,往下搂一搂。呃,如果是数,咱们这样处理,如果是小括号直接入账没问题,如果是。诶,这方怎么少写了一个东西啊。是吧,你看这个麻烦了,如果是右括号,咱们是不是要这样去,如果是碰到了一个右括号,应该这么去处理吧,右括号怎么处理就消这个是消除小括号嘛,好,这个写完了,这下子应该就没没没毛病了吧,来再来运行值。
26:01
运势OK,我们发现又出问题了,哪里出问题了呢?奥特说有一个NPT。空战的一场怎么可能呢?看一下70。这个没毛病的吧。呃,我们再来看看它的提示信息吧。没事啊,同学们遇到这个问题不要着急,看这个23行。23行也是转化出了问题。那诶,大家有没有发现我这出了一个大问题。我这个中缀表达式对应的怎么是变成了一个这样的符号呢?应该是星号啊。好,我这个地方应该给错了,你看这里面又犯了一个错误。因为我在进行这个符号判断的时候,我在进行符号判断的时候,我这给的是。这个不好是吧,所以说我们这个地方呢,老喜欢把这个PPT里面东西拿过来就出了问题了啊,这个改成它就可以了,预算式不要写错了啊,注意。
27:06
注意这个,呃,这个表达式,嗯,表达式的写法啊,就是这个星号和一个叉号不一样的啊,不一样的好,我们再来执行一下,应该就没没问题了,走一个啊,如果再出问题的话,今天就不吃中午饭了,对不对,执行直走。好,我们看到这次很顺利,没有任何问题,大家看这次呢,我们在处理过后,我们发现呢,123加四星加五,看看对应的跟我们是不是一样啊,来走一个。我们发现呢,这边得到的结果跟我们完全一样啊,跟我们完全一样,你看123加四星加五减,好,最后我们还要确认一下,这个结果跟我们一不一样,我们再把这个结果计算出来一下。因为现在呢,我已经拿到一个后缀表达式的list,而我们前面我们在前面讲的时候,是不是是不是有个计算方法,这个计算方法传的就是一个后缀表达式对应的list,我们把这个运算一下。
28:10
来玩一把,现在呢,我们得到这个结果,现在把这个拿过来用一用啊,这个等于格式化一下。格式化一下,它的结果是多少呢?我们输出。百分号D。百分号D好,然后呢。然后我们用这个计算的方法把后缀表达式对应的历史放进去。好,我们看看这个结果对不对。对不对,首先呢,我们先自己人为的算一下对不对。呃,我们自己算这个结果应该是多少啊。自己算的话,这个结果应该是五乘以四等于二十二十加一个一,21 21减去一个五等于16,哦,它只要等于16就就正确了,来运行一下。
29:01
我们发现结果是没有毛病的啊,没有毛病,所以这个结果呢,的确是实有代码没有任何问题,没有任何问题,好,那关于到此呢,我们就把这个中缀表达式转后缀表达式的代码给大家实现了一把。
我来说两句