二叉树表示运算符优先级算法思想实例代码执行屏幕快照，其中骑马订表达式已转换为后缀堆栈，表达式已应用于表达式评估
堆栈在公式评估中的应用
表达式评价是编程语言编译中最基本的问题，它的实现是堆栈APP应用的典型例子。 骑马订公式不仅依赖于运算符的优先顺序，还包括括号的处理。 后缀表达式运算符位于操作数之后，后缀表达式考虑了运算符的优先级。 没有括号，只有操作数和运算符。
的二叉树表达式也可以用二叉树的形式表示。 在这种情况下，操作数都是二叉树的叶节点，运算符节点决定该叶节点的运算。 运算符左边的操作数位于运算符节点左边的子树中，运算符右边的操作数位于运算符节点右边的子树中。 根节点是表达式中优先级最低的运算符。 从式AB*(C-D )-E/F对应的二叉树可见，骑马订式和二叉树的中序扫描相同，后缀式和二叉树的后序扫描具有异质特征。
运算符优先级icp表示当前扫描的运算符op在推送前的优先级，isp表示运算符op在推送后的优先级。 其中，“#”是初始标志。
运算符# ()、//- ) isp01536icp06421算法思想从左到右扫描一次编写公式：
如果检测到操作数，并且检测到将操作数直接输出到后缀表达式的运算符，则将当前运算符的icp优先级与堆栈顶运算符的isp优先级进行比较
a .堆栈顶部运算符的isp优先级对于当前运算符icp优先级，请将堆栈顶部运算符输出到后缀表达式以提取堆栈，重复此步骤直到不满足步骤条件，然后继续执行下一步。
b .堆栈顶部运算符的isp优先级当前运算符icp优先级，如果当前运算符进入堆栈并执行以下步骤：
c .堆栈顶部运算符的isp优先级对于当前运算符icp优先级，堆栈顶部运算符直接输出到堆栈，而不输出到后缀表达式。 (表示此运算符为“(”或“)”)如果在骑马订表达式扫描完成后堆栈不为空，则将堆栈中除“#”之外的所有运算符输出为后缀表达式。 实例aB*(c-d )-E/F
扫描步骤项目类型动作堆栈中的元素输出0’#‘堆栈，读取下一个符号#1A操作数直接输出#A2运算符ISP’’#’) ICP’，堆栈# 3B操作数为# B4*运算(6c操作数为直接#*(C7-运算符ISP )’(ICP ) ) -’)、堆栈#*(-8d操作数为直接#*(-D9 )运算符ISP )’-’() )、堆栈输出堆栈#-14E操作数是#-E15/运算符ISP ) ) )/)/)/) 65代码/* * * * * * * * * * * * * author 330 if(op=='# ' ) {优先级=0； }elseif(op==' () ) {priority=1； }elseif(op==' () ) {priority=6； }elseif(op==''|op=='-' ) {priority=3； }elseif(op=='*'|op=='/' ) {priority=5； }返回优先级； //堆栈外优先级intICP(charop ) {int priority； if(op=='# ' ) {优先级=0； }elseif(op==' () ) {priority=6； }elseif(op==' () ) {priority=1； }elseif(op==''|op=='-' ) {priority=2； }elseif(op=='*'|op=='/' ) {priority=4； }返回优先级； }voidtrans(stringmid_str，string last_str ) {stackchar s； //开始s.push('# ' )； cout '堆栈：#'endl； for(intI=0； imid_str.size (； I ) if(mid_str[I]='a'mid_str[I]='z ' ) {last_str=mid_str[i]； cout '直接输出：“mid_str[i]endl； }else{intop_ISP=ISP(mid_str[I]； intop_ICP=ICP(mid_str[I]； if(ISP(s.top ) ) op_icp (while ) ISP (s.top ) ) op _ ICP！ s.empty () {last_str=s.top； cout '推回输出： ' s.top () endl； s.pop (； }if(ISP(s.top ) ) op_icp ) s.push ) mid_str[I]； cout'instack:「mid_str[I]endl； (if ) ISP (s.top ) )==op_icp ) {cout (直接退出堆栈) s.top ) ) endl； s.pop (； }}}while (！ s.empty () ) if ) s.top )！='# ' ) {last_str=s.top (； cout '推回输出： ' s.top () endl； s.pop (； (else ) cout (直接退出堆栈) s.top ) ) endl； s.pop (； }}intmain(int ) {string mid_str； string last_str； cout '请输入骑马订格式。' endl； cinmid_str； trans(mid_str，last_str )； cout '后缀表达式为' last_strendl； 返回0； }执行屏幕截图