算术表达式求值问题z-数据结构与算法课程设计报告

合肥学院

计算机科学与技术系

课程设计报告

2009～2010学年第二学期

课学学专指

业导

班教生

姓

程 数据结构与算法

算术表达式求值问题

杨松 0804012031 08计科(2) 王昆仑 张贯虹

名 号 级 师

课程设计名称

2010年6月

1

题目：（算术表达式求值问题）一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。要求：（1）从键盘读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。选作内容：操作数类型扩充到实数。

一、问题分析和任务定义

要对一个含有加减乘除四则运算的合法的算术表达式进行求值， ①首先，应了解算术表达式的四则运算的规则： (1)从左向右计算 (2)先乘除，后加减 (3)先括号内，后括号外

由此可知，比如算术表达式（7+15）*（23-28/4）的计算顺序，即为 （7+15）*（23-28/4）=22*（23-28/4）=22*（23-7）=22*16=352 ②其次，应明确“算符优先法”的内容：

算符优先法就是根据上述四则运算规则确定的优先关系来实现对表达式的编译或解释执行的。

一个简单的四则运算表达式由操作数（operand）、运算符（operator）和界限符（delimiter）组成，其中操作数是正整数，运算符只含加、减、乘、除四种，界限符有左右括号和表达式起始、结束符“#”；而且，为了统一算法的描述，将运算符和界限符通称为算符。算符集OP=｛+，-，*，/，（，），#｝。

根据上述3条运算规则，在具体的运算的每一步中，任意两个相继出现的算符θ1和θ2

之间的优先关系只能是如下3中关系之一：

θ1<θ2 θ1的优先级低于θ2 θ1=θ2 θ1的优先级等于θ2 θ1>θ2 θ1的优先级高于θ2

下表定义了算符之间的这种优先关系。

表1 算符之间的优先关系

θ1 θ2 + - * / （ ） # + > > > > < > < - > > > > < > < * < < > > < > < / < < > > < > < （ < < < < < < ） > > > > = > # > > > > > = 表格说明：

1、θ1 、θ2 同“*”、“/”或同为“+”、“-”，则算符θ1的优先级高于θ2 2、θ1为“*”、“/”的优先级高于θ1为“+”、“-” 3、θ1为“+”、“-”、“*”、“/”的优先级高于θ2为“）” 4、θ1为“（”的优先级低于θ2为“+”、“-”、“*”、“/” 5、θ1、θ2同为“（”，θ1的优先级低于θ2；θ1、θ2同为“（”，θ1的优先级高于θ2 6、θ1为“（”且θ2为“）”，或者，θ1、θ2同为“#”，则θ1、θ2的优先级相同

2

7、θ1为“）”、θ2为“（”，或者，θ1为“#”θ2为“）”，或者θ1为“（”θ2为“#”，这3中情况各自之间无优先关系，表示为“ ”，因为表达式中不允许它们相继出现，如果出现，则可以认为出现语法错误。 ③最后，确定算法的基本思想：

设置两个工作栈，一个为OPTR栈，存放运算符；另一个为OPND栈，存放操作数或运算结果。则算法的基本思想描述如下：

(1)首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；

(2)依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先级后，做如下相应操作：

①若栈顶算符θ1的优先级低于刚读入的算符θ2，则将θ2入算符栈OPTR ②若栈顶算符θ1的优先级高于刚读入的算符θ2，则将让θ2出栈；同时，将操作数栈OPND退栈两次，得到两个操作数x、y，对x、y运用θ2进行运算后，再将运算结果如操作数只栈OPND

③若栈顶算符算符θ1的优先级等于刚读入的算符θ2，说明左右括号相遇，或者是表达式的起始、结束符相遇，只需将栈顶算符（左括号或起始符）退栈即可；当算符栈OPTR栈空时，算法结束。

二、数据结构的选择和概要设计 数据结构的选择：

本程序采用顺序存储结构存储两个栈，即操作数栈（OPND）和算符栈（OPTR）； 概要设计如下：

运算符栈的相关功能函数

操作数栈的相关功能函数

算术表达式的相关功能函数 主函数

表2 运算符栈的功能函数

OPTR栈 int OPTR_InitStack(OPTR_STACK &s) char OPTR_GetTop(OPTR_STACK &s) int OPTR_Push(OPTR_STACK &s, char e) int OPTR_Pop(OPTR_STACK &s, char &e)

表3 操作数栈的功能函数

算符栈的初始化 获取算符栈的栈顶元素 算符栈的栈顶插入新的数据元素 算符栈的栈顶元素出栈 OPND栈 int OPND_InitStack(OPND _STACK &s) double OPND_GetTop(OPND _STACK &s) int OPND_Push(OPND_STACK &s, double e) int OPND_Pop(OPND_STACK &s, double &e) 操作数栈的初始化 获取操作数栈的栈顶元素 操作数栈的栈顶插入新的数据元素 操作数栈的栈顶元素出栈 表4 算术表达式的相关功能函数

double Operate( double a, char theta, double b) int In(char Test, char * TestOp) int ReturnOpOrd(char op, char* TestOp)

3

两个操作数之间的四则运算函数 算符的判断函数 返回该算符在算符数组中的位置的函数 char Precede(char Aop, char Bop) double EvaluateExpression(char * MyExpression)

两个算符的优先级的判断函数 表达式的正确性判断函数，同时计算表达式 三、详细设计和编码

首先本程序定义两个顺序栈：算符栈（OPTR）和操作数栈（OPND）； OPTR栈定义如下： typedef struct{

char * base; //算符栈的栈底 char * top; //算符栈的栈顶 int stacksize; //算符栈的最大长度 }OPTR_STACK; OPND栈定义如下： typedef struct{

double * base; //操作数栈的栈底 double * top; //操作数栈的栈顶 int stacksize; //操作数栈的最大长度 }OPND_STACK;

然后是算符栈和操作数栈的相关功能函数的详细设计： （1）算符栈的相关功能函数的详细设计如下： 1、int OPTR_InitStack(OPTR_STACK &s)

为OPTR栈申请char类型的初始空间STACK_INITSIZE=100个 操作结果：构造一个空栈S，最大长度s.stacksize为100； 2、char OPTR_GetTop(OPTR_STACK &s)

初始条件：OPTR栈S已存在且非空（s.top!=s.base） 操作结果：用e= *(s.top-1)返回S的栈顶元素 3、int OPTR_Push(OPTR_STACK &s,char e) 初始条件：OPTR栈S已存在

因为考虑到原先申请的空间可能不够，即当OPTR栈的长度已经大于s.stacksize=100，这是需要申请额外的存储空间；每次均用realloc函数申请char类型的额外的STACKINCREMENT=10个存储单元，申请额外空间后的OPTR栈的最大长度s.stacksize增加10；

操作结果：插入元素ｅ为新的OPTR栈顶元素，即*s.top++=e； 4、int OPTR_Pop(OPTR_STACK &s,char &e) 初始条件：OPTR栈S已存在且非空；

操作结果：OPTR栈顶元素出栈，同时用e保存该栈顶元素，即e=*--s.top；

（2）操作数栈的相关功能函数的详细设计如下： 1、int OPND_InitStack(OPND_STACK &s)

为OPTR栈申请double类型的初始空间STACK_INITSIZE=100个 操作结果：构造一个空栈S，最大长度s.stacksize为100； 2、double OPND_GetTop(OPND_STACK &s)

初始条件：OPND栈S已存在且非空（s.top!=s.base） 操作结果：用e= *(s.top-1)返回S的栈顶元素 3、int OPND_Push(OPND_STACK &s,double e)

4

初始条件：OPND栈S已存在

因为考虑到原先申请的空间可能不够，即当OPND栈的长度已经大于s.stacksize=100，这是需要申请额外的存储空间；每次均用realloc函数申请double类型的额外的STACKINCREMENT=10个存储单元，申请额外空间后的OPND栈的最大长度s.stacksize增加10；

操作结果：插入元素ｅ为新的OPND栈顶元素，即*s.top++=e； 4、int OPND_Pop(OPND_STACK &s,double &e) 初始条件：OPND栈S已存在且非空；

操作结果：OPND栈顶元素出栈，同时用e保存该栈顶元素，即e=*--s.top；

（3）下面实现本课程设计目标的算术表达式的相关功能函数的详细设计过程：

首先应定义7种算符的字符数组char OPSET[OPSETSIZE]={'+' , '-' , '*' , '/' ,'(' , ')' , '#'}; 然后是7算符的的优先级的定义：

char Prior[7][7] = { '>' , '>' , '<' , '<' , '<' , '>' , '>', '>' , '>' , '<' , '<' , '<' , '>' , '>', '>' , '>' , '>' , '>' , '<' , '>' , '>', '>' , '>' , '>' , '>' , '<' , '>' , '>', '<' , '<' , '<' , '<' , '<' , '=' , ' ', '>' , '>' , '>' , '>' , ' ' , '>' , '>', '<' , '<' , '<' , '<' , '<' , ' ' , '='

};

因为算术表达式涉及到两个数的四则运算，所以要设计一个两个数四则运算的函数，即函数double Operate( double a, char theta, double b)，定义了两个数的(加)+、(减)-、(乘)*、(除)/ 四种运算，并返回两个数的运算结果。

然后，当依次读入算术表达式的各个字符时，要同时判断字符的合法性，包括算符的合法性和操作数的合法性，所以应设计算符合法性的判断函数，即int In(char Test, char * TestOp)，将依次读入的字符与算符数组中的所有算符依次比较，若算符合法，则返回该算符在算符数组中的位置m，若算符不合法，则均返回0。

在判断算符的合法性之后，则应该对相邻的两个算符的优先级进行比较，以便于算术表达式的相关运算，所以应设计函数char Precede(char Aop, char Bop)比较两个算符Aop和Bop的优先级，返回值即为两个算符对应在算符优先级二维数组Prior[7][7]中的值。

经过上述两个步骤，确定了的算符的合法性与否以及两个算符的优先级，然后即要判断算术表达式的合法性与否，并同时对该算术表达式进行一系列的计算，设计函数double EvaluateExpression (char * MyExpression)。

该函数需要的所有变量为：OPTR，为算符栈；OPND，为操作数栈；TempData[40]，为辅助字符数组，其中所有的字符均为满足合法性的算术表达式的操作数；theta，为算符；a，b，为运算的两个操作数；Data，为两个数的运算结果；c，为当前读入的字符；Dr[2]，为当前读入的字符和结束符’\\0’构成的字符串；其中变量TempData[40]和Dr[2]是因为考虑到操作数有可能不止一位数，则Dr[2]起到字符衔接的作用，只要读入的字符是操作数，就将该字符衔接到字符数组TempData[40]中，则TempData[40]中除了结束符’\\0’之外的所有字符就是算术表达式中的一个完整的操作数，即TempData[40]中存放的操作数或者是一位数，或者是多位数。

算术表达式的详细计算过程：

5

首先，将所需的变量初始化：初始化算符栈和操作数栈，OPTR_InitStack (OPTR)，OPND_InitStack (OPND)；将算术表达式的起始字符’#’入算符栈；变量c保存当前表达式MyExpression的地址；利用strcpy()函数将结束符’\\0’衔接至数组TempData[40]中。

然后，利用while循环，开始计算。当OPTR栈的栈顶元素OPTR_GetTop(OPTR)和当前读入的字符*c同时为’#’时，整个表达式求值完毕；若不满足表达式结束的该条件，则进行计算。读入当前字符*c：

若*c是操作数，则首先将*c给Dr[2]，利用strcat()函数将Dr[2]衔接至TempData[40]中，然后c++,判断下一个字符*c是否是算符，若不是，说明当前操作数是多位数，然后再将该操作数字符衔接至TempData[40]中，然后再c++，重复上述过程，将当前操作数的所有字符完整的保存至TempData[40]中，利用强制转换函数atof()将TempData[40]中的字符转换为double型的数据，同时赋给Data，则Data即为当前的完整的double型操作数（Data或为一位数，或为多位数），然后Data入操作数栈，即OPND_Push(OPND, Data)；

若*c是算符，则将*c与当前算符栈的栈顶元素进行优先级的比较，即Precede(OPTR_GetTop(OPTR), *c)；比较的结果若为’<，说明当前算符栈的栈顶算符的优先级低于比当前读入的字符*c的优先级，则将*c入栈，即OPTR_Push(OPTR, *c)，且c++；若比较结果为’=’，说明当前算符栈的栈顶算符的优先级等于比当前读入的字符*c的优先级，则将当前算符栈的栈顶算符出栈，即OPTR_Pop(OPTR, x)，且c++；若比较结果为’>’，说明当前算符栈的栈顶算符的优先级高于比当前读入的字符*c的优先级，则首先将当前算符栈的栈顶算符出栈，即OPTR_Pop(OPTR, theta)；然后，将当前操作数栈的栈顶操作数和次栈顶操作数依次出栈，即OPND_Pop(OPND, b)，OPND_Pop(OPND, a)，将该两个操作数a和b进行theta运算，将运算结果入操作数栈，即OPND_Push(OPND, Operate(a, theta, b))；

while循环重复上述两个过程，直至当前算符栈的栈顶元素OPTR_GetTop(OPTR)和当前读入的字符*c同时为’#’时，整个算术表达式的计算全过程结束。

四、上机调试

1、语法问题及解决

由于本程序牵扯到四个方面的内容，首先是OPTR栈的相关功能函数的设计；其次是OPND栈的相关功能函数的设计；再次是算术表达式的具体计算涉及到的相关功能函数的设计，最后是主函数的设计；前两个方面均为对顺序栈的基本操作，具有通用性，基本无语法错误；主要是在设计算术表达式的具体计算的函数时，调用相关栈的函数以及其它语句时，出现了语法编辑的错误，还有在设计主函数的时候，由于要考虑到用户的使用方便，也出现了一些编辑语法错误，在反复使用加注释和单步运行两种方法对于具体错误分析、调试后，所有语法错误均得到解决。

2、逻辑问题及解决 在编辑本程序时，一个最关键的方面就是在设计本程序的中心算法即算术表达式的具体计算函数EvaluateExpression(char * MyExpression)时，出现多处逻辑错误；其中最关键的两个问题就是，如何解决操作数是实数范围内的多位数处理问题，和读入的非法字符(包括非法算符和非法操作数)的处理问题；经反复思考和多次查阅资料，解决办法：一方面，利用在程序的详细设计过程中提到的TempData[40]和Dr[2]，将依次读入的字符满足操作数的条件时，就利用Dr[2]将该字符衔接至TempData[40]中，这样直到读入的字符是算符时，TempData[40]中存放的所有字符组成的字符串就是一个完整的操作数(或是实数范围内的一位数，或是实数范围内的多位数；或是实数范围内的整数，或是实数范围内的浮点数)，这样就解决了操作数是实数范围内的多位数处理问题；另一方面，利用强制转换函数atof()，将TempData[40]中所有字符构成的字符串强制转换为double型浮点数据，就将读入字符过

6

程中出现的非法字符(非法算符和非法操作数)全部转换为实数0.000，它们就不会影响到合法的数据，更不会影响到后继读入的字符的处理，这样就解决了读入的非法字符的处理问题。

3、时间、空间复杂度的分析

由于本程序的算法只涉及到2个循环语句，分别为：for (int i=0; i< OPSETSIZE; i++)，此循环语句是用于判断当前读入字符是否是算符的功能，OPSETSIZE=7，它的时间复杂度是O(OPSETSIZ)；while (*c!= '#' || OPTR_GetTop(OPTR)!= '#')，此循环语句是用于算术表达式的具体计算，它的时间复杂度取决于用户输入的算术表达式MyExpression的长度length，length=strlen（MyExpression），即该语句的时间复杂度为O(length)=O(strlen（MyExpression）)； 所以，本程序的算法的时间复杂度为O(OPSETSIZE+ strlen（MyExpression）)。

由于在本程序中，在为算符栈(OPTR)和操作数栈(OPND)涉及到两种情况时申请空间，一方面分别为OPTR栈和OPND栈申请了初始的存储单元，均为STACK_INITSIZE=100个；另一方面，考虑到两个栈在处理具体的算术表达式时，有可能会出现溢出的情况，即栈的初始的存储空间不够用，这时需要为其申请额外的存储空间，每溢出一次，就为其申请存储单元STACKINCREMENT=10个；所以，本程序的算法的空间复杂度一方面取决于算术表达式的长度，另一方面取决于本程序的所有代码所占用的存储空间大小。

五、测试结果及其分析

调试菜单：

第一组测试数据：2.34+11.456=13.796

7

该算术表达式为单纯的加法运算，参与运算的两个数据均为实数，算术表达式的结果为13.796，正确；而且算术表达式的具体计算过程即算符栈（OPTR）和操作数栈（OPND）的入栈和出栈的遍历过程均正确；

第二组测试数据：999.567-10.43=989.137

该算术表达式为单纯的减法运算，参与运算的两个数据均为实数，算术表达式的结果为989.137，正确；而且算术表达式的具体计算过程即算符栈（OPTR）和操作数栈（OPND）的入栈和出栈的遍历过程均正确；

第三组测试数据：23.24*34.5=801.780

该算术表达式为单纯的乘法运算，参与运算的两个数据均为实数，算术表达式的结果为801.780，正确；而且算术表达式的具体计算过程即算符栈（OPTR）和操作数栈（OPND）的入栈和出栈的遍历过程均正确；

8

第四组测试数据：1000.46/10.2=98.084

该算术表达式为单纯的除法运算，参与运算的两个数据均为实数，算术表达式的结果为98.084，正确；而且算术表达式的具体计算过程即算符栈（OPTR）和操作数栈（OPND）的入栈和出栈的遍历过程均正确；

第五组测试数据：1.21+(12.3/3-4)*2=-1.410

9

该算术表达式为加减乘除的复合运算，参与运算的所有数据均在实数范围内，算术表达式的结果为1.410，正确；而且算术表达式的具体计算过程即算符栈（OPTR）和操作数栈（OPND）的入栈和出栈的遍历过程均正确；

第六组测试数据：(7+15)*(23-28/4)=352

该算术表达式为加减乘除的复合运算，参与运算的所有数据均在实数范围内，并且均是正整数，算术表达式的结果为352.000，正确；而且算术表达式的具体计算过程即算符栈（OPTR）和操作数栈（OPND）的入栈和出栈的遍历过程均正确。

10

六、用户使用说明

1、本课程设计源代码重要语句均有相应的注释，用户可根据注释加以使用、阅读和理解；

2、本课程设计源程序适用于实数范围内double浮点型数据的四则运算，非常方便用户使用；

3、本课程设计考虑到了多种特殊情况的处理和意外错误的处理；同时在调试菜单过程中也进行了特殊处理，可便于用户参考，详细情况见“详细设计和编码”。

七、参考文献

[1] 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。 [2] 严蔚敏，吴伟民. 数据结构（C语言版）. 北京：清华大学出版社，2007年5月。

八、附录

#include #include #include

#define STACK_INITSIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配量 #define OPSETSIZE 7 //算符的长度

/********************算符栈的结构体**********************/ typedef struct{ char * base; //算符栈的栈底 char * top; //算符栈的栈顶 int stacksize; //算符栈的最大长度 }OPTR_STACK;

/********************操作数栈的结构体********************/ typedef struct{

double * base; //操作数栈的栈底 double * top; //操作数栈的栈顶 int stacksize; //操作数栈的最大长度 }OPND_STACK;

int OPTR_InitStack(OPTR_STACK &s){ // 算符栈的初始化函数

s.base=(char *)malloc(STACK_INITSIZE*sizeof(char)); // 算符栈分配初始的存储空间 if(!s.base) return 0; // 若申请存储空间失败，返回0 s.top=s.base; // 栈顶等于栈底，为空栈 s.stacksize=STACK_INITSIZE; // 算符栈的最大长度为100 return 1; }

char OPTR_GetTop(OPTR_STACK &s){ // 取算符栈顶元素函数 char e;

if(s.top==s.base) return 0; // 算符栈为空，返回0 e=*(s.top-1);

11

return e; // 返回算符栈顶元素 *(s.top-1) }

int OPTR_Push(OPTR_STACK &s,char e){ // 算符栈插入元素函数 if(s.top-s.base>=s.stacksize){

// 当栈的长度超过规定的最大长度s.stacksize时，需要申请额外的存储空间 s.base=(char *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char)); if(!s.base) return 0; // 若申请空间失败，则返回0 s.top=s.base+s.stacksize;

// 申请额外空间之前的栈顶位置s.top为s.base+s.stacksize s.stacksize+=STACKINCREMENT;

// 申请额外空间之后的栈的长度增加了STACKINCREMENT }

*s.top++=e; // 若栈的长度未超过规定的最大长度s.stacksize，将元素e入栈顶 return 1; }

int OPTR_Pop(OPTR_STACK &s,char &e){ // 算符栈顶元素出栈函数 if(s.top==s.base) return 0; // 若为空栈，返回0 e=*--s.top; // 不为空栈，将栈顶元素出栈 return 1; }

int OPND_InitStack(OPND_STACK &s){ // 操作数栈的初始化函数 s.base=(double *)malloc(STACK_INITSIZE*sizeof(double)); // 操作数栈分配初始的存储空间 if(!s.base) return 0; // 若申请存储空间失败，返回0 s.top=s.base; // 栈顶等于栈底，为空栈

s.stacksize=STACK_INITSIZE; // 操作数栈的最大长度为100 return 1; }

double OPND_GetTop(OPND_STACK &s){ // 取操作数栈顶元素函数 double e;

if(s.top==s.base) return 0; // 操作数栈为空，返回0 e=*(s.top-1); // 返回操作数栈顶元素 *(s.top-1) return e; }

int OPND_Push(OPND_STACK &s,double e){ // 操作数栈插入元素函数 if(s.top-s.base>=s.stacksize){

// 当栈的长度超过规定的最大长度s.stacksize时，需要申请额外的存储空间 s.base=(double *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(double)); if(!s.base) return 0; // 若申请空间失败，则返回0 s.top=s.base+s.stacksize;

// 申请额外空间之前的栈顶位置s.top为s.base+s.stacksize s.stacksize+=STACKINCREMENT;

// 申请额外空间之后的栈的长度增加了STACKINCREMENT }

12

*s.top++=e;

// 若栈的长度未超过规定的最大长度s.stacksize，将元素e入栈顶 return 1; }

int OPND_Pop(OPND_STACK &s,double &e){ // 操作数栈顶元素出栈函数 if(s.top==s.base) return 0; // 操作数栈为空，返回0 e=*--s.top; // 不为空栈，将栈顶元素出栈 return 1; }

//7种算符：'+' (加)，'-' (减)，'*' (乘)，'/' (除)，'(' (左括号)，')' (右括号)，'#' (结束符) char OPSET[OPSETSIZE]={'+' , '-' , '*' , '/' ,'(' , ')' , '#'}; //7种算符的算符优先级如下 char Prior[7][7] = {

'>' , '>' , '<' , '<' , '<' , '>' , '>', '>' , '>' , '<' , '<' , '<' , '>' , '>', '>' , '>' , '>' , '>' , '<' , '>' , '>', '>' , '>' , '>' , '>' , '<' , '>' , '>', '<' , '<' , '<' , '<' , '<' , '=' , ' ', '>' , '>' , '>' , '>' , ' ' , '>' , '>', '<' , '<' , '<' , '<' , '<' , ' ' , '=' };

double Operate( double a, char theta, double b){ // 两个数之间的四则运算函数 switch(theta){ // theta为运算符 case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/': return a/b; default : return 0; } }

int In(char Test, char * TestOp){ // 算符的判断函数 int m=0;

for (int i=0; i< OPSETSIZE; i++) // 将输入的字符与已知规定的算符比较 if (Test == TestOp[i]) m=1; return m; }

int ReturnOpOrd(char op, char* TestOp) { //返回该算符在算符数组中的位置的函数 int i;

for(i=0; i< OPSETSIZE; i++)

if(op == TestOp[i]) return i; return 0; }

char Precede(char Aop, char Bop){ // 两个算符的优先级的判断函数 return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];

13

}

double EvaluateExpression(char * MyExpression){ /* 表达式的正确性判断函数，同时计算表达式 */ OPTR_STACK OPTR; // OPTR为算符栈 OPND_STACK OPND; // OPND为操作数栈

char TempData[40]; // TempData[40]为辅助字符数组 double Data,a,b; // a和b为进行运算的两个操作数 char theta,*c,x,Dr[2];

// theta是算符，*c和x均为字符串的当前字符，Dr[2]保存当前字符和结束符 OPTR_InitStack (OPTR); // 初始化算符栈 OPTR_Push (OPTR, '#'); // '#'入算符栈，作为表达式的第一个字符 printf(\ #入栈 \\n\OPND_InitStack (OPND); // 初始化操作数栈

c = MyExpression; // 当前c保存字符串MyExpression的首地址 strcpy(TempData,\

while (*c!= '#' || OPTR_GetTop(OPTR)!= '#'){

// 当字符串的首字符和尾字符同时为#时，运算结束

if(In(*c, OPSET)==0){ // 若当前字符是操作数 Dr[0]=*c; // Dr[0]保存当前字符 Dr[1]='\\0'; // Dr[1]保存字符串的结束符'\\0' strcat(TempData,Dr);

// 将当前字符*c和结束符'\\0'连接到字符串TempData中

c++; if(In(*c,OPSET)==1){ // 考虑到操作数有可能不止一位数 Data=(double)atof(TempData);

// atof函数是将当前字符串转换成浮点型数据

OPND_Push(OPND, Data); strcpy(TempData,\ printf(\ %.3f入栈 \\n\ } } else{ // 若当前字符是算符 switch (Precede(OPTR_GetTop(OPTR), *c)){

// 获取当前算符栈的栈顶字符，与*c比较优先级，进行运算

case '<':

// 若当前栈顶算符优先级小于*c，则*c入算符栈

OPTR_Push(OPTR, *c); printf(\ %c入栈 \\n\ c++; break; case '=':

// 若当前栈顶算符优先级等于*c，则当前栈顶字符出栈

OPTR_Pop(OPTR, x); printf(\ %c出栈 \\n\

14

c++; break; case '>':

// 若当前栈顶算符优先级大于*c，则进行运算

OPTR_Pop(OPTR, theta); // 将栈顶算符出栈 printf(\ %c 出栈 \\n\

OPND_Pop(OPND, b); // 将栈顶操作数出栈 printf(\ %.3f出栈 \\n\

OPND_Pop(OPND, a); // 将次栈顶操作数出栈 printf(\ %.3f出栈 \\n\

OPND_Push(OPND, Operate(a, theta, b)); // 将运算结果入操作数栈 printf(\ %.3f入栈 \\n\ break; } } }

return OPND_GetTop(OPND); // 返回表达式的运算结果 }

void main(){ int x,t=0;

double RESULT;

char * MyExpression,str[40]; system(\

printf(\ 《 算术表达式的四则运算 》 \\n\

printf(\本课程设计完成简单的加、减、乘、除四则运算的功能^^\\n\\n\ printf(\ case 1: 输入表达式 \\n\ printf(\ case 2: 输出表达式 \\n\printf(\ case 3: 计算表达式 \\n\ printf(\ case 0: 退出程序 \\n\\n\ for(;;){ printf(\请输入您要进行的操作的序号：\ scanf(\ switch(x){ case 1: t++; getchar(); printf(\ 请输入一个正确的表达式 \\n\\t\\t\\t\\t\ gets(str); MyExpression=str; break; case 2: if(t==0) printf(\您尚未输入表达式，请先进行1操作，然后再进行此操作! \\n\ else{ printf(\ 您输入的表达式为\\n\\t \

15

puts(MyExpression); } break; case 3: if(t==0)

printf(\您尚未输入表达式，请先进行1操作，然后再进行此操作! \\n\ else{ RESULT=EvaluateExpression(MyExpression); printf(\ 算术表达式的结果：%.3f \\n\ } break; case 0: printf(\ exit(0); default: printf(\ break; }

}

}

欢迎使用，BYE BYE ^^__^^ 操作序号错误，请重新输入 16

\\n\\\n\ ！

puts(MyExpression); } break; case 3: if(t==0)

printf(\您尚未输入表达式，请先进行1操作，然后再进行此操作! \\n\ else{ RESULT=EvaluateExpression(MyExpression); printf(\ 算术表达式的结果：%.3f \\n\ } break; case 0: printf(\ exit(0); default: printf(\ break; }

}

}

欢迎使用，BYE BYE ^^__^^ 操作序号错误，请重新输入 16

\\n\\\n\ ！

本文来源：https://www.bwwdw.com/article/jssp.html