骑马订式后缀式参考的文章直接给出了算法，但算法是如何推导的还不清楚。 简单地写下我自己的理解，勉强说明。
后缀表达式跟在操作符的再次操作数之后，计算机可以按照简单的优先顺序进行运算。 前面我们讨论了手动转换骑马订表达式的情况，但是首先必须按照计算顺序完全添加括号来创建大括号表达式。 像() a b ) ) c )那样向外侧移动。 最终结果为ab c*，可见操作数的相对位置没有变化。 操作员只是跳出了这一层括号。 因此，对于操作数，可以直接按原来的顺序排出。 对于操作数，请先保存(当然也保存括号)，如果遇到右括号，则提取前一个操作数并将其放在当前操作数之后。 这相当于将操作员跳出括号。
我们相遇是因为骑马订式，不是中括号式。 另外，当计算机转换为后缀表达式时，它不会丢失。 那么，不需要花括号式吗？ (有些骑马订公式不能删除。 因为要改变原来的优先顺序，所以只能在不改变原来意思的基础上删除括号)
其实不用转换成全括号式。 最外面的括号可以不加。 最后一次扫描结束后，只需取出当前剩下的保存的操作符并放在操作数后面即可。
中括号呢？ (a b c ) )如果是d呢？ 其全括号式为((a b ) c ) d )，除去最外层的括号为(a b ) c ) ) d，确认是否可以去除a b的括号。 之后除(a b c ) ) d外，按上述步骤进行转换。 即，a b cD )显然这是错误的(但是，后缀式的评价结果是正确的，但由于无法逆算为中继式所以是错误的)，正确答案是a b cD )，很明显，ABC的中间也有“优先顺序” 反过来看结果，a和b的加号比c的加号早一步出现。 实际上，公式遇到c的加号时会出来(因为如果没有出来，下次遇到c的时候，c一定会出来)。 在那里想想。 c的加号应该没有a和b的加号那么高，所以a和b的加号不需要等到右括号就提前出来，保存当前的操作符。
用一个例子验证一下(a*b c ) d )。 毫无疑问，首先遵循第一个说法，即abc* d*。 而且根据上一步的变换，ab*c d*会发现这种情况是正确的。 应该认为前面步骤的假设是正确的。
那么，叫(a b*c ) d怎么样呢？ 按照最初的说法，就是abc *d*。 这个结果明显是错误的。 *号码优先于号码，遇到*时，可以不输出号码，但*号码必须先保存。 提取运算符的顺序是什么样的？ *的优先顺序较高，括号内的读取结束时，必须*先进行。 可以想象，当前操作符保存时，只有当前操作符的优先级高于已保存操作符的优先级时才保存，否则检索后再保存(请参阅上一步优化)。 因此，存储的操作符的顺序优先级越来越高。 越晚读取，越容易遇到最近的操作员，最近的操作员的优先顺序最高，因此在取操作员时可以判断为相反顺序。 因此，它可以在堆栈中实现，因此可以验证括号表达式，结果应该是abc* d*。 这进一步验证了上述优化是正确的。
总之，程序是指无需转换为括号表达式就可以直接转换骑马订表达式。 遇到数字就直接写。
遇到原来的左括号就保存。
遇到运算符时，首先将已存储的运算符与优先级进行比较，如果高于现有优先级则存储(堆栈)，如果低于原运算符的优先级则取出原运算符(堆栈弹出)，将当前运算符与新堆栈顶部进行优先级比较，当前运算符与
遇到方括号时取出堆栈中的所有操作员。
加载完成后，取出堆栈中的其余操作员。 结束了
基本上是这一步。 代码如下。 dfinfixtopostfix(infixexpr ) :
#公式中的各个元素由空格分隔，便于以后的分割判断
#定义优先级
prec={}
prec['*']=3
prec['/']=3
prec[' ']=2
prec['-']=2
prec [ ' (' )=1
op堆栈=堆栈(#用于保存操作符
postfixList=[]#用于存储临时转换结果
tokenList=infixexpr.split (
fortokenintokenList:
#为了展示通用性，这里用字母表示一般公式
#判断一般元素
iftokenin ' abcdefghijklmnopqrrstuvwxyz ' ortokenin ' 0123456789 ' :
postfixList.append(token )
#判断左括号
eliftoken=='(':
opstack.push(Token ) )。
#打印(op stack.peek ) )
#判断右括号
eliftoken==' ) ' :
topToken=opStack.pop (
whiletopToken！='(':
postfix list.append (顶部令牌) )。
topToken=opStack.pop (
#判断操作员
else:
while(notopstack.isempty () and ) prec [ op stack.peek ] ]=prec [ token ] ) :
postfixlist.append(opstack.pop ) )
opstack.push(Token ) )。
#横移结束，最后取出所有操作员
whilenotopStack.isEmpty () :
postfixlist.append(opstack.pop ) )
return '.join (postfix列表) )。
作者： qq_42907161
链接： https://blog.csdn.net/QQ _ 42907161/article/details/108048932
来源： CSDN
版权属于作者。 转载请联系作者取得许可。 请不要擅自转载。