表达式运算算法的实现.doc

专 业：
班 级：
指导教师：
姓 名：
学 号：

目 录
一、设计思想……………………………………………………….01
二、算法流程图…………………………………………………….01
三、源代码………………………………………………………….04
四、运行结果……………………………………………………….12
五、遇到的问题及解决…………………………………………….13
六、心得体会……………………………………………………….14

一、设计思想
（1）先将中缀表达式转化为后缀表达式，再通过计算后缀表达式求表达式的值。第一遍扫描中缀表达式，需要一个运算符栈和一个数组。运算符栈用来存放运算符，数组用来存放转换成的后缀表达式。首先将中缀表达式挨个扫描。如果是数字，则直接放在后缀表达式数组中，依次存放。如果扫描到的是运算符，则按照以下规则存放：栈空时，任何运算符可直接入栈。栈不空是，如果栈中运算符的优先级高于或等于将要放入栈中的运算符的优先级，则将栈中运算符出栈，放入后缀表达式数组中，直到栈中运算符优先级低于将要放入栈中的运算符的优先级，此时将此运算符放入运算符栈中。如果遇到左括号，则直接将左括号入栈，左括号入栈后优先级最低，其他运算符可直接放入。如果遇到右括号，则将运算符栈中的运算符依次取出放到后缀表达式数组中，直到遇到左括号为止，此时将左括号从栈顶删除。按此方法，直到后缀表达式转换成功。第二遍扫描后缀表达式，此时需要一个数栈。扫描时如果遇到数字，则直接放到数栈中。如果遇到运算符，则将数栈中两个数取出，先取出的放在运算符后面，后取出的放在运算符前面，进行运算符运算。将运算的结果放入栈中。之后接着扫描后缀表达式。另外因为运算数的位数不一定而且还有小数点，所以在扫到一个数时要判断这个数的位数，将这个完整的运算数字符串整个取出，这需要用到一个辅助索引。当栈中只有一个数字时，这个数字就是我们要求的表达式的值。
（2）直接计算表达式的值。这种方法需要两个栈，一个运算符栈，一个数栈。只需扫描一遍中缀表达式，边运算边入栈。当扫描到的为数字是，将其放入数栈中，然后扫描下一个字符。如果扫描到的是运算符，栈空时，任何运算符可直接入栈。栈不空是，如果栈中运算符的优先级高于或等于将要放入栈中的运算符的优先级，则将栈中运算符出栈，并从数栈中取出两个数，先取出的放在后面，后取出的放在前面，进行运算符运算，得出结果后，将其放入数栈中。如果栈顶运算符优先级依然高于或等于将要入栈的运算符优先级，仍然进行以上操作，直到栈顶运算符低于将要放入栈中的的运算符的优先级，此时将该运算符入栈。如果扫描到的是左括号，则直接将其入栈。如果扫描到的是右括号，则将栈顶运算符取出，进行以上运算，直到栈顶为左括号，此时将栈顶左括号删除即可，然后将运算结果放入数栈中。当中缀表达式扫描完，并且运算符栈中全部出栈，数栈中只剩一个数字时，即为运算结果。另外因为运算数的位数不一定而且还有小数点，所以在扫到一个数时要判断这个数的位数，将这个完整的运算数字符串整个取出，这需要用到一个辅助索引。

二、算法流程图

图1是从中缀表达式转为后缀表达式并对后缀表达式进行计算的算法流程图，图中所有图形都是长方形，按箭头顺序依次执行。其中如果箭头向下方向有分叉，则箭头左侧长方形代表“是”，右侧代表“否”。

图2是中缀表达式直接计算的算法流程图。按箭头方向执行。图中如果遇到选择类型的语句，则在箭头有分叉的下一行语句中先声明了选项，然后与后面语句逗号隔开。

具体流程图如下：

中缀表达式扫描完毕
运算符栈中元素全部输出放入后缀表达式数组exp[len]中
从后缀表达式中取元素ch=exp[t],t++
是否为数
存入数栈中
从数栈中取出两个数进行运算符运算，得出结果放入数栈
输出栈里最终栈顶元素即为所求
结束
ch是否为（
运算符栈为空或者栈运算符优先级低于ch优先级
将ch放入运算符栈中
将栈顶运算符出栈放入后缀表达式中，直到栈顶元素优先级低于ch优先级，此时将ch入栈
将ch入栈
将操作符栈中元素取出放入后缀表达式中，直到栈顶元素为（
用户输入表达式
将表达式赋给str[len]
构造运算符栈和数栈
扫描中缀表达式ch=str[i],i++
ch是否为数
将ch直接放入后缀表达式数组中
ch是否为+-*/%

图1 中缀转后缀再计算算法流程图
栈顶元素是否为（
是，pop出左括号
操作符栈是否为空
不是，取出数栈中两个数，计算后存入数栈
为空，取出数栈中的数作为返回值
不为空，取出数栈中两个数，计算后存入数栈，作为返回值
得到存放中缀表达式的数组
运算符，与栈顶比较优先级
操作符，判断是运算符还是括号
数字或小数点，截取子串并将其转换成double型存入数栈中
判断字符类型
依次取出数组中的每个字符
右括号，取出栈顶元素
左括号，直接入操作符栈
判断是哪个括号
入操作符栈
不高于栈顶，取出数栈中两个数，计算后存入数栈
结束

图2 中缀表达式直接计算算法流程图

三、源代码
下面给出的是用中缀表达式转换为后缀表达式再进行计算的算法实现的程序的源代码：

#include<stdio.h>//导入要用的包
#include<stdlib.h>
#include<math.h>
#define len 1000
struct opnode
{
char data[len];
int top;
}op;//定义字符栈
struct odnode
{
int top;
float data[len];
}od;//定义数栈
void trans(char str[],char exp[],struct opnode op)//中缀变后缀的方法
{
char ch;
int i=0,t=0;
op.top=-1;//初始字符栈顶为空
od.top=-1; //初始数栈顶为空
ch=str[i];i++; //定义存放字符串的数组
while(ch!='\0')//数组中字符串不为空
{
switch(ch)
{
case'+': //判断是否是'+'、'-'
case'-':
while(op.top!=-1&&op.data[op.top]!='(')//栈不为空且栈顶符号不为'('
{
exp[t++]=op.data[op.top--];//存放后缀表达式的数组添加元素
}
op.top++;
op.data[op.top]=ch;//入栈
break;
case'*': //判断是否是'*'、'/'、'%'
case'/':
case'%':
while(op.data[op.top]=='*'||op.data[op.top]=='/'||op.data[op.top]=='%')
{
exp[t++]=op.data[op.top--];
}//栈顶元素为'*'或'/'，存放后缀表达式的数组添加元素
op.top++;
op.data[op.top]=ch;//入栈
break;
case'(': op.top++;op.data[op.top]=ch;break;//扫描若是'(',入栈
case')': while(op.data[op.top]!='(')//不是左括号出栈
{
exp[t++]=op.data[op.top--];
}//栈顶元素不为'('，出栈
op.top--;//'('出栈
break;
case'=':break;
default: while(ch>='0'&&ch<='9'||ch=='.')
{
exp[t++]=ch;
ch=str[i++];
}//扫描是否是数字或小数点，存入数组
i--;
exp[t]='|';t++;//分隔后缀中的数值元素
break;
}
ch=str[i];i++;
}
while(op.top!=-1)//栈顶不为空
{
exp[t++]=op.data[op.top];
op.top--;
}//将栈顶元素赋给后缀表达式直到栈为空
exp[t]='\0';
}

float count(char exp[])//后缀计算的方法
{

float d=0; char ch,tran[len];
int t=0,i=0;
ch=exp[t];t++;
while(ch!='\0')
{
switch(ch)
{
case'+':
od.data[od.top-1]=od.data[od.top-1]+od.data[od.top];od.top--;//数栈中取值相加
break;
case'-':
od.data[od.top-1]=od.data[od.top-1]-od.data[od.top];od.top--;//数栈中取值相减
break;
case'*':
od.data[od.top-1]=od.data[od.top-1]*od.data[od.top];od.top--;//数栈中取值相乘
break;
case'/': if(od.data[od.top]!=0)
{

od.data[od.top-1]=od.data[od.top-1]/od.data[od.top];od.top--;//数栈中取值相除
}
else
{
printf("\n 0不能做被除数\n");//若除数为0则输出此语句
}
break;
case'%':if(od.data[od.top-1]!=0)
{

od.data[od.top-1]=fmod(od.data[od.top-1],od.data[od.top]); od.top--;//数栈中取值取余
}
else
{printf("0不能被任何值取余");}//若除数为0输出此语句
break;
default: while(ch>='0'&&ch<='9'||ch=='.')//扫描是否是数字或小数点
{
tran[i]=ch;//把元素存入字符串
i++;
ch=exp[t];
t++;
}
tran[i]='\0';//结束表示数字的字符串
i=0;
d=atof(tran);//字符串转化成数

od.top++;
od.data[od.top]=d;
}
ch=exp[t];t++;
}
return od.data[od.top];//返回计算结果
}
main()
{
char str[len],exp[len];
struct opnode op;
printf("输入一个计算表达式：\n");
gets(str);
trans(str,exp,op);
printf("后缀表达式：%s\n",exp);
printf("表达式结果： %f\n",count(exp));
scanf("%d\n");
return 0;
}
下面给出的是用中缀表达式直接进行计算的算法实现的程序的源代码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h> /*包含库函数*/
#define MAX 100 /*定义栈的最大长度*/
struct opnode /*声明op栈*/
{
char str[MAX];
int top_op;
};
struct odnode /*声明od栈*/
{
double num[MAX];
int top_od;
};

void push_op(struct opnode *op,char c) /*定义op栈的进栈函数*/
{
if(op->top_op>=MAX-1) /*如果栈满，不进行操作*/
{
}
else /*否则，进行进栈操作*/
{
op->top_op++;
op->str[op->top_op]=c;
}
}
void pop_op(struct opnode *op) /*定义op栈的出栈函数*/
{
if(op->top_op<=-1) /*如果栈为空，不进行操作*/
{
}
else /*否则，进行出栈操作*/
{
op->top_op--;
}
}
char top_op(struct opnode *op) /*定义op栈的看栈顶的函数*/
{
return(op->str[op->top_op]);
}
/***************/
void push_od(struct odnode *od,double d) /*定义od栈的进栈函数*/
{
if(od->top_od>=MAX-1) /*如果栈为满，不进行操作*/
{
}
else /*否则，进行进栈操作*/
{
od->top_od++;
od->num[od->top_od]=d;
}
}

void pop_od(struct odnode *od) /*定义od栈的出栈函数*/
{
if(od->top_od<=-1) /*如果栈为空，不进行操作*/
{
}
else /*否则，进行出栈操作*/
{
od->top_od--;
}
}

double top_od(struct odnode *od) /*定义od栈看栈顶的函数*/
{
return(od->num[od->top_od]);
}

/*判断是否为运算符*/
int is_op(char op) /*op为运算符*/
{
switch(op) /*用switch语句判断*/
{
case '(':return 1;break;
case ')':return 1;break;
case '+':return 1;break;
case '-':return 1;break;
case '*':return 1;break;
case '/':return 1;break;
case '%':return 1;break; /*如果是运算符，返回1*/
default:return 0;break; /*否则，返回0*/
}
}

/*判断运算符优先级*/
int level(char op) /*op为运算符*/
{
switch(op) /*用switch语句判断，返回值为运算符的栈内优先级*/
{
case '#':return 0;break; /*'#'作为栈底元素*/
case ')':return 0;break; /*如果是'#'或')'，返回0*/
case '(':return 1;break; /*如果是'（'，返回0*/
case '+':return 2;break;
case '-':return 2;break; /*如果是'+'或'-'，返回2*/
case '*':return 3;break;
case '/':return 3;break;
case '%':return 3;break; /*如果是'*','/'或'%'，返回3*/
default:return 0;break;
}
}
/*计算*/
double re(double a,double b,char op) /*计算两个浮点数的运算结果*/
{
switch(op) /*用switch语句判断，op为运算符*/
{
case '+':return a+b; /*返回a和b的和*/
break;
case '-':return a-b; /*返回a和b的差*/
break;
case '*':return a*b; /*返回a和b的积*/
break;
case '/':if(b==0.0)return 0; /*返回a和b的商*/
else return a/b; /*如果b=0，返回0，计算结果出错，但程序不会强行终止*/
break;
case '%':return (int)a%(int)b; /*返回a取余b的结果*/
break;
default:return 0;break; /*否则，返回0*/
}
}
/*主函数*/
void main()
{
int i,inpos; /*inpos是inorder[100]的扫描索引*/
char inorder[MAX]; /*用于存储表达式*/
char c,*p=NULL; /*atof()函数所用的指针*/
double a,b,result;
char temp_op;
struct opnode oplist; /*定义op栈*/
struct odnode odlist; /*定义od栈*/
struct opnode *op; /*定义op栈的指针*/
struct odnode *od; /*定义od栈的指针*/
op=&oplist;
od=&odlist;
od->top_od=-1; /*初始化od栈*/
op->top_op=-1; /*初始化op栈*/
c='#';
push_op(op,c); /*向op栈栈底放入'#'，用于进栈时判断优先级*/
printf("输入一个中缀表达式(直接计算):\n");/*提示信息*/
gets(inorder); /*接收表达式*/
/*扫描表达式*/
i=0; /*i作为扫描inorder[100]的辅助索引*/
inpos=0; /*初始化扫描索引*/
c=inorder[inpos];
while(c!='\0') /*用while循环扫描数组inorder[100]*/
{
c=inorder[inpos];
i=inpos;
if(c>='0'&&c<='9') /*如果是数字字符*/
{
p=&inorder[i]; /*p指针指向此数字字符在数组中的位置*/
a=atof(p); /*用atof()函数将数字字符转换为浮点型*/
push_od(od,a); /*将数字压入od栈中*/
while(inorder[i]>='0'&&inorder[i]<='9'||inorder[i]=='.')
{
i++;
}
i--;
inpos=i; /*将主索引和辅助索引置为此数字字符的最后一个位置*/
}
else if(is_op(c)) /*如果是操作符*/
{
if(level(c)>level(top_op(op))||c=='(')
{ /*如果操作符优先级大，压入op栈中*/
push_op(op,c);
}
else if(c==')') /*如果操作符是')'*/
{
temp_op=top_op(op);
while(temp_op!='(') /*从op栈中出栈，直到栈顶为'('*/
{
temp_op=top_op(op);
pop_op(op); /*从op栈中取出一个操作符*/

b=top_od(od);
pop_od(od);

a=top_od(od);
pop_od(od); /*从od栈中依次取出两个数字*/

result=re(a,b,temp_op); /*计算两个数字的运算结果*/

push_od(od,result); /*将结果压入od栈中*/

temp_op=top_op(op);
}
pop_op(op); /*将'('出栈*/
}
else if(level(c)<=level(top_op(op))) /*如果操作符优先级低*/
{
do
{
temp_op=top_op(op);
pop_op(op); /*从op栈中取出一个操作符*/

b=top_od(od);
pop_od(od);

a=top_od(od);
pop_od(od); /*从od栈中依次取出两个数字*/
result=re(a,b,temp_op); /*计算两个数字的运算结果*/
push_od(od,result); /*将结果压入od栈中*/
}
while(level(c)<=level(top_op(op))); /*此while循环结束后，操作符可以入栈*/
push_op(op,c); /*操作符压入op栈*/
}
}
inpos++; /*主索引自加1，开始下一次扫描*/
c=inorder[inpos];
} /* while循环结束后，表达式已扫描完毕*/
while(op->top_op>0) /*如果op栈中还有操作符*/
{
temp_op=top_op(op);
pop_op(op); /*从op栈中取出一个操作符*/

b=top_od(od);
pop_od(od);
a=top_od(od);
pop_od(od); /*从od栈中依次取出两个数字*/
result=re(a,b,temp_op); /*计算两个数字的运算结果*/
push_od(od,result); /*将结果压入od栈中*/
}/*此while循环结束后，计算表达式结束，结果存放在od栈的栈顶*/
result=top_od(od); /*从od栈中取出计算结果*/
printf("中缀表达式:"); /*提示信息*/
puts(inorder); /*输出中缀表达式*/
printf("结果=%f",result); /*输出结果*/
printf("\n按任意键退出!"); /*提示信息*/ }

四、运行结果

图4 中缀转后缀算法运行结果图

图5 中缀表达式直接计算算法运行结果图

五、遇到的问题及解决
这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：
l 当我基本将我的思路转为程序并编译通过后，我随意的输入几个算式，有些式子得 出的结果正确，而有的却出现错误。如式子为：9.0*(7+8)的结果正确，而当式子为9*12-5或者7/2-3时就会出错。
解决方法：为了发现问题的出处，我又连续试了好几个式子，并亲自计算结果，有些式子的结果很奇怪。其中一些式子本来应该是正值的结果却出现了负值。后来我发现如果式子很短，并且只有加号和乘号就不会出错，于是我就用两个简单的式子验证每个运算符，在验证减号时：7-3得出了-4的答案。于是猜想可能是运算顺序搞反了。接着我又试了试7/3和7%3，得出的结果是0和3。这就验证了我的猜想，于是我就开始检查我的代码，因为在程序中我运用自己建的一个运算函数来进行运算。我就将运算函数中两个数的位置前后对调。结果发现，式子的运算结果正常了，得到了需要的答案。可是还是没弄明白原因，于是我就看了看pop出这些数的数栈，突然想起栈是有调换数的顺序的功能的，先进栈的数后出来，而我却把先pop出来的数赋在运算符前，后pop出来的数放在运算符后面，所以出现了上面的错误，就这样纠正了错误。
l 将字符表示的数字转化成浮点数
解决方法：我的c语言基础比较薄弱，所学知 识 也不全面。刚开始的思路是先将出现数字的子串计数，得到一共有多少个数字，然后再从子串开始处扫描，依次乘以它的位权，在百位就乘以10的2次方，依次类推。经过很长时间的思考，终于写出了此解决方法，可是却忽略了小数点的存在。又开始用此方法试图解决存在小数点的问题，想了好久也没有解决方法。无奈之下求助于网络，看有没有什么更好的解决办法，一经查询知道了stdlib.h库中有atof的函数可以将字符串类型的数字转换为浮点型。于是我用一个while循环将数值子串截取下来存到一个临时数组中，将其成功的转换成浮点数，小数点的情况也解决了。
六、心得体会
大一就开始学c语言，可是当时学的时候觉得自己好像懂了，但是一编程就会头大。而且当时学的时候也没有好好学，指针、结构体、数组之类的只学了个一知半解，没有完全掌握。这次作业，让我又重新拿起了c语言课本，把自己以前没有学会的一点点拾起来。复习了以前的c语言基础知识，一点一点摸索。我知道，我现在的水平特别差，要想学好数据结构，就要打好以前的基础。以后就要多动手操作。书上的例题和算法最好都要自己动手来编程实现。那样可以加深对算法的理解，也可以提高我们的编程水平。同时，很多的东西理解了，可是在实现的时候还是会有很多意想不到的错误发生。在以后的练习和实践中，应该多动手，遇到问题多思考，即使方案不是最优也要想办法自己解决。然后和好的方案进行比较，找出自己的差距在哪。
由于编程基础没有打好，这次的作业寻求了很多网络资源和同学的帮助，在匆匆忙忙中才勉强完成。也深刻地认识到了自己和别人的差距，感觉自己有很大的不足。以前的态度就是不对的，以后一定更加努力地学习，补充以前落下的只是，争取能赶上其他人。
13