用两种方式实现表达式自动计算

数据结构（双语）

——项目文档报告

用两种方式实现表达式自动计算

专 业： 计算机科学与技术应用 班 级： 指导教师： *** 姓 名： 学 号：

- 1 -

用两种方式实现表达式自动计算

目 录

一、设计思想……………………………………………………….01 二、算法流程图…………………………………………………….01 三、源代码………………………………………………………….03 四、运行结果……………………………………………………….15 五、遇到的问题及解决…………………………………………….16 六、心得体会……………………………………………………….17

- 2 -

用两种方式实现表达式自动计算

一、设计思想

A: 中缀表达式转后缀表达式的设计思想： 我们借助计算机计算一个算数表达式的值，而在计算机中，算术表达式是由常量，变量，运算符和括号组成。由于运算符的优先级不同又要考虑括号。所以表达式不可能严格的从左到右进行，因此我们借助栈和数组来实现表达式的求值。栈分别用来存储操作数和运算符。

在计算表达式的值之前，首先要把有括号的表达式转换成与其等值的无括号的表达式，也就是通常说的中缀表达式转后缀表达式。在这个过程中，要设计两个栈，一个浮点型的存储操作数，用以对无符号的表达式进行求值。另一个字符型的用来存储运算符，用以将算术表达式变成无括号的表达式；我们要假设运算符的优先级：( ) , * /, + - 。首先将一标识号‘#’入栈，作为栈底元素；接着从左到右对算术表达式进行扫描。每次读一个字符，若遇到左括号‘（’，则进栈；若遇到的是操作数，则立即输出；若又遇到运算符，如果它的优先级比栈顶元素的优先级数高的话，则直接进栈，否则输出栈顶元素，直到新的栈顶元素的优先级数比它低的，然后将它压栈；若遇到是右括号‘）’，则将栈顶的运算符输出，直到栈顶的元素为‘（’，然后，左右括号互相底消；如果我们设计扫描到‘#’的时候表示表达式已经扫描完毕，表达式已经全部输入，将栈中的运算符全部输出，删除栈底的标识号。以上完成了中缀表达式转后缀表达式，输出无括号的表达式，若遇数值，操作数进栈；若遇运算符，让操作数栈的栈顶和次栈顶依次出栈并与此运算符进行运算，运算结果入操作数栈；重复以上的步骤，直到遇到‘#’，则此时栈中的结果便是所求的后缀表达式的值，接着输出结果。以上就是设计这个算法的主要的思想。

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

所谓的扫一遍就是当扫完一个表达式结果也就计算出来了，是在上面扫两遍的思想进行修改的得来，首先，我们要建立两个栈，一个为字符型的用来存放运算符，另一个浮点型的用来存放操作数。我们开始对表达式进行扫描，首先我们要假设运算符的优先级：( ) , * /, + - 。如果扫描到的是数字符号，把它们转换成浮点型数据，存入操作数栈中。如果扫描到的是运算符号，第一个运算符进栈，遇到‘（’存入运算符栈中，我们按照第一种算法的方法将表达式依次扫描。只不过不同的是，当每取得的一个运算符的时候，都要与栈顶的运算符进行比较，如果它的优先级小于栈顶运算符优先级时，取出栈顶运算符并从操作数栈中取栈顶两个数进行运算，得到的结果则要存回操作数栈，就这样边扫描边比较，再进行计算。遇到“）”对运算符的处理相同。扫描结束后，把运算符栈的元素和操作数栈里的数进行运算。每次的运算结果再放入操作数栈，一直到计算到运算符栈空。最后操作数栈的栈顶留下的操作数即表达式的计算结果。以上就是设计这个扫一遍算法的主要的思想。

设计思想的流程图详见图B；

二、算法流程图

- 3 -

用两种方式实现表达式自动计算

A:以下是中缀转后缀算法的流程图

图2是中缀转后缀算法的流程图

- 4 -

用两种方式实现表达式自动计算

B：以下是扫一遍代码运算的流程图：

图B是直接计算的流程图

三、源代码

A：下面给出的是用中缀表达式转后缀表达式算法实现的程序的源代码：

#include /*I/O函数*/ #include #include

#define MAXLEN 100 /*对栈的最大存贮值进行定义*/

- 5 -

用两种方式实现表达式自动计算

/*自定义两个栈*/ 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\ /*判断循环的条件当输入EOF的时候停止*/ {

Operation = InitChar(); Data = InitNum(); PushChar(Operation,'#');

- 6 -

用两种方式实现表达式自动计算

recv[strLen(recv)]='#'; /*将字符#赋予数组最后*/ ptRecv = recv;

for(i=0;iif(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)=='(') /*判断操作符的优先级高低*/

{

- 7 -

用两种方式实现表达式自动计算

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\ /*输出一个运算符*/ PopNum(Data,&opA); PopNum(Data,&opB);

resoult = Compute(opB,(char)suffix[j],opA); /*调用函数进行运算*/ PushNum(Data,resoult); /*运算结果入栈*/ }else {

- 8 -

用两种方式实现表达式自动计算

PushNum(Data,suffix[j]);

printf(\"%10f\输出后缀表达式*/; } }

printf(\"\\nthe Result is:%.2f\\n\\n\ /*输出运算结果*/ } 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; }

- 9 -

用两种方式实现表达式自动计算

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; /*#的优先级*/

- 10 -

用两种方式实现表达式自动计算

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 /*I/O函数*/ #include #include

#define MAXLEN 100 /*对栈的最大存储值进行声明*/

/*声明用来存储操作数和运算符的栈*/ typedef struct stackData {

float data[MAXLEN]; int top;

}stackData; /*定义操作数的栈*/

- 11 -

用两种方式实现表达式自动计算

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\ /*判断循环的条件当输入EOF的时候停止*/ {

Data = InitNum(); Operation = InitChar();

PushChar(Operation,'#');

recv[strLen(recv)]='#'; /*将字符#赋予数组最后*/

- 12 -

用两种方式实现表达式自动计算

ptRecv = recv;

for(i=0;iif(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

- 13 -

用两种方式实现表达式自动计算

{

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\输出扫描一遍的运算结果*/

- 14 -

用两种方式实现表达式自动计算

} 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*/

- 15 -

用两种方式实现表达式自动计算

} }

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;

- 16 -

用两种方式实现表达式自动计算

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:首先我们通过中缀表达式转换为后缀表达式来计算表达式

- 17 -

用两种方式实现表达式自动计算

图C：上图是利用中缀表达式转后缀表达式

B：其次我们直接来计算表达式的值

图D：这次是利用直接计算来实现的结果

五、遇到的问题及解决

这部分我主要遇到了如下几个个问题，其内容与解决方法如下所列：

➢ C语言中没有string类型，所以不能直接声明string类型的变量来存储输入的表达式，

也不能直接声明一个字符串数组来存储截取的数字字符串。

解决方法：C语言中有char类型，但是只能存储单个字符，所以可以声明一个char类型的数组或者一个指向char数组的指针变量，用来存储输入的表达式字符串。同样也可以使用char类型的数组来存储截取下来的数字字符串，具体存储方法如下：如果数字式单个字符，直接存入数组，然后在其后添加分隔符，如果是一系列的数字，则在字

- 18 -

用两种方式实现表达式自动计算

符数组中采用连续地址存储，同样后面添加分隔符，和其他字符分割开来，这样，就可以把数字字符存入到字符数组中了

➢ 问题2：在遇到小数点处理的问题上，虽然说处理小数点的方法不是唯一的，但在处理

的时候只能计算一位小数，如果输入的是两位的话，计算结果的时候它就把一位小数后面的数据全丢了。 解决方法：在输出后缀表达式的时候可以看到栈里存的数据最多只带一位小数，所以结果也只能出现一位小数。因为在处理小数的时候我是让小数点后面的数乘以0.1，再加上前面的。但如果是两位的话，那么最后的那一个是要乘以0.01的，也就是乘以0.1的自乘，所以在处理小数时我加了自乘的这行代码，运行的结果才出来了。

➢ 问题3：这个问题我碰到的确是改不出来，程序把小数点按0来算，所以结果出来跟正

确的结果比相差特别的大。

解决方法：当扫到一个小数的时候，一般是用小数部分除以10或乘以0.1，然后它们再自乘，接着往下算。但这个方法不管用，到最后实在是没办法了。所以最后请教了别人。 ➢ 问扫一遍的程序：问题1：扫一遍的是从扫两遍的改过来的，两个程序的算法存在差异，

特别是要修改中缀转后缀的那段代码，修改完成后，执行后的结果始终是零。 解决方法：出错的原因可能是运算符栈空或者是数据栈空，要不就是每次的计算结果没有放回到数据栈里。所以输出的结果是零。后来发现在每次计算的结果往回放的时候出了错误，根本就没往回放，所以加上计算结果往回放的代码，结果也就出来了

六、心得体会

通过这次作业真的受益匪浅，感触良多：

首先，要提高编程能力，必须多动手，多实践，对写程序代码这方面，一个程序从算法到用程序把它实现出来，这一整个过程是很不容易的，你懂得它的算法，不一定就能写的出来，通过这次我也深深的了这一点，而不是仅仅局限在书本上，更不能眼高手低。眼高手低，懒得动手，这就犯了编程人员的大忌。大一我们开始接触C语言，这是我们接触到的第一种编程语言，但是当时徒有对编程的兴趣，却没有付诸行动，动手少，结果考试险过，通过这次作业，我再次看了C语言课本，边看边写代码，理解快，印象深刻，思维也活跃许多，状态也好，真正的意识到，编程能力需要靠实践来提升。当自己写出意想的程序后，真的有些成就感。再者，在吴老师的指导和要求下，我们改掉了很多的编程坏习惯的同时也养成了良好的编程习惯，另一方面我们态度端正了很多，认真完成好每一项任务，这样无形中提高了对自己的要求，同时也增强了我们的动手能力和编程能力。 。

- 19 -