这是以下两个数据结构学习视频的支持文档：
（5）堆栈应用：表达式求值预览
（9）堆栈应用：表达式求值说明
请同学们先阅读文档再学习视频效果更好。（请用电脑查看此文档）
一、表达式求值的规则
表达式求值是程序设计语言编译中的一个基本问题。它的实现就是对“栈”的典型应用。
首先了解算术四则运算的运算规则：
（1）先乘除，后加减。
（2）从左到右计算
（3）先算括号内，再算括号外
因此，下面这个算数表达式的计算顺序应为：
4 + 2 * 3 – 10 / 5
= 4 + 6 – 10 / 5
= 10 – 10 / 5
= 10 – 2
= 8
任何一个表达式都由操作数（operand）、运算符（operator）和界定符组成：
①操作数即可以是常量，也可以是被说明为变量或常量的标识符。
②运算符可以分为算术运算，关系运算和逻辑运算符。
③界定符有左右括号和结束符等。
为了叙述的简洁，我们仅讨论简单算数表达式的求值问题，这种表达式只包含加、减、乘、除等四种算术运算。需要时，不难把它推广到更一般的表达式上。
二、运算符优先级
对于两个相继出现的操作符θ1和θ2 有三种关系：
θ1 <θ2 θ1的优先级低于θ2
θ1 =θ2 θ1的优先级等于θ2
θ1 >θ2 θ1的优先级高于θ2
由此可以列出“+-*/”之间的优先级。如下图（见图1）
通过图可以看出：加减乘除优先性都低于“（”但是高于“）”，由运算从左到右可知，当θ1=θ2 ，令θ1>θ2；
为了算法简洁，在表达式的左边和右边虚设一个“#”，这一对“#”表示一个表达式求值完成。
“（”=“）”当一对括号相遇时表示括号内已运算完成。
“）”和“（”、“#”和“(”、“(”和“#”无法相继出现，如果出现则表达式出现语法错误。(实现时，可以用0存储)
这个表如何理解呢？例如：a+b+c，这里有两个运算符，运算符θ1 为+，运算符θ2 也为+ ，查上表，得到“>”的关系，那么意味着先计算前面的+号，也就是先算a+b，得到结果后，再考虑算后面的表达式。
三、算法思路
为实现优先算法，可以使用两个工作栈，一个是OPTR，用于寄存运算符，一个是OPND，用于寄存操作数和运算结果。算法的基本思想是：
（1） 首先置操作数栈为空栈，表达式起始符’#’为栈底元素。
（2）依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先级作相应操作，直至整个表达式求值完毕（OPTR栈顶元素和当前读入的字符均为’#’）
算数表达式求值的运算符优先算法。假定输入的表达式语法正确，以’#’做结束符。使用OPTR和OPND分别作为运算符栈和操作数栈。
expression函数的算法逻辑如下。以下是伪代码，需要用真实的代码代替：
setNull(OPTR);
push(OPTR, ‘#’); //将’#’压入操作符OPTR栈
setNull(OPND);
读入字符ch;
do{
if (ch IN op) //op为运算符的集合
swith( precede(top(OPTR),ch ) { //比较栈顶元素和ch的优先关系
case ‘<‘:
push(OPTR,ch); //栈顶元素优先级低，则压入操作符栈
读入字符ch;
break;
case ‘=’:
if (ch==’)’)
x = pop(OPTR); //自己思考什么情况需要这个判断
读入字符ch;
break;
case ‘>’://栈顶元素优先级高，取出一个运算符，两个操作数，并计算
theta = pop(OPTR);
b = pop(0PND);
a = pop(OPND);
push(OPND,operate(a, theta, b));//将计算结果压入操作数栈
}
else{ //op为操作数的集合
push(OPND,ch);
读入字符ch;
}
}while (( ch != ‘#’) OR ( top(OPTR) != ‘#’))
return top(OPND);
算法中调用了两个函数，precede是判断运算符栈的栈顶运算符与读入的运算符之间的优先关系；
operate作一元运算：a θ b，算出运算结果，例如调用operate(‘1‘, ‘+‘, ‘5‘);算出结果6。
四、编程需要思考的几个问题
1.优先级表如何存储并查找？（precede函数）
2.如何判断输入的字符是数字还是运算符？（isOpnd，isOptr函数）
3.根据举例手动跟踪代码，看看能否理解栈的变化情况。
4.如何实现operate函数？
5.目前的算法是在假定表达式正确的情况下进行的，要求大家先这样假定，（1）只对1位整数进行四则运算，采用跟踪调试的方法检验程序的运行。当程序运行正确后，再根据自己的能力情况考虑增加：（2）是否要对空格过滤？（3）是否要对多位整数进行运算？（4）是否需要检查表达式格式是否正确？按照提示的（2）（3）（4）顺序逐步增加功能，每增加一个检查后，用多个范例验证过关后，再进入下一个步骤，不要一次把所有的检查功能都加上去，这样会增加调试难度。
即使只完成（1）的功能也算程序完成，但一定要做到能够想明白程序是如何执行的，堆栈是如何变化的。
五、测试范例
说明：蓝色字体表示输入，黑色字体是说明，不是运行结果的一部分。基本要求完成（1）的效果，如果完全正确完成（1）可以评90。后续其他范例可选，还有其他范例，可以自己思考和检查。
（1）1位整数的表达式
请输入一个正整数表达式（可以输入的字符包括+-*/()#0123456789）：
2+3*4*(5-2)+6#
计算结果是：44
（2）包含空格
请输入一个正整数表达式（可以输入的字符包括+-*/()#0123456789）：
2 +3 *9 #
计算结果是：29
（3）识别多位整数
请输入一个正整数表达式（可以输入的字符包括+-*/()#0123456789）：
23*(2+5)+62/3#
计算结果是：181.667
（4）数字中包含空格
请输入一个正整数表达式（可以输入的字符包括+-*/()#0123456789）：
23 *4 5+2#
计算结果是：1037
（5）检查表达式格式是否正确
请输入一个正整数表达式（可以输入的字符包括+-*/()#0123456789）：
@345+6#
输入错误，请输入一个正确的表达式（可以输入的字符包括+-*/()#0123456789）。
计算结果是：-1
（6）检查表达式格式是否正确
请输入一个正整数表达式（可以输入的字符包括+-*/()#0123456789）：
#34/3#
输入错误，表达式前面不能以#开头。
计算结果是：-1
参考文献：
[1]严蔚敏.数据结构(C语言版)[M].清华大学出版社，北京：2019