《用两种方式实现表达式自动计算.doc》由会员分享，可在线阅读，更多相关《用两种方式实现表达式自动计算.doc（18页珍藏版）》请在金锄头文库上搜索。
1、用两种方式实现表达式自动计算数据结构（双语）项目文档报告用两种方式实现表达式自动计算专 业： 计算机科学与技术应用 班 级： 指导教师： 吴亚峰 姓 名： 学 号： 目 录一、设计思想.01二、算法流程图.01三、源代码.03四、运行结果.15五、遇到的问题及解决.16六、心得体会.17一、设计思想A: 中缀表达式转后缀表达式的设计思想：我们借助计算机计算一个算数表达式的值，而在计算机中，算术表达式是由常量，变量，运算符和括号组成。由于运算符的优先级不同又要考虑括号。所以表达式不可能严格的从左到右进行，因此我们借助栈和数组来实现表达式的求值。栈分别用来存储操作数和运算符。在计算表达式的值之前，
2、首先要把有括号的表达式转换成与其等值的无括号的表达式，也就是通常说的中缀表达式转后缀表达式。在这个过程中，要设计两个栈，一个浮点型的存储操作数，用以对无符号的表达式进行求值。另一个字符型的用来存储运算符，用以将算术表达式变成无括号的表达式；我们要假设运算符的优先级：( ) , * /, + - 。首先将一标识号#入栈，作为栈底元素；接着从左到右对算术表达式进行扫描。每次读一个字符，若遇到左括号（，则进栈；若遇到的是操作数，则立即输出；若又遇到运算符，如果它的优先级比栈顶元素的优先级数高的话，则直接进栈，否则输出栈顶元素，直到新的栈顶元素的优先级数比它低的，然后将它压栈；若遇到是右括号），则将栈
3、顶的运算符输出，直到栈顶的元素为（，然后，左右括号互相底消；如果我们设计扫描到#的时候表示表达式已经扫描完毕，表达式已经全部输入，将栈中的运算符全部输出，删除栈底的标识号。以上完成了中缀表达式转后缀表达式，输出无括号的表达式，若遇数值，操作数进栈；若遇运算符，让操作数栈的栈顶和次栈顶依次出栈并与此运算符进行运算，运算结果入操作数栈；重复以上的步骤，直到遇到#，则此时栈中的结果便是所求的后缀表达式的值，接着输出结果。以上就是设计这个算法的主要的思想。设计思想的流程图详见图A；B: 直接计算表达式的值。所谓的扫一遍就是当扫完一个表达式结果也就计算出来了，是在上面扫两遍的思想进行修改的得来，首先，我
4、们要建立两个栈，一个为字符型的用来存放运算符，另一个浮点型的用来存放操作数。我们开始对表达式进行扫描，首先我们要假设运算符的优先级：( ) , * /, + - 。如果扫描到的是数字符号，把它们转换成浮点型数据，存入操作数栈中。如果扫描到的是运算符号，第一个运算符进栈，遇到（存入运算符栈中，我们按照第一种算法的方法将表达式依次扫描。只不过不同的是，当每取得的一个运算符的时候，都要与栈顶的运算符进行比较，如果它的优先级小于栈顶运算符优先级时，取出栈顶运算符并从操作数栈中取栈顶两个数进行运算，得到的结果则要存回操作数栈，就这样边扫描边比较，再进行计算。遇到“）”对运算符的处理相同。扫描结束后，把运
5、算符栈的元素和操作数栈里的数进行运算。每次的运算结果再放入操作数栈，一直到计算到运算符栈空。最后操作数栈的栈顶留下的操作数即表达式的计算结果。以上就是设计这个扫一遍算法的主要的思想。设计思想的流程图详见图B；二、算法流程图A:以下是中缀转后缀算法的流程图图2是中缀转后缀算法的流程图B：以下是扫一遍代码运算的流程图：图B是直接计算的流程图三、源代码A：下面给出的是用中缀表达式转后缀表达式算法实现的程序的源代码：#include /*I/O函数*/#include #include #define MAXLEN 100 /*对栈的最大存贮值进行定义*/*自定义两个栈*/typedef struct
6、 stackData float dataMAXLEN; int top; /*指针*/stackData; /*定义存储操作数的栈*/typedef struct stackChar char dataMAXLEN; int top; /*指针*/stackChar; /*用于定义存储操作符号的栈*/*对相应的函数和常量变量，指针进行声明*/ int judgeFirst(char c); /*声明判定操作符优先级的函数*/ int PushNum(stackData *p,float value); /* 入栈 */ int PushChar(stackChar *p,char value
7、); int PopNum(stackData *p,float *value); /* 出栈 */ int PopChar(stackChar *p,char *value); float VisitNum(stackData * p); char visitChar(stackChar * p); float Compute(float a,char ch,float b); /* 操作函数，执行具体运算 */ int Check(char *); stackData *Data; /*定义操作数栈，由指针data指出*/ stackChar *Operation; stackData *
8、 InitNum(); stackChar * InitChar(); int i,j=0; float bl,blo; /*对变量进行声明*/ float resoult,opA,opB; char operand2,opChar; /*定义字符型数组和字符变量*/ char recvMAXLEN; float suffixMAXLEN; char *ptRecv=NULL; /*定义字符型指针*/int main() /*主函数*/ printf(please enter tne formula:); while(scanf(%s,recv)!=EOF) /*判断循环的条件当输入EOF的时候停止*/ Operation = InitChar(); Data = InitNum(); PushChar(Operation,#); recvstrLen(recv)=#; /*将字符#赋予数组最后*/ ptRecv = recv;for(i=0;i=0 & recvi=0 & recvi+1judgeFirst(visitChar(Operation)|visitChar(Operation)=() /*判断操作符
