[数据结构与算法]用栈数据结构对算数表达式求值的思想

• 问题描述

????????表达式求值是程序设计语言编译中的一个基本问题，是栈应用的一个典型例子。对于一个简单的算数表达式，假如它的操作数是整型常数，运算符有加减乘除四种运算符，界限符有左右括号、表达式起始符和表达式结束符（#）。那么，它应遵循算数四则运算的规则是：从左到右，先括号内，后括号外，先乘除后加减。

• 算法分析

? ? ? ? 要对一个算数表达式求值，首先要了解算符（运算符和界限符）间的优先关系，即算数表达式的计算顺序，从而决定如何对表达式进行操作。对算数表达式进行扫描，任意两个相继出现的算符θ?和θ?之间的优先关系比较如表所示。

第一行表示θ?，第一列表示θ?，“-”表示此情况不存在

? ? ? ? 由表可知，θ?和θ?之间存在以下三种关系：

1. ???????θ??> θ? ：θ? 的优先级高于 θ? ，应执行θ? 对应的运算；
2. ? ? ? ?θ? < θ? :? θ? 的优先级低于?θ? ，不执行任何运算，继续扫描下一运算符；
3. ? ? ? ?θ? = θ? :? θ? 的优先级等于 θ? ，两者为左右括号或同为#。

????????要实现以上算符优先算法需使用两个栈，一个称作运算符栈（OPTR），用于存放运算符；另一个称作操作数栈（OPND），用于存放操作数或运算结果。算法的基本思想是：

1. 初始化OPTR和OPND两个栈，并将表达式起始符“#”作为OPTR栈的栈底元素。
2. 依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符，则与OPTR栈的栈顶元素进行优先级比较，并执行相应的操作：

• 若栈顶运算符的优先级低于刚读入的运算符（θ?<θ?），则刚读入的运算符进OPTR栈；
• 若栈顶运算符的优先级与刚读入的运算符优先级相同（θ?=θ?），说明左右括号相遇，即将栈顶运算符（左括号）出栈；
• 若栈顶运算符的优先级高于刚读入的运算符（θ?>θ?），则将栈顶运算符出栈送入θ，同时OPND栈弹出两个操作数a和b，对a和b执行θ运算并使运算结果进OPND栈。

? ?3. 当OPND栈的栈顶元素和当前读入字符均为“#”，整个表达式求值完毕，OPND栈的栈顶元素即为表达结果。

? ? ? ? 利用栈实现算数表达式 2*(35-10)+5 的过程如下表所示。