当前课程知识点:Data Structures and Algorithm Design Part I >  04.Stack+Queue >  C4.stack-App-infix >  04C4−6C

返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表

04C4−6C在线视频

下一节:04C4-6D

返回《Data Structures and Algorithm Design Part I》慕课在线视频列表

04C4−6C课程教案、知识点、字幕

这是一个操作数

所以我们直接将它归入操作数栈中

也就是说 接下来的状态应该是这样

5入栈 我们随即将注意力转向下一个字符

这是一个阶乘运算符

算法的处理手法依然

这里我们采用刚刚记下来的诀窍

当左括号在栈顶的时候

它总是乐于接收包括阶乘在内的

任何一个常规运算符

所以接下来,我们会看到

阶乘号不出意外地入栈

同时注意力转向下一个字符

我们看到这是一个减法运算符

同样地,将减法与阶乘进行优先级比较

会发现出现了一次大于号的情况

也就是说,我们刚才所缓冲起来的

阶乘运算现在等到了能够执行的时机

讲到这里,细心的你或许会发现

在我们目前所定义的运算符体系中

阶乘号是优先级最高的

所以即便是它被推入了栈中

在接下来的一步中,必将会出栈并且执行

既然如此,我们为什么不判断出来

阶乘号而直接运算呢

原因在于虽然可以利用这种性质

加速阶乘处理

但是无形中必然会引入一句额外的判断

而且这句判断是对所有的运算符

都要执行一次的

而我们刚才所做的优化的效果

只能体现在阶乘这一种运算上

得与失两相比较,得不偿失

所以不妨采用算法

所建议的这种简明的方法

统一进行处理

好了

回到我们的阶乘运算符

既然它可以运算

我们就应该

弹出栈顶元素5来进行运算

并且将所得的结果,我们心算一下

120重新纳回操作数栈中

作为新的栈顶

同时,我们的关注力依然停留在

仍未处理完毕的减法运算上

既然接下来,栈顶运算符是左括号

按照我们刚才所总结的规律

它总是乐于接收

包括减号在内的任何运算符

所以接下来,减法运算符会顺利地进栈

转为这样的一个状态

而此后呢,我们的关注力

转向接下来的字符,也就是左括号

我们刚刚总结过

左括号出现在当前的位置

它也会被任何栈顶操作符乐于接纳

所以它也会随即进栈

转入这样一个状态

我们的关注力,会转向下一个字符6

作为一个操作数

它也会顺利地推入操作数栈中

成为这样

接下来又碰到了

我们总结到的一个情况

左括号处于栈顶的时候

它也会乐于接受

包括当前的减号在内的

任何一个运算符

所以接下来减法运算符

也会顺利地进栈

我们又转向了下一个左括号

同样它会入栈

并且转向下一个操作数7

这个操作数会随即进栈

并转向下一个操作符减法

同样

这个时候栈顶既然是左括号

减法运算符也会顺利地入栈

这个时候我们又再次地遇到了左括号

左括号人缘非常好

它也会被任何一个字符接纳

成为它顶端的朋友

我们的关注力,这个时候转向了8

当然8会随即进栈

但是接下来,我们的注意力又转向了9

此时就涉及到我们在算法中

所提供的一个叫ReadNumber的例程

它的具体实现

虽然我们只是放在示例代码包中

但是我们从语义上能够知道

它是用来读取像89这样的多位数的

其实它的原理也非常简单

对于这样连续的一系列的数字

它会每一次都将上一次的结果弹出栈

乘以10,加上当前的这个字符

然后再重新地推入栈中

就这个例子而言

我们接下来应该把8弹出乘以10

再加上9,得到89

操作数栈的栈顶被替代为89

同时,我们的关注焦点转向下一个字符减法

再一次地,这个减法运算符

会被当前处于栈顶的

那个好客的左括号

接纳,成为它顶端的朋友

所以应该转入这样一个状态

而我们的关注焦点转向下一个数字0

同样,作为操作数,它会直接被推入栈中

变成操作数栈的栈顶

同时我们的关注力转向阶乘

经过查表,不出我们的意料

作为优先级最高的运算符

阶乘号自然会比减法更加优先

所以接下来

我们应该将这个阶乘运算符推入栈中

并且将注意力转向下一个字符

也就是右括号

Data Structures and Algorithm Design Part I课程列表:

01.Introduction I

-A.Computation

--01A-1

--01A-2

--01A-3

--01A-4

--01A-5

--演示

--01A-6

--(a)计算--作业

-B.Computational_Models

--01B-1

--01B-2

--01B-3

--01B-4

--01B-5

--01B-6

--01B-7

--01B-8

-B.Computational_Models--Homework

-C.Big_o

--01C-1

--01C-2

--01C-3

--01C-4

--01C-5

--01C-6

--01C-7

-C.Big_o--Homework

01.Introduction II

-D.Algorithm_analysis

--01D-1

--01D-2

--01D-3

--01D-4

--01D-5

--01D-6

--01D-7

-D.Algorithm_analysis--Homework

-E.Iteration+Recursion

--01E-1

--01E-2

--01E-3

--01E-4

--01E-5

--01E-6

--01E-7

--01E-8

--01E-09

-E.Iteration+Recursion--Homework

-F.Dynamic_Programming

--01XC-1

--01XC-2

--01XC-3

--01XC-4

--01XC-5

--01XC-6

-- 演示

--01XC-7

--01XC-8

--01XC-9

--01XC-A

-F.Dynamic_Programming--Homework

-Homework

02.Vector I

-A.Interface+Implementation

--02A-1

--02A-2

--02A-3

--02A-4

--02A-5

-A.Interface+Implementation--Homework

-B.extendable_vector

--02B-1

--02B-2

--02B-3

--02B-4

--02B-5

-B.extendable_vector--Homework

-C.unsorted_Vector

--02C-1

--02C-2

--02C-3

--02C-4

--02C-5

--02C-6

--02C-7

--02C-8

-C.unsorted_Vector--Homework

-D1.Sorted_Vector.uniquify

--02D1-1

--02D1-2

--02D1-3

--02D1-4

--02D1-5

-D1.Sorted_Vector.uniquify--Homework

-D2.Sorted_Vector.binary_search

--02D2-1

--02D2-2

--02D2-3

--02D2-4

--02D2-5

--02D2-6

--02D2-7

-D2.Sorted_Vector.binary_search--Homework

02.Vector II

-D3.Sorted_Vector.fibonaccian_search

--02D3-1

--02D3-2

--02D3-3

--02D3-4

-D3.Sorted_Vector.fibonaccian_search--Homework

-D4.Sorted_Vector.binary_search_optimized

--02D4-1

--02D4-2

--02D4-3

--02D4-4

--02D4-5

-D4.Sorted_Vector.binary_search_optimized--Homework

-D5.Sorted_Vector.interpolation_search

--02D5-1

--02D5-2

--02D5-3

--02D5-4

--02D5-5

-D5.Sorted_Vector.interpolation_search--Homework

-E.Bubblesort

--02 E-1

--02E-2

--02E-3

--02E-4

--02E-5

-E.Bubblesort--Homework

-F.Mergesort

--02F-1

--02F-2

--02F-3

--02F-4

--02F-5

--02F-6

-F.Mergesort-Homework

-Homework

03.List

-A.interface+Implementation

--03A-1

--03A-2

--03A-3

--03A-4

-A.interface+Implementation--Homework

-B.Unsorted_list

--03B-1

--03B-2

--03B-3

--03B-4

--03B-5

-B.Unsorted_list--Homewrok

-C.Sorted_list

--03C-1

--03C-2

--03C-3

-C.Sorted_list--Homewrok

-D.Selectionsort

--03D-1

--03D-2

--03D-3

--03D-4

--03D-5

--03D-6

-D.Selectionsort--Homework

-E.Insertionsort

--03E-1

--03E-2

--03E-3

--03E-4

--03E-5

--03E-6

--03E-7

--03E-8

-E.Insertionsort--Homework

-(xd):LightHouse

--03XD

-Homework

04.Stack+Queue

-A.stack-ADT+implementation

--04A-1

--04A-2

--04A-3

-A.stack-ADT+implementation--Homework

-C1.stack-App-conversion

--04C1-1

--04C1-2

--04C1-3

-C1.stack-App-conversion--Homework

-C2.stack-App-parentheses

--04C2-1

--04C2-2

--04C2-3

--04C2-4

--04C2-5

--04C2-6

-C2.stack-App-parentheses--Homewrok

-C3.stack-App-permutation

--04C3-1

--04C3-2

--04C3-3

--04C3-4

--04C3-5

-C3.stack-App-permutation--Homework

-C4.stack-App-infix

--04C4-1

--04C4-2

--04C4-3

--04C4-4

--04C4-5

--04C4−6A

--04C4−6B

--04C4−6C

--04C4-6D

-C4.stack-App-infix--Homework

-C5.stack-App-rpn

--04C5-1

--04C5-2

--04C5-3

--04C5-4

-C5.stack-App-rpn--Homework

-D.Queue-ADT+implementation

--04D-1

--04D-2

--04D-3

-Homework

05.Binary_Tree

-A.Tree

--05A-1

--05A-2

--05A-3

--05A-4

--05A-5

--05A-6

--05A-7

-A.Tree--Homework

-B.Representation

--05B-1

--05B-2

--05B-3

--05B-4

--05B-5

-B.Representation--Homework

-C.Binary_Tree

--05C-1

--05C-2

--05C-3

-C.Binary_Tree--Homework

-D.Implementation

--05D-1

--05D-2

--05D-3

--05D-4

--05D-5

-D.Implementation--Homework

-E1.Preorder

--05E1-1

--05E1-2

--05E1-3

--05E1-4

--05E1-5

--05E1-6

--05E1-7

--05E1-8

--05E1-9

-E1.Preorder--Homework

-E2.Inorder

--05E2-1

--05E2-2

--05E2-3

--05E2-4

--05E2-5

--05E2-6

--05E2-7

-E2.Inorder--Homework

-E4.LevelOrder

--05E4-1

--05E4-2

--05E4-3

-E4.LevelOrder--Homework

-E5.reconstruction

--05E5-1

--05E5-2

--05E5-3

-E5.reconstruction--Homework

-Homework

06.Graph

-A.Introduction

--06A-1

--06A-2

--06A-3

-A.Introduction--Homework

-B1.Adjacency_Matrix

--06B1-1

--06B1-2

--06B1-3

--06B1-4

--06B1-5

--06B1-6

--06B1-7

--06B1-8

--06B1-9

-B1.Adjacency_Matrix--Homework

-C.BFS

--06C-1

--06C-2

--06C-3

--06C-4

--06C-5

--06C-6

--06C-7

--06C-8

-C.BFS--Homework

-D.DFS

--06D-1

--06D-2

--06D-3

--06D-4

--06D-5

--06D-6

--06D-7

-D.DFS--Homework

-Homework

04C4−6C笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。