**本博客内容根据慕课浙大数据结构2.2课栈总结整理而成。如果对博客中的算法有任何疑问，请指正问题**：当计算机面对一个复杂的算术表达式时，如何计算呢？思考过程：首先，如果是一个简单的算术表达式3+2，我们可以将这个表达式从左到右分解为操作数3、2和操作符“+”，然后我们很容易得到结果是5，如果我们用机器来计算也是一样。但是我们知道操作符号有优先权。如果我们现在要计算的表达式是像2+3/2这样稍微复杂一点的计算表达式，如果我们简单的从左到右分解操作数和运算符号，那么就会有很多复杂的计算判断。因此，我们有一个计算上更友好的后缀表达式。什么是后缀表达式：后缀表达式是指运算符号在要运算的两个数之后。以上两种我们日常生活中常见的算术表达式也称为中缀表达式。我们将中缀表达式2+3/2转换为后缀表达式，得到232/+。第一次面对这个后缀表达式肯定会觉得陌生，但是如果我们知道这个表达式是如何工作的，我们也就知道为什么后缀表达式更适合计算机计算了。如何通过后缀表达式计算：对于232/+这个后缀表达式。我们从左向右遍历，如果得到一个操作数，就找“地方”存放。如果是运算符，就去存储的地方找到输入的两个操作数，然后进行计算，然后继续存储结果。重复这个过程，直到循环结束，最终我们会得到最终的结果。下图1.1给出了后缀表达式的运算过程。存储结构最上面是当前循环的操作数，存储结构显示的是本次循环后存储结构的结果：图1.1后缀表达式的运算过程，可以看出我们使用了一种特殊的存储方式。进入存储结构的元素首先从存储结构中出来。这种存储数据的结构就是栈。栈的特点是先进后出，每次从栈中推出的元素都是最后进入的元素。栈常用于计算机计算过程中。在我的理解中，如果我们在计算过程中需要记录之前的结果，以后再用的话，那么这时候我们都可以使用栈。比如我们常用的递归，其实就是用栈来存储“上一个结果”。C1python中栈的简单实现："""实现最简单的栈，我们基本上只需要实现两个方法，一个是栈的push方法，将元素压入栈中。另一个是pop方法，即压栈的元素最后一个元素压出并返回那个元素"""classStack:#不要让类变量成为可变对象#values=[]def__init__(self):self.values=[]def__getitem__(self,item):返回self.values.__getitem__(item)defpush(self,value):self.values.append(value)defpop(self):returnself.values.pop()def__len__(self):returnlen(self.values)如何把中缀表达式变成后缀表达式：首先，我们还是循环中缀表达式。这个时候我们不关心数字，所以遇到数字就直接输出数字。当我们遇到一个算子的时候，首先要将这个算子和栈中已有的算子进行比较，因为我们在计算的时候会先计算出优先级高的算子，所以我们要输出栈中优先级比它高的算子当前循环到的运算符，然后将当前运算符压入堆栈。当然，还有一个特殊的运算符号就是“()”括号。这个时候我们就得专门处理一下。如果是“(”，我们就直接入栈，如果遇到“)”，就入栈。("后面的所有运算符都从堆栈中弹出。最后，如果循环结束，这时候我们要把栈中剩余的算子全部弹出出栈。C2python中中缀表达式转后缀的简单实现："""只是一个简单的实现，没有考虑中缀表达式中的浮点数，只简单处理"*"、"/"、"+"等符号,"-","(",")""""defconvert_the_infix_expression_to_suffix_expression(infix_expression:str)->list:""":paraminfix_expression::return:Usage::>>>convert_the_infix_expression_to_suffix_expression("3+2/4")[3,2,4,"/","+"]"""res=[]operator_stack=Stack()#存储符号的行列operator_ranks={"*":2,"/":2,"+":1,"-":1,"(":0,")":0}foroperatorininfix_expression:ifoperator.isdigit():#数字直接存入res.append(int(operator))else:#运算符必须和栈中的比较stack()whileoperator_stackandoperator_stack[-1]!="(":res.append(operator_stack.pop())#将“(”抛出operator_stack.pop()elifoperator.isspace():continueelse:#抛出栈中所有优先级>=当前的operator#然后把当前的operators加入whileoperator_stackandoperator_ranks[operator_stack[-1]]>=operator_ranks[operator]:res.append(operator_stack.pop())operator_stack.push(operator)#将符号栈中的所有符号抛出whileoperator_stack:res.append(operator_stack.pop())returnres总结：通过上面的学习，我们也可以理解中缀表达式，后缀表达式，栈，以及面试中会问到的infix-to-suffixConversionReferenceMooc-DataStructure
