00:00
同学们,我们继续来讲解这一个数据结构,站那前面呢,我们讲了一个逆波兰计算器,对吧?那也就是说我们在输入一个表达式的时候呢,我们实际上是按一个逆波兰表达式去输入的,这样呢,对计算机来说很方便,但是对人来说呢,它又变得不方不方便了,所以说下边呢,我们要讲一个新的知识点。或者说在我们面试中经常被问到的一个知识点什么呢?就是如何将中缀表达式转成后缀表达式。这么一个知识点。那刚才老师已经给他分析了,后缀表达式呢,适合计算,计算机的一种运算,但是人他不太容易写出来,你比如说同学们看到前面我们这一个,大家看到这是一个。中缀表达式它对应的后缀表达式呢,是这样子的,也就是说逆波兰表达式是这样子的,那同学们也看到,对于一个比较长的或者比较复杂的一个中缀表达式呢,其实你不太容易一眼看出来,对吧?尤其是假设我们还带了括号,就更麻烦了。因此呢,现在我们来研究一个问题是在实际的开发中呢,我们需要将中缀表达式转成后缀表达式。
01:28
明白这意思吧,因为后缀表达式更适合计算机的运行,那现在呢,我们就来分析一下中缀表达式转后缀表达式的一个具体的一个步骤,那具体的步骤呢,同学们可以看到,下面呢,我已经把这个具体的步骤给大家整理好了。也就是说中缀表达式转后缀表达式的一个具体步骤呢,咱们已经有了,我们来给大家讲一讲它的步骤,大概要分这么八步。那么为了让同学们能够快速的理解中缀转后缀表达式呢?我这里有个具体的案例,我们结合起来说一下,好吧,那现在呢,我们来打开一个Excel表。
02:09
诶,我们打开一个Excel表。然后呢,我们一边画图一边为同学们讲解,打开我们的笔记。笔记打开,然后再打开我们的一个Excel图。OK,我们来一起看一看啊,同学们。那这样子呢,图解的方式大家比较容易理解。好,我先写上一句话,就是所谓的宗罪。中缀表达式转转后缀。后缀表达式的一个思路步骤分析。好吧,分析。分析。好,首先呢,我们先把这个步骤给同学们拿过来,待会儿呢,我们有针对性的对照来看一看,具体步骤呢,是这个样子的,我先把它拿过来啊,同学们。
03:04
放这儿。放这儿,然后为了好看呢,我给他一个颜色。对不对,好,这个这个粘过来过后,他这个标号就没有了,我把这个标号重新标一标。三。第四一步对吧,里面第四一步里面里面又分成三个小的步骤,也就它这里面还有三个逻辑。然后第四步完了过后呢,后面还有四部,我们也把它整理过来,待会儿呢,我们有针对性的进行一个讲解,这个稍微有一点麻烦啊,同学们注意听讲。哦,这是第五一个步骤,第五个步骤里面呢,又分两个步骤,第六一个步骤。第七个步骤。第八一个步骤。好OK,那嗯,这边是它的一个步骤,这边是它的一个标题,把这个标题呢,我们标粗一点。
04:00
那么具体呢,这边还有一个表格,我们来看一看表格,这个表格呢,我们就拿一个具体的例子,结合刚才的步骤,一步一步分析,我把这个表格也拿过来。待会儿呢,我们有针对性的来进行一个评价啊,有针对性的进行一个比较。好,我把这个先拿过来放这放这呢,然后为了好看,这边稍微的往边挪一下啊,这样好看一点。好,现在我们来分析一把,我们来分析一把,说现在有一个中罪表达式是这个样子的。这个是大家可以看到这是一个中缀表达式。我们写到这儿啊,这是一个中罪,这这个是一个中缀表达式,大家应该能看出来吧,这是一个宗罪。中缀表达式,那么我通过下面的步骤呢?我希望把它转成一个后缀。后缀表达式。那么我们来看一看后缀表达式是怎么转过来的。
05:03
后缀表达式是怎么转过来的?就以这个具体的案例来讲解。好,同学们,为了好讲解呢,我先把这个地方。呃,隔成几个空格,为什么要隔成空格呢?因为待会儿呢,我要进行讲的时候,我这需要画一个指针。待会儿呢,我这里有个指针。就是相当于是一个索引,不停的在扫描这个字符串,最后呢,把它变成一个后缀表达式,好,同学们,我们开始按照这给大家写好的一个步骤,我们来捋一捋这个思路。我们来捋一捋思路。首先第一步初始化两个站。运算一个站是S1,这个站是用来存放运算符的,第二个站呢,是存储中间结果的站,叫S2。好,为了好讲呢,我同样在这画两个赞,认真听讲啊。听讲好,这儿有一个站。好,这是第二个站,那那么呃,我往这个往下面挪一挪啊,好,这样好看一点啊,这样好看一点,那这个第一个站呢,我们给它取个名字叫一。
06:11
它是用来存号,存放我们符号的。好,第二个站,同学们看第二个站呢,是这个站S2这个站。好,现在呢,我们按照这个步骤开始来玩啊,第一步,首先呃初始化,假设初始化我们已经有了S1和S2这个站,第二步从左至右,从左至右扫描中缀表达式就是我们这假定有个索引在不停的扫描,没问题吧,当遇到操作数的时候,直接压入S2这个站。也就是说,如果是数直接入S2这个三,那现在呢,我们扫描到是几了?扫描到一了没问题吧,那现在呢,我们先把一放入。当我们把一放进去过后。
07:00
当我们把一放进去过后,同学们。诶,这个地方还有点小问题啊,把这个稍微放高拉高一点。高一点好,当我们把它放到一里面去了,过后呢,我们假定这有一个。站顶指向他。是不是前面我们讲过这有站顶吧,为了好看,我们标这个颜色,用这个箭头表示站顶的一个索引就是这个top。那么紧接着又去扫描加号,大家看当遇到运算符的时候呢,它的逻辑一共有三个。呃,它这个运算符呢,比较它与S2占顶的运算符的优先级。这里面分三个情况,如果目前S1为空或者占顶运算符为左括号,那么直接将运算符入账,显然是入的是。S1这个站没有问题吧,也就是说现在遇到加号应该符合哪个条件呢?这个条件,那也就是说现在呢,我们需要把这个加号直接入账。
08:05
这个大家看能能理解啊,加号入站,加号入站过后呢,我们认为此时此刻也有一个站点指向了它,那么这个时候呢,我们用另外一个颜色指色。好,紧接着继续扫描,现在扫描到一个主括号,同学们他说了,遇到括号的时候怎么处理呢?遇到括号的时候我们怎么处理呢?如果是左括号就直接压入S13,现在是左括号还是右括号,左括号好,如果是左括号,我们直接将这个压进去,压进去过后这个站顶往上移动没问题吧。没问题,紧接着再扫描是不是还是一个左括号,那没什么可说的,直接又入账。没吧,好,紧接着我们发现是二二呢,没有什么可说的,直接入账。往这移动一下,当然这个呢也上移了,入站的操作嘛,紧接着我们遇到加号,注意遇到这个加号的时候呢,它满足是运算符的问题,大家看。
09:08
此时显然呃,S一并不为空,那就看下面,如果你的优先级,什么谁的优先级呢?就是准备正在扫描的这个运算符的优先级,它比占顶的预算符高。也将他加入S1站。也将它加入S,那么现在想一想加号的运算符。加号的运算符,加号的运算符有这个括号的运算符优先级高吗?显然是没有的。那这个时候就是符合三这个条件,因为它没有占顶这个运算符高嘛,因为小括号的运算符肯定很高的了,那么其实将S1站点的运算符弹出并压入到S2这个站。大家理解是什么意思吗?就是将S1占顶的运算符。我们看看这里面啊,优先级大于现在不符合,不符合那就啊,那就看这个加号啊,将S1站点的运算符弹出并压入S2站,然后再转到4.1这个这个四杠一是代表4.1,就是重新回到这个地方操作啊,那大家想现在我们遇到这个加号,此时此刻这个加号应该怎么怎么处理呢。
10:24
同学们看。看下应该怎么处理。现在这个小括号啊。它它现在是小括号,既然是小括号的话呢,我们我们应该这样去考虑,小括号它并不算是一个运算符。是不是小括号不不算是运算符,所以我刚才说的那有问题,因为你小括号并不是运算符嘛,对不对,我们加减乘除才是运算符,因此呢,这个时候咱们呢,是就应该它不,它相当于是不是运算符,如果不是运算符的话呢,我们就直接怎么样把这个加号入账就可以了。
11:06
诶,刚才我们说的是有小问题啊,如果是加号就直接入账,因为小括号并不是一个运算符,它只是表它是改变我们运算的一个顺序的。对不对,好,那这个时候这个加号咱们就放进去了。对不对,这时我们就把这个加号放入到我们这一个一这个站没有任何问题。没有任何问题,那紧接着呢,我们继续扫描下面扫描到一个三好三呢,直接入账。放松一点。没问题吧,好,紧接着我们继续扫描这个括号,这个时候是个右括号,右括号我们看这里右括号是什么呢?则依次弹出S1占领的运算符,并压入S1。A as2直到遇到左括号为止,此时一对括号就丢弃了,这句话什么意思?就说现在我们遇到这个右括号,相当于就要把这个括号。
12:08
给消除掉。那这个时候应该怎么办呢?先把这边这个加号弹出来,放到这里面去,先让它往上移了。它一往上移,肯定你弹出来过后,它就往下移,同时这个加号呢,我们可以认为没有了啊,实际上它还它还在这个站里面,只是我们认为没有了,这个时候又遇到一个小括号怎么办呢?小括号也被干掉,所以说往下移这个就没有了,这个小括号就相当于这个小括号就被消除掉了,明白我的意思吧。紧接着,他继续扫描惩罚。那么同学们看到乘号,乘号呢,呃,运是一个运算符,这个时候因为这个小框呢,它。他这个时候我们我们认为。它的优先级呢,我们不做比较了,因为小括号的我们认为它只是改变一个运算规则的嘛,运算顺序的,所以说此时此刻呢,这个惩罚就直接入战。
13:05
二乘法就直接入账。好,那现在呢,我们就把这个乘法直接入战了。陈浩,入站往上移动,然后紧接着继续扫描,现在是不是扫描是把四四是数直接入站。也没有问题,紧接着我们又扫描到一个右括号,右括号根据前面的这个规则是把这个弹出来放到这里来。它往上移动。然后呢,这个往下移动,因为你弹战了吗?这个星号相当于没有了,这个时候又遇到一个小括号往下移动。相当于把。又一个向左的小括号消除掉了。紧接着我们继续扫描减号,那么同学们看减号和加号的优先级谁高谁低呢?谁高谁低,看这里他说若优先级比占顶的高,则压入SC,那现在我减号和加号的优先级是一个级别。
14:04
是不是一个级别,如果是一个级别的话呢?实际上就应该满足第三个条件,将S1占顶的符号这个运算符弹出,并压入S2这个站。那也就是说此时的这个加号呢,弹到这来了,同样往下移动。往下一动。好,这个时候相当于没有了,那么现在没有的话,问题是当做完这个事情,再回到4.1这个操作。也就是说。当他这个弹出完完了后,你再判断S1压入站,把这个弹出压入S站过后,再回到这个4.1这个逻辑继续做,现在大家想S1目前是不是空的。如果是空的,是不是应该把这个减号直接。入战。能理解我意思吧,直接入到S1这个站,如果一站,然后再扫描到554数,没有什么可说的,直接入站。
15:00
那现在呢,我们这一头的占领呢,已经到这儿了。好,这个往上面往下面来一下,也就是说现在指到这儿了,指到这里以后,同学们看我们整个这个中缀表达式就扫描完毕,那么扫描完毕过后呢,大家看这里。他说,将S1中剩余的运算符依次弹入并压入S2,现在S1是不是只有一个了,那就把它弹出来,弹出来,放到这里来。好,当然这个弹出来过后,我们认为这边也就没有了啊,我再说一遍啊,实际上这个减号呢,呃,我再说一遍,实际上这个减号还在这个A1站,只是呢,我们这个站顶往下移动,你相当于就访问不到了,最后大家看到这个结果。看到没有,在S2这个站里面呢,我们看。大家看这里S二战到第八部了,依次弹出S2中的元素,并输出结果的逆序。
16:02
则为中缀表达式对应的后缀表达式,那么我们来看看,如果我们按这个顺序来弹出的话,是不是它应该是这样子的。就是出站啊,将将S2出站,出站它的顺序应该是减。五加乘四加321,但是人家讲了啊。这个并不是最终的结果,而应该是什么呢?而是它对应的一个逆序才是后缀,那应该是什么呢?就是123。加四乘加。五减同学们,最后这个结果是它。我们来看看这个是不是我们的后缀表达式呢?就是前面这个中缀表达式对应的后缀表达式就是这个,同学们看这两个是不是对应的关系呢?我们发现是的。
17:01
看啊,是的。那有些同学你怎么知道是呢?大家看我这里不是已经把答案给出来了吗?它的结果是不是123加四乘加五减,是不是123加四乘加五减完全一样?成加不减,所以说这样我们就把一个什么呢,把一个就是中缀表达式转后缀表达式的一个步骤给同学们说出来了。同学们可能会在这儿去想一个问题啊,我想大部分同学听到这儿呢,都会去想说老师。呃,这边这个图跟刚才分析一样啊。所以这边这个图和刚才这个分析是一样的,我就没有照着这个表格来讲了,你们有兴趣可以按照这个步骤来看,跟我刚才说的是一一模一样的,那么有些同学讲老师他怎么你怎么知道中缀表达式转后缀表达式是这个思路呢?你如果这样问,我就觉得问的特别好。
18:00
说我怎么知道中缀表达式转后缀表达式是这个思路呢?我告诉大家,这个不是我想出来的。这个中缀表达式转后缀表达式的这个思路啊,是已经有什么呢?已经有相应的计算机这个专家或者他们设设计者把这个方法已经告诉我们了,我们才知道是这样做的。说老师,我们那同学可能问说老师,我们自己能不能想一个呢?想一个这个思路和步骤,我们自己来设计一个这样的算法,或者设计自己设计一个步骤来做这个事情,可不可以呢?可以,但是很难。但是很难,我做一个比较吧,我给大家打一个比方啊,我我给打一个比方。比方啊,比方啊,打比方,比如说你现在,你现在要去学一门武功,叫什么呢?叫叫这个武功叫叫降龙十八掌,不叫降龙十八掌。降龙十八掌。
19:01
这个武功降龙十八掌是很厉害的,对不对,那么现在你你有两,你有两个这个这个层面可以学习,第一个呢,你就是学习。你就是学习这个这个武功,然后呢,你去应用这个武功啊,你就用这个武功,应用应用这个武功,这是一个层面。就说你自己有一个心法了,就说别人已经有武林宗师把这个降龙十八掌已经这个心法,还有他的招式已经设计出来,你要做的就是学习和应用,这是一个,这是一个层次。这是一个层次,还有一种层次呢,是什么呢?就说你你你自己去设计了一个武功,或者你自己自创了一套武功,然后去用单想。谁的层次更高呢?显然,如果你,如果你自己自己去创造一套武功。那这个档次就太高了。
20:00
所以说回到我们这边说,我们告诉大家中缀表达式转后缀表达式,它的步骤是这样子的,老师也想不出来。我也是看书。看资料哦,发现人家是这样一个步骤,所以说我们就这样去讲的,那如果说我们自己要去设计一个这样的步骤,同学们就那就需要我们更高的一个水平。所以说我们在后面学这个算法也是一样的道理,算法呢,你同样涉及到这样几个层面,比如说我把这个地方给大家写一写啊,简单的聊聊一下,比如说我们同学们在后面学这个算法呢,其实你你你是可以有这样几个思路的,比如说后边我们学这个算法。算法呢,其实第一个层面。就第一个。第一个层面。第一个层面是什么呢?就是说你去理解,去理解这个算法。你首先要理解算法,然后呢,你你能灵活的运用,运用这个算法解决问题。
21:04
这是一个层面,那么第二个层面呢,第二个层面,第二个层面就是说。就说说老师,我现在我希望希望自己去设计一个算法。我自己设计一个算法,然后呢,我再去运用运用这个算法,显然同学们第二个的层次更高。比如说我们我们现在常用的排序算法有八个。对不对,所以说这些算法呢,人家已经给我们设计好了,我们去理解,我们去运用,但是说说老师,我们这我觉得这三这八大算排序算法都不行,我要去搞一个更牛逼的算法。可不可以呢?可以,那就需要相当深厚的这个数学的功底和计算机的这个功底,所以说你要自己去设计一个算法,其实都会用你的名字来命名的,比如说后面我们讲的弗洛伊德算法,为什么人家叫弗洛伊德算法呢?就是因为这个算法是美国的一个叫弗洛伊德的一个教授,他发现并设计出来的。
22:05
所以一个算法,一个成熟的算法,其实要设计出来是有一定难度的,但是我们要去理解这个算法并应用这个算法呢,相对来说容易,但是也要付出很多,就好比刚才老师讲的中缀表达式转后缀表达式这个道理对吧,你说老师你这个步骤,八个步骤你怎么知道的,对不对,因为我们看书了,我们看资料,人家说是这样做的,明白啊,好,同学们,那关于我们这一个中缀表达式转后缀表达式的思路呢,我们就分析到这里,一会儿呢,我们用代码将其实现。我们用代码将其实现好。关于思路的分析,我们就先给大家聊到这里。
我来说两句