数据结构（双语）——项目文档报告用两种方式实现表达式自动计算专业：计算机科学与技术应用班级：指导教师：吴亚峰姓名：学号：目录一、设计思想 (01)二、算法流程图 (01)三、源代码 (03)四、运行结果 (15)五、遇到的问题及解决 (16)六、心得体会 (17)一、设计思想A: 中缀表达式转后缀表达式的设计思想：我们借助计算机计算一个算数表达式的值，而在计算机中，算术表达式是由常量，变量，运算符和括号组成。

由于运算符的优先级不同又要考虑括号。

所以表达式不可能严格的从左到右进行，因此我们借助栈和数组来实现表达式的求值。

栈分别用来存储操作数和运算符。

在计算表达式的值之前，首先要把有括号的表达式转换成与其等值的无括号的表达式，也就是通常说的中缀表达式转后缀表达式。

在这个过程中，要设计两个栈，一个浮点型的存储操作数，用以对无符号的表达式进行求值。

另一个字符型的用来存储运算符，用以将算术表达式变成无括号的表达式；我们要假设运算符的优先级：( ) , * /, + - 。

首先将一标识号‘#’入栈，作为栈底元素；接着从左到右对算术表达式进行扫描。

每次读一个字符，若遇到左括号‘（’，则进栈；若遇到的是操作数，则立即输出；若又遇到运算符，如果它的优先级比栈顶元素的优先级数高的话，则直接进栈，否则输出栈顶元素，直到新的栈顶元素的优先级数比它低的，然后将它压栈；若遇到是右括号‘）’，则将栈顶的运算符输出，直到栈顶的元素为‘（’，然后，左右括号互相底消；如果我们设计扫描到‘#’的时候表示表达式已经扫描完毕，表达式已经全部输入，将栈中的运算符全部输出，删除栈底的标识号。

以上完成了中缀表达式转后缀表达式，输出无括号的表达式，若遇数值，操作数进栈；若遇运算符，让操作数栈的栈顶和次栈顶依次出栈并与此运算符进行运算，运算结果入操作数栈；重复以上的步骤，直到遇到‘#’，则此时栈中的结果便是所求的后缀表达式的值，接着输出结果。

以上就是设计这个算法的主要的思想。

设计思想的流程图详见图A；B: 直接计算表达式的值。

所谓的扫一遍就是当扫完一个表达式结果也就计算出来了，是在上面扫两遍的思想进行修改的得来，首先，我们要建立两个栈，一个为字符型的用来存放运算符，另一个浮点型的用来存放操作数。

我们开始对表达式进行扫描，首先我们要假设运算符的优先级：( ) , * /, + - 。

如果扫描到的是数字符号，把它们转换成浮点型数据，存入操作数栈中。

如果扫描到的是运算符号，第一个运算符进栈，遇到‘（’存入运算符栈中，我们按照第一种算法的方法将表达式依次扫描。

只不过不同的是，当每取得的一个运算符的时候，都要与栈顶的运算符进行比较，如果它的优先级小于栈顶运算符优先级时，取出栈顶运算符并从操作数栈中取栈顶两个数进行运算，得到的结果则要存回操作数栈，就这样边扫描边比较，再进行计算。

遇到“）”对运算符的处理相同。

扫描结束后，把运算符栈的元素和操作数栈里的数进行运算。

每次的运算结果再放入操作数栈，一直到计算到运算符栈空。

最后操作数栈的栈顶留下的操作数即表达式的计算结果。

以上就是设计这个扫一遍算法的主要的思想。

设计思想的流程图详见图B；二、算法流程图A:以下是中缀转后缀算法的流程图图2是中缀转后缀算法的流程图B：以下是扫一遍代码运算的流程图：图B是直接计算的流程图三、源代码A：下面给出的是用中缀表达式转后缀表达式算法实现的程序的源代码：#include <stdio.h> /*I/O函数*/#include <malloc.h>#include <stdlib.h>#define MAXLEN 100 /*对栈的最大存贮值进行定义*//*自定义两个栈*/typedef struct stackData{float data[MAXLEN];int top; /*指针*/}stackData; /*定义存储操作数的栈*/typedef struct stackChar{char data[MAXLEN];int top; /*指针*/}stackChar; /*用于定义存储操作符号的栈*//*对相应的函数和常量变量，指针进行声明*/int judgeFirst(char c); /*声明判定操作符优先级的函数*/int PushNum(stackData *p,float value); /* 入栈*/int PushChar(stackChar *p,char value);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 * InitNum();stackChar * InitChar();int i,j=0;float bl,blo; /*对变量进行声明*/float resoult,opA,opB;char operand[2],opChar; /*定义字符型数组和字符变量*/char recv[MAXLEN];float suffix[MAXLEN];char *ptRecv=NULL; /*定义字符型指针*/int main() /*主函数*/{printf("please enter tne formula:");while((scanf("%s",recv))!=EOF) /*判断循环的条件当输入EOF的时候停止*/ {Operation = InitChar();Data = InitNum();PushChar(Operation,'#');recv[strLen(recv)]='#'; /*将字符#赋予数组最后*/ptRecv = recv;for(i=0;i<strLen(ptRecv);i++) /*扫描表达式，判断循环的条件*/{if(recv[i]>='0' && recv[i]<='9' || recv[i]=='.') /*判断数值*/{double weight=0.1;int flag=0; /*定义变量flag，用来标志小数点*/float blo=0; /*定义浮点型变量*/blo=recv[i]-'0';while(recv[i+1]>='0' && recv[i+1]<='9' || recv[i+1]=='.') /*判定数值*/{if(recv[i+1]=='.') /*读到小数点*/flag=1;else{if(flag==0) blo=blo*10+recv[i+1]-'0'; /*将整数部分字符串转化为实数*/else{blo=blo+( recv[i+1]-'0' )*weight; /*将表示小数部分的字符也转化过来*/weight*=0.1; /*weight为小数位权*/}}i++;}suffix[j]=blo;j++; /*数值进入数组*/}else{if(recv[i]=='#') /*遇见字符#*/{while(visitChar(Operation)!='#') /*对操作符栈进行遍历*/{PopChar(Operation,&opChar);suffix[j]=opChar;j++; /*字符出栈进入数组*/}}else{if(judgeFirst(recv[i])>judgeFirst(visitChar(Operation))||visitChar(Operation)=='(') /*判断操作符的优先级高低*/ {PushChar(Operation,recv[i]); /*字符入栈*/}else{if(recv[i]==')') /*遇见字符）*/{while(visitChar(Operation)!='(') /*输出（之前的所有操作符*/{PopChar(Operation,&opChar);suffix[j]=opChar;j++; /*操作符进入数组*/}PopChar(Operation,&opChar);}else{while(judgeFirst(recv[i])<=judgeFirst(visitChar(Operation))) /*进栈的运算符优先级低时，先出栈后进栈*/{PopChar(Operation,&opChar);suffix[j]=opChar; /*出栈的进入数组*/j++;}PushChar(Operation,recv[i]); /*运算符进栈*/}}}}}printf("the suffix is:"); /*输出后缀表达式*/for(j=0;suffix[j]!='\0';j++){if((char)suffix[j]=='+'||(char)suffix[j]=='-'||(char)suffix[j]=='*'||(char)suffix[j]=='/') /*强制类型转换*/{printf("%6c",(char)suffix[j]); /*输出一个运算符*/PopNum(Data,&opA);PopNum(Data,&opB);resoult = Compute(opB,(char)suffix[j],opA); /*调用函数进行运算*/PushNum(Data,resoult); /*运算结果入栈*/}else{PushNum(Data,suffix[j]);printf("%10f",suffix[j]) /*输出后缀表达式*/;}}printf("\nthe Result is:%.2f\n\n",resoult); /*输出运算结果*/}return 0;}stackData * InitNum() /*初始化数值栈*/{stackData *p = (stackData *)malloc(sizeof(stackData)); /*取一段内存赋予数值栈*/ p->top = -1; /*定义栈底*/return p; /*返回数值栈*/}stackChar * InitChar() /*初始化操作符栈*/{stackChar *p = (stackChar *)malloc(sizeof(stackChar)); /*取一段内存赋予操作符栈*/ p->top = -1;return p;}int PushNum(stackData *p,float value) /*定义入栈函数*/{if(p->top < MAXLEN-1){p->top +=1; /*指针*/p->data[p->top] = value; /*入栈的数值为栈顶元素*/return 1;}else{return 0;}}int PushChar(stackChar *p,char value) /* 定义操作符入栈函数*/{if(p->top < MAXLEN-1) /*栈不能满*/{p->top +=1; /*指针*/p->data[p->top] = value; /*入栈字符为栈顶元素*/return 1;}else{return 0; /*栈溢出返回0*/}}int PopNum(stackData *p,float *value) /*定义数值出栈函数*/{if(p->top >= 0) /*判定栈不为空*/{*value = p->data[p->top];p->top -= 1; /*指针*/}return 1;}int PopChar(stackChar *p,char *value) /*定义操作符出栈函数*/ {if(p->top >= 0) /*判定栈不为空*/{*value = p->data[p->top];p->top -= 1; /*指针*/}return 1;}float VisitNum(stackData * p) /*定义数值栈遍历函数*/{if(p->top!=-1) /*判定栈是否为空*/return p->data[p->top];else return 0;}char visitChar(stackChar * p) /*定义操作符栈遍历函数*/{if(p->top!=-1) /*判定栈是否为空*/return p->data[p->top];else return 0;}int judgeFirst(char c) /*符号的优先级*/{switch(c){case '#': return 0; /*#的优先级*/case '+':return 1;case '-':return 1; /*减号的优先级*/case '*':return 2;case '/':return 2;case '(':return 3; /*左括号的优先级*/default : return -1;}}int strLen(char *L) /*计算字符串长度*/{int i = 0;for(;L[i]!='\0';i++); /*循环条件的判定*/if(L[0]=='-'||L[0]=='+'){i=i-1;}return i;}float Compute(float a,char ch,float b) /*数据运算*/{switch(ch){case '+':return a+b; /*返回加号数值运算结果*/case '-':return a-b;case '*':return a*b; /*返回乘号数值运算结果*/case '/':return a/b; /*返回除号数值运算*/default : return -1; }}B：下面给出的是直接计算的思想的代码实现：#include <stdio.h> /*I/O函数*/#include <malloc.h>#include <stdlib.h>#define MAXLEN 100 /*对栈的最大存储值进行声明*//*声明用来存储操作数和运算符的栈*/typedef struct stackData{float data[MAXLEN];int top;}stackData; /*定义操作数的栈*/typedef struct stackChar{char data[MAXLEN];int top;}stackChar; /* 用于定义运算符的栈*//*对函数进行声明*/int judgeFirst(char c); /*声明判定操作符优先级的函数*/ char visitChar(stackChar * p);int pushNum(stackData *p,float value); /* 操作数入栈*/int PushChar(stackChar *p,char value); /* 运算符入栈*/int PopNum(stackData *p,float *value); /* 操作数出栈*/int PopChar(stackChar *p,char *value); /* 运算符出栈*/float VisitNum(stackData * p);float Compute(float a,char ch,float b); /* 操作函数，执行具体运算*/int main() /*主函数*/{stackData * InitNum();stackChar * InitChar();int Check(char *);stackData *Data; /*定义操作数栈，由指针data指出*/stackChar *Operation; /*定义运算符栈，由指针Operation指出*/int i; /*对变量进行声明*/float dit,digit;float resoult,opA,opB;char operand[2],opChar; /*定义字符型数组和字符变量*/char recv[MAXLEN];char *ptRecv=NULL; /*定义字符型指针*/printf ("please enter the formula:");while((scanf("%s",recv))!=EOF) /*判断循环的条件当输入EOF的时候停止*/{Data = InitNum();Operation = InitChar();PushChar(Operation,'#');recv[strLen(recv)]='#'; /*将字符#赋予数组最后*/ptRecv = recv;for(i=0;i<strLen(ptRecv);i++) /*判定循环的条件*/{if(recv[i]>='0' && recv[i]<='9' || recv[i]=='.') /*判断值*/{double weight=0.1;int flag=0; /*定义整形变量flag,记录是否有小数点*/float digit=0; /*定义浮点型变量*/digit=recv[i]-'0';while(recv[i+1]>='0' && recv[i+1]<='9' || recv[i+1]=='.') /*判定数值*/{if(recv[i+1]=='.') /*读到小数点*/flag=1;else{if(flag==0) digit=digit*10+recv[i+1]-'0'; /*将整数部分字符串转化为实数*/else{digit=digit+( recv[i+1]-'0')*weight; /*将表示小数部分的字符也转化过来*/weight*=0.1; /*weight为小数位权*/}}i++;}pushNum(Data,digit); /*将数值进栈*/}else{if(recv[i]=='#') /*遇见字符#*/{while(visitChar(Operation)!='#') /*对操作符栈进行遍历*/{PopChar(Operation,&opChar); /*字符出栈*/PopNum(Data,&opA);PopNum(Data,&opB); /*数出栈*/resoult = Compute(opB,opChar,opA); /*调用运算函数*/pushNum(Data,resoult);}}else{if(judgeFirst(recv[i])>judgeFirst(visitChar(Operation))||visitChar(Operation)=='(')/*判断操作符的优先级高低*/ {PushChar(Operation,recv[i]); /*操作符进栈*/}else{if(recv[i]==')') /*当操作符为)时*/{while(visitChar(Operation)!='(') /*遍历操作符栈*/{PopChar(Operation,&opChar);PopNum(Data,&opA);PopNum(Data,&opB); /*从数值栈输出一个值*/resoult = Compute(opB,opChar,opA);pushNum(Data,resoult);/*结果放回栈里*/}PopChar(Operation,&opChar); /*输出操作符*/}else{while(judgeFirst(recv[i])<=judgeFirst(visitChar(Operation))) /*判断操作符的优先级高低*/{PopChar(Operation,&opChar);PopNum(Data,&opA); /*从数值栈输出数值*/PopNum(Data,&opB);resoult = Compute(opB,opChar,opA); /*调用运算函数*/pushNum(Data,resoult); /*将运算结果入栈*/}PushChar(Operation,recv[i]); /*将操作符入栈*/}}}}}printf("\nthe Result is:%.2f\n\n",resoult);/*输出扫描一遍的运算结果*/}return 0;}stackData * InitNum() /*初始化数值栈*/{stackData *p;p= (stackData *)malloc(sizeof(stackData)); /*取一段内存赋予数值栈*/p->top = -1; /*定义栈底*/return p; /*返回数值栈*/}stackChar * InitChar() /*初始化操作符栈*/{stackChar *p = (stackChar *)malloc(sizeof(stackChar)); /*取一段内存赋予操作符栈*/p->top = -1;return p;}int pushNum(stackData *p,float value) /*定义入栈函数*/{if(p->top < MAXLEN-1) {p->top +=1; /*指针*/p->data[p->top] = value; /*入栈的数值为栈顶元素*/return 1;}else{return 0;}}int PushChar(stackChar *p,char value) /* 定义操作符入栈函数*/ {if(p->top < MAXLEN-1){p->top +=1; /*指针*/p->data[p->top] = value; /*入栈字符为栈顶元素*/return 1;}else{return 0; /*栈溢出返回0*/}}int PopNum(stackData *p,float *value) /*定义数值出栈函数*/ {if(p->top >= 0) /*判定栈不为空*/{*value = p->data[p->top];p->top -= 1; /*指针*/}return 1;}int PopChar(stackChar *p,char *value) /*定义操作符出栈函数*/ {if(p->top >= 0) /*判定栈不为空*/{*value = p->data[p->top];p->top -= 1; /*指针*/}return 1;}float VisitNum(stackData * p) /*定义数值栈遍历函数*/ {if(p->top!=-1) /*判定栈是否为空*/return p->data[p->top];else return 0;}char visitChar(stackChar * p) /*定义操作符栈遍历函数*/ {if(p->top!=-1) /*判定栈是否为空*/return p->data[p->top]; /*返回栈顶的值*/ else return 0;}int judgeFirst(char c) /*符号的优先级*/{switch(c){case '#': return 0;case '+':return 1; /*加号的优先级*/case '-':return 1;case '*':return 2; /*乘号的优先级*/case '/':return 2; /*除号的优先级*/case '(':return 3;default : return -1;}}int strLen(char *L) /*计算字符串长度*/{int i = 0;for(;L[i]!='\0';i++); /*循环条件的判定*/if(L[0]=='-'||L[0]=='+'){i=i-1;}return i;}float Compute(float a,char ch,float b)/*数据运算*/{switch(ch){case '+':return a+b; /*返回加号数值运算*/case '-':return a-b; /*返回减号数值运算*/case '*':return a*b;case '/':return a/b; /*返回除号数值运算*/default : return -1;}}四、运行结果A:首先我们通过中缀表达式转换为后缀表达式来计算表达式图C：上图是利用中缀表达式转后缀表达式B：其次我们直接来计算表达式的值图D：这次是利用直接计算来实现的结果五、遇到的问题及解决这部分我主要遇到了如下几个个问题，其内容与解决方法如下所列：C语言中没有string类型，所以不能直接声明string类型的变量来存储输入的表达式，也不能直接声明一个字符串数组来存储截取的数字字符串。