数据结构与算法：Python语言描述-栈和队列-课件.ppt

1、数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/1/4 4，栈和队列，栈和队列v 栈和队列的概念栈和队列的概念v 数据的生成，缓存，使用和顺序数据的生成，缓存，使用和顺序v 栈的实现和问题栈的实现和问题v 栈应用实例栈应用实例v 栈与递归，递归和非递归栈与递归，递归和非递归v 队列的实现和问题队列的实现和问题v 队列应用实例队列应用实例v 搜索问题搜索问题v 相关问题相关问题数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/2/概述概述n栈栈（stack）和和队列队列（queue）是两种使用最广泛的数据结构，它们都是两种使用

2、最广泛的数据结构，它们都是保存数据元素的是保存数据元素的容器容器，可以将元素存入其中，或者从中取出元素使用，可以将元素存入其中，或者从中取出元素使用（查看查看，或，或弹出弹出，即在取得元素的同时将其从容器里删除），即在取得元素的同时将其从容器里删除）n容器是一大类能保存数据元素的数据结构，它们都保证存入的元素可以容器是一大类能保存数据元素的数据结构，它们都保证存入的元素可以在将来取得，而被删除的元素不再存在于容器之中在将来取得，而被删除的元素不再存在于容器之中n栈和队列主要用于在计算过程中栈和队列主要用于在计算过程中临时性地临时性地保存元素保存元素q这些元素是前面计算中发现或产生的中间数据，需

3、要在后面使用这些元素是前面计算中发现或产生的中间数据，需要在后面使用q如果产生的中间数据暂时不用或者用不完，但将来可能要用到，就如果产生的中间数据暂时不用或者用不完，但将来可能要用到，就有必要临时保存起来有必要临时保存起来q栈和队列常用于生成和使用之间的缓冲，称为栈和队列常用于生成和使用之间的缓冲，称为缓冲存储缓冲存储或或缓存缓存n栈和队列的操作都比较简单栈和队列的操作都比较简单q最重要的就是存入元素和取出元素两个操作最重要的就是存入元素和取出元素两个操作q还可能有另外一些辅助操作，如创建，检查，判断空还可能有另外一些辅助操作，如创建，检查，判断空/满等满等数据结构和算法（Python 语言版

4、）：栈和队列(1)裘宗燕，2023-5-27-/3/概述概述n中间数据的生成有早有晚，时间上有先后。在实际应用中，使用这些元中间数据的生成有早有晚，时间上有先后。在实际应用中，使用这些元素也可能需要按时间顺序。有两种最典型的顺序如下：素也可能需要按时间顺序。有两种最典型的顺序如下：q按数据生成的顺序，后生成的数据需要先处理按数据生成的顺序，后生成的数据需要先处理q按数据生成的先后顺序处理，先生成的数据先处理按数据生成的先后顺序处理，先生成的数据先处理如去银行办事，先到的应先得到服务，具体等待方式不重要，如如去银行办事，先到的应先得到服务，具体等待方式不重要，如o 直接排在一个等待队列上直接排在

5、一个等待队列上o 拿（顺序）号后等叫号，每次叫尚未服务的最早来的顾客拿（顺序）号后等叫号，每次叫尚未服务的最早来的顾客n在这两种情况下，访问（并可能删除）都按默认方式确定元素在这两种情况下，访问（并可能删除）都按默认方式确定元素q栈和队列就是支持按这两种顺序使用元素的缓存数据结构栈和队列就是支持按这两种顺序使用元素的缓存数据结构q栈和队列存入操作只需要保证元素存入和将来取出的顺序，不记录栈和队列存入操作只需要保证元素存入和将来取出的顺序，不记录也不保证新存入元素与容器中已有元素之间的任何关系也不保证新存入元素与容器中已有元素之间的任何关系数据结构和算法（Python 语言版）：栈和队列(1)裘

6、宗燕，2023-5-27-/4/概述概述n栈和队列保证元素存取之间的时间关系，特点是：栈和队列保证元素存取之间的时间关系，特点是：q栈是保证缓存元素栈是保证缓存元素后进先出后进先出（Last In First Out，LIFO）的结构的结构q队列是保证缓存元素的队列是保证缓存元素的先进先出先进先出（先存者先用，（先存者先用，First In First Out，FIFO）关系的结构关系的结构n对于栈和队列，任何时候，下次访问或删除的元素都默认地唯一确定。对于栈和队列，任何时候，下次访问或删除的元素都默认地唯一确定。只有新的存入或删除（弹出）操作可能改变下次的默认元素只有新的存入或删除（弹出）操

7、作可能改变下次的默认元素n栈和队列的性质完全是栈和队列的性质完全是抽象的、逻辑的抽象的、逻辑的，对实现方式（如何实现相应时，对实现方式（如何实现相应时间顺序）并没有任何约束，任何能满足要求的技术均可使用间顺序）并没有任何约束，任何能满足要求的技术均可使用q最方便的技术是利用元素的排列顺序表示其先来后到关系，也就是最方便的技术是利用元素的排列顺序表示其先来后到关系，也就是说，可以用线性表作为栈和队列的说，可以用线性表作为栈和队列的“实现结构实现结构”q例如：把元素进入实现为表的后端插入，这样例如：把元素进入实现为表的后端插入，这样o 最老的元素总是最前面的元素（作为队列下次应访问和删除）最老的元

8、素总是最前面的元素（作为队列下次应访问和删除）o 最新的元素总是最后一个元素（作为栈下次应访问和删除）最新的元素总是最后一个元素（作为栈下次应访问和删除）数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/5/概述概述n栈和队列是计算中使用最广的缓存结构，其使用环境可以总结如下：栈和队列是计算中使用最广的缓存结构，其使用环境可以总结如下：q计算过程分为一些顺序进行的操作步骤计算过程分为一些顺序进行的操作步骤q执行的操作时会产生一些后面可能需要用的中间数据执行的操作时会产生一些后面可能需要用的中间数据q产生的某些数据无法立即用掉，需要保存起来以备后面使用产生的某些

9、数据无法立即用掉，需要保存起来以备后面使用q需要保存的数据的项数不能事先确定需要保存的数据的项数不能事先确定这种情况下，通常就需要用一个栈或一个队列作为缓存这种情况下，通常就需要用一个栈或一个队列作为缓存n栈和队列是许多重要算法的基础，后面有许多实例。栈和队列的性质和栈和队列是许多重要算法的基础，后面有许多实例。栈和队列的性质和操作效率，也是许多算法设计中的关键因素操作效率，也是许多算法设计中的关键因素n由于栈和队列在应用中的重要性，由于栈和队列在应用中的重要性，Python 的基本功能中包括了对栈的的基本功能中包括了对栈的支持（可直接用支持（可直接用 list），标准库提供了支持队列用途的结

10、构，标准库提供了支持队列用途的结构n下面分别讨论这两种结构的情况，包括下面分别讨论这两种结构的情况，包括性质和模型；实现和问题；一些应用；一些一般性问题性质和模型；实现和问题；一些应用；一些一般性问题数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/6/栈：概念栈：概念n栈（栈（stack），），有的书籍里称为有的书籍里称为堆栈堆栈，是一种容器，可存入数据元素、，是一种容器，可存入数据元素、访问元素、删除元素。在这里没有位置的概念访问元素、删除元素。在这里没有位置的概念栈保证任何时刻可以访问、删除的元素都是在此之前最后存入的那个栈保证任何时刻可以访问、删除的元

11、素都是在此之前最后存入的那个元素。因此确定了一种默认的访问顺序元素。因此确定了一种默认的访问顺序n栈的基本操作是一个封闭集合（与表不同），通常包括：栈的基本操作是一个封闭集合（与表不同），通常包括：q创建空栈创建空栈q判断栈是否为空（还可能需要判断满），判断栈是否为空（还可能需要判断满），is_empty()q向栈中插入（通常称向栈中插入（通常称推入推入/压入压入，push）一个元素，一个元素，push(.)q从栈中删除（从栈中删除（弹出弹出，pop）一个元素，空栈弹出报错，一个元素，空栈弹出报错，pop()q取当前（最新）元素的值（并不删除），取当前（最新）元素的值（并不删除），top()数

12、据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/7/栈：特性和基本实现考虑栈：特性和基本实现考虑n栈可以实现为（可以看作）只在一端插入和删除的表栈可以实现为（可以看作）只在一端插入和删除的表q因此有人（有书籍中）把栈称为后进先出（因此有人（有书籍中）把栈称为后进先出（LIFO）表表q进行插入或删除操作的一端称为栈顶，另一端称为栈底进行插入或删除操作的一端称为栈顶，另一端称为栈底n用线性表技术实现栈时，由于只需要在一端操作，自然应该利用实现最用线性表技术实现栈时，由于只需要在一端操作，自然应该利用实现最方便，而且能保证两个主要操作的效率最高的那一端方便，而且能保

13、证两个主要操作的效率最高的那一端q采用连续表方式实现，在后端插入删除都是采用连续表方式实现，在后端插入删除都是 O(1)操作（操作（!）q采用链接表方式实现，在前端插入删除都是采用链接表方式实现，在前端插入删除都是 O(1)操作操作栈通常都采用这两种技术实现栈通常都采用这两种技术实现n实现栈之前，先定义一个自己的异常类（实现栈之前，先定义一个自己的异常类（Python 的内部异常是一组类，的内部异常是一组类，都是都是 Exception 的子类，可以继承已有异常类定义自己的异常类）的子类，可以继承已有异常类定义自己的异常类）class StackUnderflow(ValueError):#栈

14、下溢（空栈访问）栈下溢（空栈访问）pass数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/8/栈：实现栈：实现n采用连续表技术实现，也会遇到连续表的各种相关问题采用连续表技术实现，也会遇到连续表的各种相关问题q用简单连续表，还是采用动态连续表（分离式实现的连续表）？用简单连续表，还是采用动态连续表（分离式实现的连续表）？q如果用简单连续表，就可能出现栈满的情况如果用简单连续表，就可能出现栈满的情况q采用动态连续表，栈存储区满时可以换一块更大的存储区。这时又采用动态连续表，栈存储区满时可以换一块更大的存储区。这时又会出现置换策略问题，以及分期付款式的会出现置换

15、策略问题，以及分期付款式的 O(1)复杂性复杂性nPython list 及其操作实际上提供了一种栈功能，可以作为栈使用及其操作实际上提供了一种栈功能，可以作为栈使用q建立空栈，对应于创建一个空表建立空栈，对应于创建一个空表 ，判空栈对应于判空表，判空栈对应于判空表q由于由于 list 采用动态连续表技术（分离式实现），作为栈的表不会满采用动态连续表技术（分离式实现），作为栈的表不会满q压入元素操作应在表尾端进行，对应于压入元素操作应在表尾端进行，对应于 lst.append(x)q弹出操作也应在尾端进行，无参的弹出操作也应在尾端进行，无参的 lst.pop()默认弹出表尾元素默认弹出表尾元素

16、q由于采用动态连续表技术，压入操作具有分期付款式的由于采用动态连续表技术，压入操作具有分期付款式的 O(1)复杂复杂性，其他操作都是性，其他操作都是 O(1)操作操作数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/9/栈：实现栈：实现n为了概念清晰、操作名更易理解、排除不符合栈性质的其他操作，应该为了概念清晰、操作名更易理解、排除不符合栈性质的其他操作，应该基于连续表定义一个栈类，用基于连续表定义一个栈类，用 list 作为其实现的基础作为其实现的基础class SStack():#基于顺序表技术实现的栈类基于顺序表技术实现的栈类 def _init_(se

17、lf):#用用list对象对象 _elems存储栈中元素存储栈中元素 self._elems=#所有栈操作都映射到所有栈操作都映射到list操作操作 def is_empty(self):return self._elems=def top(self):if self._elems=:raise StackUnderflow(in SStack.top()return self._elems-1 def push(self,elem):self._elems.append(elem)def pop(self):if self._elems=:raise StackUnderflow(in SS

18、tack.pop()return self._elems.pop()数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/10/栈：链接表实现栈：链接表实现n采用链接技术，可以借用采用链接技术，可以借用 LNode 类实现一个链接栈：类实现一个链接栈：class LStack():#基于链接表技术实现的栈类，用基于链接表技术实现的栈类，用LNode作为结点作为结点 def _init_(self):self._top=None def is_empty(self):return self._top is None def top(self):if self._to

19、p is None:raise StackUnderflow(in LStack.top()return self._top.elem def push(self,elem):self._top=LNode(elem,self._top)def pop(self):if self._top is None:raise StackUnderflow(in LStack.pop()p=self._top self._top=p.next return p.elem数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/11/栈的应用栈的应用n栈是算法和程序里最常用的辅助

20、结构，基本用途基于两方面：栈是算法和程序里最常用的辅助结构，基本用途基于两方面：q用栈可以很方便地保存和取用信息，因此常作为算法或程序里的辅用栈可以很方便地保存和取用信息，因此常作为算法或程序里的辅助助存储结构存储结构，临时保存信息，供后面的操作使用，临时保存信息，供后面的操作使用q利用栈后进先出的特点，可以得到特定的存储和取用顺序利用栈后进先出的特点，可以得到特定的存储和取用顺序许多实际运用结合了这两方面的特性许多实际运用结合了这两方面的特性n作为最简单的应用实例，栈可用于颠倒一组元素的顺序作为最简单的应用实例，栈可用于颠倒一组元素的顺序q将一组元素依次全部存入后取出，就能得到反序的序列将一

21、组元素依次全部存入后取出，就能得到反序的序列q通过不同的存入取出操作序列，可以得到不同的元素序列。但请注通过不同的存入取出操作序列，可以得到不同的元素序列。但请注意，这种做法不能得到任意的排列，结果序列有一定的规律性意，这种做法不能得到任意的排列，结果序列有一定的规律性n下面介绍栈的若干典型应用下面介绍栈的若干典型应用q有些比较具体，是特殊的应用有些比较具体，是特殊的应用q有些实例代表一大类应用，更具典型性有些实例代表一大类应用，更具典型性数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/12/简单应用：括号配对问题简单应用：括号配对问题n在许多正文中都有括号

22、，特别是在表示程序、数学表达式的正文片段里。在许多正文中都有括号，特别是在表示程序、数学表达式的正文片段里。括号有正确配对问题。作为例子，考虑括号有正确配对问题。作为例子，考虑 Python 程序里的括号程序里的括号q存在不同的括号：如圆括号、方括号和花括号存在不同的括号：如圆括号、方括号和花括号q每种括号都有开括号和闭括号，括号括起的片段可能相互嵌套，各每种括号都有开括号和闭括号，括号括起的片段可能相互嵌套，各种括号需要分别正确嵌套配对种括号需要分别正确嵌套配对n配对的原则配对的原则q遇到的闭括号应该匹配此前遇到的最近的尚未匹配的对应开括号遇到的闭括号应该匹配此前遇到的最近的尚未匹配的对应开

23、括号q由于多种由于多种/多次多次/可能嵌套，为检查配对，遇到的开括号必须保存可能嵌套，为检查配对，遇到的开括号必须保存q由于括号可能嵌套，需要逐对匹配，闭括号应与前面最近的尚未有由于括号可能嵌套，需要逐对匹配，闭括号应与前面最近的尚未有匹配的开括号匹配，后面括号应与更前面次近的括号匹配匹配的开括号匹配，后面括号应与更前面次近的括号匹配q可以删除匹配的括号，为后面的匹配做好准备可以删除匹配的括号，为后面的匹配做好准备n后遇到并保存的开括号应该先删除，这就是后进先出，而且要按照出现后遇到并保存的开括号应该先删除，这就是后进先出，而且要按照出现顺序，显然应该顺序，显然应该/可以用一个栈保存开括号可以

24、用一个栈保存开括号数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/13/简单应用：括号配对问题简单应用：括号配对问题n问题处理的线索已经清楚了：问题处理的线索已经清楚了：q顺序检查被处理正文（是一个字符串）里的一个个字符顺序检查被处理正文（是一个字符串）里的一个个字符q跳过无关字符跳过无关字符q遇到开括号时将其压入一个栈遇到开括号时将其压入一个栈q遇到闭括号时弹出栈顶元素与之匹配遇到闭括号时弹出栈顶元素与之匹配括号匹配则继续括号匹配则继续遇到不匹配时检查以失败结束遇到不匹配时检查以失败结束n下面考虑定义一个函数完成这个检查，其中先定义一些检查中需要使用下面考

25、虑定义一个函数完成这个检查，其中先定义一些检查中需要使用的数据和变量的数据和变量数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/14/简单应用：括号配对问题简单应用：括号配对问题n函数定义（很简单）：函数定义（很简单）：def check_pares(text):pares=()open_pares=(opposite=):(,:,:#表示配对关系的字典表示配对关系的字典 def paretheses(text):.#括号生成器，定义见后括号生成器，定义见后 st=SStack()for pr,i in paretheses(text):#对对 text 里

26、各括号和位置迭代里各括号和位置迭代 if pr in open_pares:#开括号，压进栈并继续开括号，压进栈并继续 st.push(pr)elif st.pop()!=oppositepr:#不匹配就是失败，退出不匹配就是失败，退出 print(Unmatching is found at,i,for,pr)return False#else 是一次括号配对成功，什么也不做，继续是一次括号配对成功，什么也不做，继续 print(All paretheses are correctly matched.)return True数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，20

27、23-5-27-/15/简单应用：括号配对问题简单应用：括号配对问题n括号生成器定义为（局部）函数括号生成器定义为（局部）函数def paretheses(text):i,text_len=0,len(text)while True:while i=text_len:return yield texti,i i+=1n生成器（回忆一下）：生成器（回忆一下）：q用用 yield 语句产生结果语句产生结果q可以用在需要迭代器的地方可以用在需要迭代器的地方q函数结束导致迭代结束函数结束导致迭代结束数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/16/简单应用：括号

28、配对问题简单应用：括号配对问题n总结：总结：q这个函数利用了栈的性质，这是关键这个函数利用了栈的性质，这是关键q函数开始先准备好处理中需要用的数据。虽然各种数据在程序里都函数开始先准备好处理中需要用的数据。虽然各种数据在程序里都只有一处使用，但这样定义使程序清晰易读，更易修改只有一处使用，但这样定义使程序清晰易读，更易修改q利用了利用了 Python 丰富的数据结构和操作，如丰富的数据结构和操作，如 in，not in 和字典等和字典等q定义理一个独立的括号生成器函数，使代码功能清晰。例如，定义理一个独立的括号生成器函数，使代码功能清晰。例如，要检查实际要检查实际 Python 程序里的括号，

29、还需要考虑跳过程序里的注程序里的括号，还需要考虑跳过程序里的注释和字符串等，修改括号生成规则时只需要修改这个函数释和字符串等，修改括号生成规则时只需要修改这个函数请自己考虑和练习请自己考虑和练习数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/17/表达式的表示、计算和变换表达式的表示、计算和变换n小学生就开始写表达式，先是算术表达式，后来是代数表达式小学生就开始写表达式，先是算术表达式，后来是代数表达式对二元运算符，通常把它们写在两个运算对象中间，这种写法称为对二元运算符，通常把它们写在两个运算对象中间，这种写法称为中中缀表示缀表示，按中缀表示法写出的表达式

30、称为，按中缀表示法写出的表达式称为中缀表达式中缀表达式n中缀表示很难统一贯彻，一元和多元运算符很难用中缀表示中缀表示很难统一贯彻，一元和多元运算符很难用中缀表示q代数表达式里的函数符号通常写在运算对象前面，这种写法称为代数表达式里的函数符号通常写在运算对象前面，这种写法称为前前缀表示缀表示。为界定函数参数的范围，通常用括号将它们括起。为界定函数参数的范围，通常用括号将它们括起q可见，常见的表达式习惯表示是前缀表示和中缀表示的组合可见，常见的表达式习惯表示是前缀表示和中缀表示的组合n实际上，表达式并不一定采用这种习惯写法实际上，表达式并不一定采用这种习惯写法q可以用纯粹的前缀表示，这样写出的表达

31、式称为前缀表达式可以用纯粹的前缀表示，这样写出的表达式称为前缀表达式q还有一种表达式写法称为后缀表示，其中运算符（函数）总写在它还有一种表达式写法称为后缀表示，其中运算符（函数）总写在它们的运算对象之后，这样写出的表达式称为后缀表达式。实际上，们的运算对象之后，这样写出的表达式称为后缀表达式。实际上，后缀表达式特别适合计算机处理后缀表达式特别适合计算机处理n前缀表达式也称为波兰表达式（由波兰数学家前缀表达式也称为波兰表达式（由波兰数学家 J.Lukasiewicz 于于1929提出），后缀表达式也称为逆波兰表达式提出），后缀表达式也称为逆波兰表达式数据结构和算法（Python 语言版）：栈和队

32、列(1)裘宗燕，2023-5-27-/18/表达式的表示、计算和变换表达式的表示、计算和变换n首先假设每个运算符有确定的元数（运算对象个数），而且元数唯一首先假设每个运算符有确定的元数（运算对象个数），而且元数唯一写表达式时，最重要的问题是准确描述写表达式时，最重要的问题是准确描述计算的顺序计算的顺序n中缀表达式的一个重要缺点是不能直接表示运算的顺序，需要借助于辅中缀表达式的一个重要缺点是不能直接表示运算的顺序，需要借助于辅助性约定和助性约定和/或辅助描述机制，实际情况：或辅助描述机制，实际情况：q必须引进括号机制，表示括号里的运算先做（显式描述计算顺序）必须引进括号机制，表示括号里的运算先做

33、（显式描述计算顺序）q为减少总写括号的麻烦，还引进为减少总写括号的麻烦，还引进优先级优先级概念，规定运算符的优先级概念，规定运算符的优先级（或优先级关系），高优先级运算符的结合性强，运算符相邻出现（或优先级关系），高优先级运算符的结合性强，运算符相邻出现时，优先级高的运算先做时，优先级高的运算先做q还需规定相同优先级的运算符相邻出现时的计算顺序（结合性）还需规定相同优先级的运算符相邻出现时的计算顺序（结合性）n与之对应的情况：在上述基本假定下，前缀表达式和后缀表达式都不需与之对应的情况：在上述基本假定下，前缀表达式和后缀表达式都不需要括号，也不需要优先级，就能自然地描述任意复杂的计算顺序要括号

34、，也不需要优先级，就能自然地描述任意复杂的计算顺序q可见，中缀表达式的表达能力最弱可见，中缀表达式的表达能力最弱q中缀表达式增加了括号后，几种表达方式具有同等表达能力中缀表达式增加了括号后，几种表达方式具有同等表达能力数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/19/表达式的表示、计算和变换表达式的表示、计算和变换n对比几种不同表达式形式。下面三个算术表达式等价对比几种不同表达式形式。下面三个算术表达式等价q中缀：中缀：(3-5)*(6+17*4)/3q前缀：前缀：/*-3 5+6*17 4 3q后缀：后缀：3 5-6 17 4*+*3/三个表达式描述的

35、是同一个计算过程三个表达式描述的是同一个计算过程n下面先考虑后缀表达式的求值，假定下面先考虑后缀表达式的求值，假定q被处理的是算术表达式被处理的是算术表达式q其中的运算对象是浮点数形式表示的数其中的运算对象是浮点数形式表示的数q运算符只有运算符只有+、-、*、/，都是二元运算符，都是二元运算符n后面还要讨论不同表达式形式的转换（考虑中缀形式到后缀形式）后面还要讨论不同表达式形式的转换（考虑中缀形式到后缀形式）研究相应的转换算法，以及中缀表达式的求值研究相应的转换算法，以及中缀表达式的求值数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/20/后缀表达式的计算后

36、缀表达式的计算n考虑计算过程，设有函数考虑计算过程，设有函数 nextItem()得到下一个运算对象或运算符：得到下一个运算对象或运算符：q遇到运算对象，需要记录以备后面使用遇到运算对象，需要记录以备后面使用q遇到运算符（或函数名），需要根据其元数取得前面最近遇到的几遇到运算符（或函数名），需要根据其元数取得前面最近遇到的几个运算对象或已做运算得到的结果，实施计算并记录结果个运算对象或已做运算得到的结果，实施计算并记录结果问题：应该用什么结构记录信息？问题：应该用什么结构记录信息？n看看计算过程的性质：看看计算过程的性质：q需要记录的是已经掌握但还不能立即使用的中间结果需要记录的是已经掌握但还

37、不能立即使用的中间结果q遇到运算符时，要用的是此前最后记录的几个结果（根据元数）遇到运算符时，要用的是此前最后记录的几个结果（根据元数）显然应该用栈作为缓存结构显然应该用栈作为缓存结构n上面分析也说明了算法的基本结构上面分析也说明了算法的基本结构实际程序就是把这个算法用实际程序就是把这个算法用 Python 的语言写出来的语言写出来数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/21/后缀表达式的计算后缀表达式的计算n先考虑算法的框架先考虑算法的框架n假定假定 st 是栈，算法核心是个循环（逐个处理运算符或运算对象）：是栈，算法核心是个循环（逐个处理运算符或

38、运算对象）：while 还有输入还有输入:x=nextItem()if not is_operator(x):st.push(float(x)else:a=st.pop()#第二个运算对象第二个运算对象 b=st.pop()#第一个运算对象第一个运算对象 .#根据运算符根据运算符 x 对对 a 和和 b 计算计算 .#计算结果压入栈计算结果压入栈n这里写了几个辅助过程，其具体实现依赖于一些情况这里写了几个辅助过程，其具体实现依赖于一些情况q被求值的表达式从哪里获得被求值的表达式从哪里获得q表达式里的元素如何表示（下面假定用字符串）表达式里的元素如何表示（下面假定用字符串）数据结构和算法（Pyt

39、hon 语言版）：栈和队列(1)裘宗燕，2023-5-27-/22/后缀表达式的计算后缀表达式的计算n假定从函数参数获得输入假定从函数参数获得输入参数是一个字符串，内容是需要求值的后缀表达式参数是一个字符串，内容是需要求值的后缀表达式表达式中不同的项之间有空格分隔表达式中不同的项之间有空格分隔n为程序清晰，定义了一个包装过程：为程序清晰，定义了一个包装过程：#定义一个函数把表示表达式的字符串转化为项的表定义一个函数把表示表达式的字符串转化为项的表def suffix_exp_evaluator(line):return suf_exp_evaluator(line.split()n定义一个扩充

40、的栈类，增加一个检查栈深度的方法：定义一个扩充的栈类，增加一个检查栈深度的方法：class ESStack(SStack):def depth(self):return len(self.elems)n下面是核心求值过程的定义（与前面设计相比有一些小修改）下面是核心求值过程的定义（与前面设计相比有一些小修改）由于函数的输入就是一个项的表由于函数的输入就是一个项的表数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/23/后缀表达式的计算后缀表达式的计算def suf_exp_evaluator(exp):operators=+-*/st=ESStack()#扩充

41、功能的栈，可用扩充功能的栈，可用 depth()检查栈内元素个数检查栈内元素个数 for x in exp:if not x in operators:st.push(float(x);continue#不能转换不能转换时时自动引发异常自动引发异常 if st.depth()=priorityx):exp.append(st.pop()st.push(x)#当前运算符进栈当前运算符进栈数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/28/中缀表达式到后缀表达式的转换中缀表达式到后缀表达式的转换 while not st.is_empty():#处理栈里剩下的

42、运算符处理栈里剩下的运算符 if st.top()=(:#如果还有左括号，就是不配对如果还有左括号，就是不配对 raise SyntaxError(Extra(.)exp.append(st.pop()return expn为测试方便，定义一个专门用于测试的辅助函数：为测试方便，定义一个专门用于测试的辅助函数：def test_trans_infix_suffix(s):print(s)print(trans_infix_suffix(s)print(Value:,suf_exp_evaluator(trans_infix_suffix(s)数据结构和算法（Python 语言版）：栈和队列(1

43、)裘宗燕，2023-5-27-/29/中缀表达式到后缀表达式的转换中缀表达式到后缀表达式的转换n把生成表达式里各个项的工作定义为一个生成器：把生成表达式里各个项的工作定义为一个生成器：def tokens(line):i,llen=0,len(line)while i llen:if linei.isspace():i+=1;continue if linei in infix_operators:#遇到运算符遇到运算符 yield linei;i+=1;continue j=i+1#处理运算对象处理运算对象 while(j llen and not linej.isspace()and li

44、nej not in infix_operators):if(linej=e or linej=E)#处理负指数处理负指数 and j+1 0数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/34/栈与递归栈与递归n考虑递归定义的函数考虑递归定义的函数 factdef fact(n):if n=0:return 1 else:return n*fact(n-1)n不难看到下面一些显然的情况（以不难看到下面一些显然的情况（以 fact(6)的计算为例）的计算为例）q为得到为得到 fact(6)的结果，必须先算出的结果，必须先算出 fact(5)q在计算在计算 f

45、act(6)时函数的参数时函数的参数 n 取值取值 6，而在递归调用计算，而在递归调用计算 fact(5)时，函数的参数时，函数的参数 n 取值取值 5，如此下去，如此下去q递归调用计算出递归调用计算出 fact(5)的值之后还需乘以的值之后还需乘以 6 以得到以得到 fatc(6)的值，的值，这说明在递归调用这说明在递归调用 fact(5)时时 n 具有值具有值 6 的情况需要记录（保存）的情况需要记录（保存）q需要这样记录的数据量与递归的次数成线性关系，无常量限制，因需要这样记录的数据量与递归的次数成线性关系，无常量限制，因此不能用定义几个整型变量的方式保存此不能用定义几个整型变量的方式保

46、存q在递归调用中保存的数据，如在递归调用中保存的数据，如 6,5,.，后保存的将先使用，后保存的将先使用q后进先出的使用方式和数据项后进先出的使用方式和数据项数无明确限制，说明应该用一数无明确限制，说明应该用一个栈支持递归函数的实现个栈支持递归函数的实现数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/35/栈与递归栈与递归n看阶乘函数导致的递归计算看阶乘函数导致的递归计算def fact(n):if n=0:return 1 else:return n*fact(n-1)n假定现在执行假定现在执行 fact(3)，与此有关与此有关的实际数据共有三项的实际数据

47、共有三项q计算结果计算结果qn 的值的值q计算后回到的位置计算后回到的位置n递归调用递归调用 fact(2)，fact(1)和和 fact(0)的情况都一样的情况都一样3r12r21r20r21126栈增长方向栈增长方向数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/36/栈与递归栈与递归/函数调用函数调用n支持递归的实现需要一个栈（运行栈），实现递归函数时支持递归的实现需要一个栈（运行栈），实现递归函数时q每个具体递归调用都有一些局部信息需要保存，语言的实现在运行每个具体递归调用都有一些局部信息需要保存，语言的实现在运行栈上为函数的这次调用建立一个帧，其中

48、保存有关信息栈上为函数的这次调用建立一个帧，其中保存有关信息q函数执行总以栈顶帧作为当前帧，所有局部变量都在这里有体现函数执行总以栈顶帧作为当前帧，所有局部变量都在这里有体现q进入下次递归调用时，将为它建立一个新帧进入下次递归调用时，将为它建立一个新帧q从递归调用返回时，上层取得函数调用的结果，并弹出已经结束的从递归调用返回时，上层取得函数调用的结果，并弹出已经结束的调用对应的帧，然后回到上一层执行时的状态调用对应的帧，然后回到上一层执行时的状态所有递归程序的执行都是这种模式所有递归程序的执行都是这种模式n实际上，一般的函数调用和退出的方式也与此类似实际上，一般的函数调用和退出的方式也与此类似

49、q目前各种语言都按这种模式实现了一套支持函数调用和返回的机制，目前各种语言都按这种模式实现了一套支持函数调用和返回的机制，其中最重要的数据结构就是一个运行栈其中最重要的数据结构就是一个运行栈q其中保存所有已经开始（被调用）执行但还没有结束的函数的局部其中保存所有已经开始（被调用）执行但还没有结束的函数的局部信息（局部变量的值约束等）信息（局部变量的值约束等）数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5-27-/37/栈与函数调用栈与函数调用n程序里函数嵌套调用是按程序里函数嵌套调用是按“后调用先返回后调用先返回”的规则进行的规则进行q这种规则符合栈的使用模式这种规

50、则符合栈的使用模式q用栈可以自然地支持函数调用的实现用栈可以自然地支持函数调用的实现def main():m=.n =.first(m,n)#位置位置1 def first(s,t):i=.s.t.second(i+s)#位置位置2 return.def second(d):x=.y=.x.y.d .return.n支持函数调用的进行，语言实现需要做一些内部动作支持函数调用的进行，语言实现需要做一些内部动作在进入新函数前保存一些信息，退出函数时恢复调用前状态并继续在进入新函数前保存一些信息，退出函数时恢复调用前状态并继续数据结构和算法（Python 语言版）：栈和队列(1)裘宗燕，2023-5