实验四 算术表达式求值
一、实验目的
帮助学生熟练掌握栈的基本操作，并通过用算符优先法对表达式求值的过程深刻领会用栈解决实际问题的基本方法。
二、实验内容
编写程序实现从键盘终端输入语法正确的算术表达式，计算出表达式的值。 为了避免算符的二义性，可以假设表达式中只包含实型正常数 运算符包括加、减、乘、除四种基本运算，可以包含圆括号。
三、实验仪器
微型计算机
实验用编程语言：Turbo C 2.0，Borland C 3.0等以上版本
四、实验原理
1、算术四则运算法则： 先乘除后加减 从左至右
先括号内后括号外
2、方法：对运算符建立优先关系矩阵，按优先关系对表达式进行处理。 算符：运算符和界符。
根据法则1：对于两个相邻运算符，乘除优先于加减。
根据法则2：乘除优先级相同，加减优先级相同。相邻两个同级运算符左优先。
根据法则3：“（”前面的运算符优先级低于“（”的优先级。“（”的优先级低于右边相邻算符。“）”左边的算符高于“）”的优先级。
由于“（”和“）”必须成对出现，令它们的优先性相同。
为了处理的方便，假设表达式以“＃”开始和结束，输入表达式的一般形式为：
#表达式#
如：
#5.3+4.2*(7.6+4.5)#
规定开始的“＃”的优先性低于所有其它算符，所有其它算符的优先性高于结束的“＃”。根据假设，表达式开始的“#”和结束的“#”必须成对出现，所以也令它们的优先性相同。
对于一个正确的表达式，“)”不可能与“（”相邻，“（”不可能与结束的“#”相邻，开始的“#”不可能与“）”相邻，它们之间没有优先性，程序应具有这种判断能力。
根据上面的讨论，可用表1所示的算符优先关系矩阵来描述算符之间的优先关系，其中，用“>”表示表达式中前一个算符的优先性高于后一个算符的优先性，用“<”表示表达式中前一个算符的优先性低于后一个算符的优先性，用“=”表示表达式中前一个算符的优
先性与后一个算符的优先性相同。若两个算符之间无优先性，用空白表示。
表1：算符优先关系矩阵
3、算符表示
+
- * / ( ) #
+ > > > > < > <
- > > > > < > <
* < < > > < > <
/ < < > > < > <
( < < < < <
) > > > < = >
# > > >
>
<
> =
为了使算符与优先关系矩阵的行列号对应，把表达式中可能有的算符放入一维数组中，可以用字符在一维数组中的下标作为字符的标识码。本计算中，算法表示如下：
＋ － * / ( ) + 0 1 2 3 4 5 6 即用0表示算符“＋”，用1表示算符“－”，等。 定义的字符数组为：
char a[]={'+','-','*','/','(',')','#'}; 4、优先关系矩阵的表示
大于关系用1表示 小于关系用－1表示 等于关系用0表示
若两个算符间不存在关系，则用一个特定的数值表示，如用整数的上限值32767表示，可定义一个宏常量来表示：
#define NO 32767 则其优先关系矩阵为：
int PriorityTable[7][7]={{ 1, 1,-1,-1,-1, 1, 1 }, { 1, 1,-1,-1,-1, 1, 1 },
{ 1, 1, 1, 1,-1, 1, 1 },
{ 1, 1, 1, 1,-1, 1, 1 },
{-1,-1,-1,-1,-1, 0, NO}, { 1, 1, 1, 1,NO, 1, 1 }, {-1,-1,-1,-1,-1,NO, 0 }
};
5、算术表达式求值算法的实现原理
处理过程：
设置两个栈：操作数栈OPND和运算符栈OPTR。
1、首先置操作数栈为空栈，把“#”移进运算符栈（实际放入栈中的是字符“#”在
字符数组中的下标，对其它算符也是一样）。
2、从左至右扫描表达式，凡遇到操作数一律进OPND栈；若遇到运算符，则把栈顶
运算符与扫描运算符的优先数进行比较：若
-1：扫描运算符进OPTR栈
0： 若“（”和“）”，栈顶符号出栈；若为#，运算结束。
1： 取OPND栈顶操作数与OPTR栈顶算符进行运算，参与运算的操作数和
运算符出栈，运算结果进OPND栈
NO:表示表达式有错。
若表达式处理完，OPTR栈为#，OPND栈中只剩一项，表示表达式的运算结果，则分析成功。若达不到这种状态，表明表达式有错。
五、实现
1、数据存储结构
假设一个表达式不可能很长，如不超过屏幕上一行的宽度（80个字符），在对表达式处理之前先把表达式放入一个一维字符数组中，用户可以不输入表达式前后的“#”，由处理程序自动加入。
由于表达式的长度有限，运算符栈和操作数栈的长度野优先，假定不超过20，所以都采用顺序存储结构比较合适。用C语言可定义如下：
#define EXPLENGT 100 #define STACKSIZE 20 char expr[EXPLENGT];
int OPTR[STACKSIZE]; //运算符栈，元素为运算符对应的整数编码 double OPND[STACKSIZE]； //操作数栈，元素为表达式中的运算数据 2、运算符宏定义
为了判断运算符的方便，增强程序的可读性，定义如下宏常量：
#define PLUS 0 //运算符+ #define MINUS 1 //运算符- #define POWER 2 //运算符* #define DIVIDE 3 //运算符/ #define LEFTP 4 //运算符( #define RIGHP 5 //运算符） #define STARTEND 6 //运算符# #define DIGIT 7 //数字字符 #define POINT 8 //小数点
3、基本功能
(1) 输入算术表达式 (2) 计算表达式的值 4、辅助功能
（1）菜单选择
（2）获取字符类型编码 5、程序结构
该程序由5个函数组成，其中主函数1个，基本功能函数2个，辅助功能函数2个。函数间的调用关系图1所示。
图1 程序结构图 6、函数说明
（1）主函数main
功能：根据菜单选择确定要操作的内容： 表达式输入 表达式计算 计算结果输出 退出系统
（2）菜单选择函数：menu
功能：构造功能菜单，并选择下一步要操作的功能。 格式： int menu(void) 参数：无参数。
返回值：1～4中的一个序号。 可供选择的功能如下：
1--input expression 表示输入表达式
2--calculation expression 表示计算表达式 3--print result 表示输出计算结果
4--Quit 表示退出系统，结束程序的运行
（3）表达式输入函数：InputExpression
功能：输入表达式，并在表达式前后加上符号“＃” 格式：void InputExpression(char str[])
GetCharType nemu InputExpression excute main
