04C5-4 慕课视频播放-Data Structures and Algorithm Design Part I-MOOC慕课视频教程-柠檬大学

回到我们此前所学过的

中缀表达式的求值算法

相信你已经对这个算法比较熟悉了

所以我们这里为了简便

只列出了其中最主要的框架

这个算法在对中缀表达式

进行求值的同时

也捎带着完成了RPN的转换和生成

你现在应该知道

为什么这个接口

需要提供一个名为RPN的

引用型的字符串了吗？

对了

它最终返回的就是原来

中缀表达式所对应的RPN

如果你对这个还有点怀疑的话

建议你打开我们的示例代码

并且对这段代码进行编译执行

如果你的方法得当

我相信你应该能看到

RPN转化的详细过程

以及最终的结果

如果我们对这个算法

进行一个关键词RPN的搜索

我们会发现对RPN的引用和修改

无非只出现在两个位置

第一处位置对应的是

我们当前扫到的这个字符

是一个数字digit

我们曾经讲过

这意味着遇到了一个数字

因此我们可以通过

readNumber把这个数字读进来

那么它将作为一个操作数

被推入操作数栈中

而随即呢？大家看到

我们可以非常简明地

直接将刚刚推入栈顶的这个操作数

续接到当前的RPN尾部

而else另一种情况

也就是当前的字符实际上

是一个运算符的时候

我们并没有急于像刚才运算数那样

直接把它后缀到RPN的尾部

而是只在某些特定的时候

才将它缀在其后

什么时候呢？

我们可以看到

在else这个分支底下

还有很多个sub case子分支

其中只有当对应于

大于号的优先级关系

也就是说

栈顶的这个元素可以立即执行的时候

当然只要表达式的语法正确

每一个运算符都会入栈

而且都会等到它应该执行的那一天

那这一天是什么时候呢？

考察任意的这样一个运算符

以及它所对应的那个子表达式

还有无论是显式的

还是像刚才我们手动方法

那样加入的隐式的

总会有一对对应的括号

我们说只有当我们的求值算法

扫描到这个显式的

或者隐式的括号的时候

这个运算符执行的时机

也恰好就在此时

请注意

对应的那个右括号就是

这个运算符被真正执行的时机

所以反过来我们就在它

真正执行的那个时候

将它续接到RPN的尾部

其实完全就等同于

我们刚才在手动的算法中

将这个运算符移到紧邻于

它所对应的这个右括号的右侧

二者实际上在做同一件事情

只不过刚才你需要纸和笔

而现在呢是由这个算法

聪明地简便地帮你实现的

好了

现在你应该对这样一个

原本是用来求值的算法

同时还能够正确地完成RPN转换

不存质疑了吧？

在说再见之前

我还希望大家和我一起

来反观一下这段程序

我们可以看到对于操作数来说

每遇到一个就随即接至RPN的末尾

所以这也是为什么

它们不会改变相对的次序

而运算符呢

你刚才已经看到了未必如此

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

04C5-4 在线视频

04C5-4 课程教案、知识点、字幕

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

01.Introduction I

01.Introduction II

02.Vector I

02.Vector II

03.List

04.Stack+Queue

05.Binary_Tree

06.Graph

04C5-4 笔记与讨论

也许你还感兴趣的课程: