数学表达式计算(c语言实现).doc

______________________________________________________________________________________________________________
一、 设计思想
计算算术表达式可以用两种方法实现：

1.中缀转后缀算法
此算法分两步实现：先将算术表达式转换为后缀表达式，然后对后缀表达式进行计算。具体实现方法如下：
（1） 中缀转后缀
需要建一个操作符栈op和一个字符数组exp，op栈存放操作符，字符数组用来存放转换以后的后缀表达式。首先，得到用户输入的中缀表达式，将其存入str数组中。对str数组逐个扫描，如果是数字或小数点，则直接存入exp数组中，当扫描完数值后，在后面加一个#作为分隔符。
如果是操作符，并且栈为空直接入栈，如果栈不为空，与栈顶操作符比较优先等级，若比栈顶优先级高，入栈；如果比栈顶优先级低或相等，出栈将其操作符存到exp数组中，直到栈顶元素优先等级低于扫描的操作符，则此操作符入栈；如果是左括号，直接入栈，如果是右括号，出栈存入exp数组，直到遇到左括号，左括号丢掉。然后继续扫描下一个字符，直到遇到str中的结束符号\0，扫描结束。结束后看op栈是否为空，若不为空，继续出栈存入exp数组中，直到栈为空。到此在exp数组最后加结束字符\0。我们就得到了后缀表达式。
（2） 后缀表达式计算
此时需要一个数值栈od来存放数值。对exp数组进行逐个扫描，当遇到数字或小数点时，截取数值子串将其转换成double类型的小数，存入od栈中。当遇到操作符，从栈中取出两个数，进行计算后再放入栈中。继续扫描，知道扫描结束，此时值栈中的数值就是计算的结果，取出返回计算结果。

2.两个栈实现算法
此算法需要两个栈，一个值栈od，一个操作符栈op。将用户输入的数学表达式存入str数组中，对其数组进行逐个扫描。
当遇到数字或小数点，截取数值子串，将其转换成double类型的数值存入od栈中；当遇到左括号，直接入op栈；遇到右括号，op栈出栈，再从值栈od中取出两个数值，计算将其结果存入值栈中，一直进行此操作，直到操作符栈栈顶为左括号，将左括号丢掉。
如果遇到操作符，若op栈为空，直接入栈；若栈不为空，与栈顶元素比较优先等级，若比栈顶操作符优先等级高，直接入op栈，如果低于或等于栈顶优先等级，op栈出栈，再从值栈中取出两个数值，计算将其结果存入值栈中，一直进行此操作，直到栈顶优先等级低于扫描的操作符等级，将此操作符入op栈。继续扫描直到遇到str中的结束字符\0，扫描结束。此时看操作符栈是否为空，若不为空，出栈，再从值栈中取出两个数值进行计算，将其结果存入值栈，一直进行此操作，直到操作符栈为空。此时把值栈中的数值取出，即为所得的最终计算结果。
二、算法流程图
第一种算法：中缀转后缀算法

其主函数流程图为：

图1 主函数算法流程图

中缀转后缀算法流程图如下：

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

计算后缀表达式流程图如下：

图3 后缀表达式计算流程图

第二种算法：两个栈算法

其主函数流程图为：

图4 主函数算法流程图

直接计算数学表达式流程图如下：

图5 直接计算表达式流程图

三、源代码
下面给出的是用中缀转后缀算法实现的程序的源代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define MAXSIZE 100 //定义宏，数组最大长度为100
//函数实现中缀转后缀，将存储数学表达式的数组str传参进来，exp存储后缀表达式
void trans(char str[],char exp[])
{
struct
{
char data[MAXSIZE];//用来存放操作符
int top;//数组下标
}op;//用结构体创建操作符栈
char ch;
int i=0,j=0,tempi=0;
op.top=-1;//给操作符栈初始化，令下标为-1
while(ch!='\0')
{
ch=str[i]; //取str数组的第i个元素赋值给ch
if((ch>='0'&& ch<='9') || ch=='.')//对数值操作
{
tempi=i;//若ch为数字或小数点，将其下标值赋给临时下标tempi
//依次向后扫描str数组，若一直为数字，跳入while循环
while((ch>='0' && ch<= '9') || ch == '.')
{
tempi++;
exp[j]=ch;//将数字存入exp数组中
j++;
ch=str[tempi];//取str数组中下标为tempi的元素赋给ch
}
exp[j]='#';j++;//用#做分隔符，将数值分隔开
i=tempi;//跳出循环，将此时的tempi赋给i,继续向后扫描
}
//对操作符操作
else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='%' || ch == '(' || ch == ')')
{
int level(char op);//声明level函数
if(ch=='(')//如果为(，直接进栈
{
op.top++;
op.data[op.top]=ch;//进栈操作
}
else if(ch==')')
{
//如果为),一直出栈直到遇到(
while(level(op.data[op.top])!=-1)//若栈顶元素不为(,进入while循环
{
exp[j]=op.data[op.top];//操作符出栈，存入exp数组中
op.top--;
j++;
if(op.top==-1)break;//如果栈为空，跳出循环
}
op.top--;//左括号pop出来
}
else if(op.top==-1)//如果栈为空，直接进栈
{
op.top++;
op.data[op.top]=ch;//进栈操作
}
//如果所扫描的操作符优先等级比栈顶元素高，直接进栈
else if(level(ch)>level(op.data[op.top]))
{
op.top++;
op.data[op.top]=ch;//进栈操作
}
else
{
//如果所扫描的操作符优先等级没有栈顶元素高，
//一直出栈直到比栈顶元素优先级高
while(level(ch)<=level(op.data[op.top]))
{
exp[j]=op.data[op.top];//出栈存入exp数组中
op.top--;
j++;
if(op.top==-1)break;//如果栈为空，跳出循环
}
op.top++;
op.data[op.top]=ch;//比栈顶元素优先级高，入栈
}
i++;//str下标加1，向后扫描
}
}
while(op.top!=-1)//扫描结束后如果操作符栈不为空，出栈直至为空
{
exp[j]=op.data[op.top];//出栈存入exp数组中
op.top--;
j++;
}
exp[j]='\0';//赋\0结束exp字符数组
}
int level(char op)//判断操作符优先等级
{
if(op == '+' || op == '-')//若为+、-，等级为1
return 1;
else if(op == '*' || op == '/' || op == '%')
return 2; //若为*、/、%,等级为2
else if(op == '(')
return -1 ; //若为(,等级为-1
else
return -3; //其他等级为-3；
}
double calvalue(double od1,double od2,char tempop)//计算
{
switch(tempop){
case '+':
return od1 + od2; //计算加法
case '-':
return od1 - od2;//计算减法
case '*':
return od1 * od2;//计算乘法
case '/':
return od1 / od2;//计算除法
case '%':
return fmod(od1,od2);//求余
}
return 0;
}
double calculate(char exp[])//计算后缀表达式
{
struct //用结构体创建值栈
{
double data[MAXSIZE]; //存储数值
int top;
}od;
double d; //声明d变量存储数值
double od1,od2; //存储值栈依次pop出来的操作数
char ch;
char tempch[20]; //声明临时数组存储子串
int j=0,t;
int length=strlen(exp);//计算exp数组的长度
od.top=-1; //初始化值栈，令下标为-1
while(j<length)
{
ch=exp[j];//提取exp中第j个元素
if(ch!='+' && ch!='-' && ch!= '*' && ch!='/' && ch!='%')
{
//如果为数字或小数点
d=0;
t=0;
while((ch>='0' && ch<='9') ||ch=='.')
{
tempch[t]=ch;t++;//依次存放到临时数组中
j++;ch=exp[j];
}
tempch[t]='\0';//结束tempch数组
d=atof(tempch);//将子串转化成double类型的数
od.top++;
od.data[od.top]=d;//入值栈
}
else //若为操作符，从值栈中pop出两个数计算
{
od2=od.data[od.top];od.top--;//先出栈的赋给od2
od1=od.data[od.top]; //后出栈的赋给od1
od.data[od.top]=calvalue(od1,od2,ch); //计算出结果后再入栈
}
j++;
}
return od.data[od.top];//将结束后值栈中的数pop出来，即为计算结果
}
main()
{
char str[MAXSIZE],exps[MAXSIZE]; //定义两个数组
printf("请输入算术表达式：\n");
gets(str); //从控制台输入算数表达式
printf("表达式为： %s\n",str);
trans(str,exps); //调用trans函数，得到后缀表达式
printf("后缀表达式：%s\n",exps);
printf("结果为：%lf\n", calculate(exps)); //调用calculate函数，计算结果
}
下面给出的是用两个栈算法实现的程序的源代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>

#define MAXSIZE 100 //定义宏，数组最大长度为100
double calculate(char str[])
{
struct //用结构体创建操作符栈
{
char data[MAXSIZE];//用来存放操作符
int top;
}op;
struct //用结构体创建值栈
{
double data[MAXSIZE];//用来存放操作数
int top;
}od;
char ch;
char tempch[20];//声明临时数组存储子串
int j=0,t;
double d;
double od1,od2;//存储值栈依次pop出来的操作数
char tempop;
int length=strlen(str);//计算str数组的长度
op.top=-1;//初始化操作符栈，令下标为-1
od.top=-1;//初始化值栈
while(j<length)
{
ch=str[j];
if((ch>='0' && ch<='9') ||ch=='.')//若为数值或小数点
{
d=0;
t=0;
while((ch>='0' && ch<='9') ||ch=='.')//截取子串
{
tempch[t]=ch;t++;//赋值给临时数组
j++;ch=str[j];
}
tempch[t]='\0';
d=atof(tempch);//将子串转化成double类型的数
od.top++;
od.data[od.top]=d;//入值栈
}
//对操作符操作
else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='%' || ch == '(' || ch == ')')
{
if(ch=='(')//如果为(，直接进栈
{
op.top++;
op.data[op.top]=ch;//进栈操作
}
else if(ch==')')//如果为),一直出栈直到遇到(
{
int level(char op);//声明level函数
while(level(op.data[op.top])!=-1)//若栈顶元素不为(,进入while循环
{
//声明calvalue函数
double calvalue(double od1,double od2,char tempop);
od2=od.data[od.top];od.top--;
od1=od.data[od.top];
tempop=op.data[op.top];op.top--;
od.data[od.top]=calvalue(od1,od2,tempop);//计算出结果后入值栈
if(op.top==-1)break;//如果操作符栈为空，跳出循环
}
op.top--;//左括号pop出来
}
else if(op.top==-1)//如果栈为空，直接进栈
{
op.top++;
op.data[op.top]=ch;//进栈操作
}
//如果所扫描的操作符优先等级比栈顶元素高，直接进栈
else if(level(ch)>level(op.data[op.top]))
{
op.top++;
op.data[op.top]=ch;//进栈操作
}
else
{
//如果所扫描的操作符优先等级没有栈顶元素高，
//一直出栈直到比栈顶元素优先级高
while(level(ch)<=level(op.data[op.top]))
{
od2=od.data[od.top];od.top--;
od1=od.data[od.top];
tempop=op.data[op.top];op.top--;
od.data[od.top]=calvalue(od1,od2,tempop);//计算结果后入值栈
if(op.top==-1)break;//如果栈为空，跳出循环
}
op.top++;
op.data[op.top]=ch;//比栈顶元素优先级高，入操作符栈
}
j++;//str下标加1，向后扫描
}
}
while(op.top!=-1)//扫描结束后如果操作符栈不为空，出栈直至为空
{
od2=od.data[od.top];od.top--;
od1=od.data[od.top];
tempop=op.data[op.top];op.top--;
od.data[od.top]=calvalue(od1,od2,tempop);//计算结果后入值栈
}
return od.data[od.top];//将结束后值栈中的数pop出来，即为计算结果
}
int level(char op)//判断操作符优先等级
{
if(op == '+' || op == '-')//若为+、-，等级为1
return 1;
else if(op == '*' || op == '/' || op == '%')
return 2; //若为*、/、%,等级为2
else if(op == '(')
return -1 ; //若为(,等级为-1
else
return -3; //其他等级为-3；
}
double calvalue(double od1,double od2,char tempop)//计算
{
switch(tempop){
case '+':
return od1 + od2;//计算加法
case '-':
return od1 - od2;//计算减法
case '*':
return od1 * od2;//计算乘法
case '/':
return od1 / od2;//计算除法
case '%':
return fmod(od1,od2);//求余
}
return 0;
}
void main()
{
char str[MAXSIZE];//定义str数组存放数学表达式
printf("输入算术表达式：\n");
gets(str); //从控制台输入算数表达式
printf("结果是：%lf\n",calculate(str));//调用calculate函数，计算结果
}

四、运行结果

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

图7 两个栈算法运行结果

五、 遇到的问题及解决
编程的前期工作很重要，需要明确的理清思路，而编写运行的过程中更是会出现很多问题，有因粗心造成的拼写错误，有语法错误，也有逻辑错误。
在整个编程过程我主要遇到了如下几个大的问题，其内容与解决方法如下所列：
l 将字符表示的数字转化为浮点数
Java中有现成的截取子串的方法可以用，而我的c语言基础比较薄弱，所学知 识也不全面。刚开始的思路是先将出现数字的子串计数，得到一共有多少个数字，然后再从子串开始处扫描，依次乘以它的位权，在百位就乘以10的2次方，依次类推。经过很长时间的思考，终于写出了此解决方法，可是却忽略了小数点的存在。又开始用此方法试图解决存在小数点的问题，想了好久也没有解决方法。无奈之下求助于网络，看有没有什么更好的解决办法，一经查询知道了stdlib.h库中有atof的函数可以将字符串类型的数字转换为浮点型。于是我用一个while循环将数值子串截取下来存到一个临时数组中，将其成功的转换成浮点数，小数点的情况也解决了。
l 打印后缀表达式时出现“喊烫”情况
情况如下图：

图8 “喊烫”出错情况
编写完中缀转后缀的trans函数后，想打印后缀表达式检查是否正确时出现了问题，打印出来的全是“烫”。刚开始觉得很奇怪，存的都是数字或操作符，怎么会出现汉字呢？仔细检查程序，发现逻辑没有出错，但为什么打印不出正确结果很是不解。通过和同学讨论，上网查询才知道，如果字符串没有结束符号\0就会“喊烫”。再经过检查发现还真是没有给字符串加结束字符。于是在循环的结束给exp[j]='\0';解决了问题，得到了正确的结果。
l 程序运行时会中止
编写完程序后，编译没有错误，但运行总是会中止。
刚开始的问题是只打印出中缀表达式，光标停在下一行不动了。也不是死循环，也没有出现语法错误。说明程序进行到某一阶段出现问题不走了。于是我把循环中可以打印出来帮助我分析程序的值都打印出来，包括循环有没有正常执行，有没有进栈，出栈。
就这样一点一点分析后，发现自己在循环嵌套中出现了一点逻辑问题，导致没有进行应有的判断，所以没有出正确结果。发现问题后及时改正，程序就正常运行了。

六、心得体会
因为C语言是大一时学的，当时就学了些基础的理论知识，上机的练习很少，敲的也是一些简单的分析素数，比大比小的程序。由于有一年多没有碰过C语言，遗忘了不少。通过这次的编程作业，把C语言的知识又重新温习了一遍。再通过和java语言的比较，大致理解了两种编程思想的不同。在这次的练习中也深刻的体会到了思维严谨，认真的态度十分重要。所以在以后的学习道路中，要养成良好的编程习惯，思考问题要全面、编写时要仔细认真，不出拼写错误。只有养成良好的编程习惯，在以后的工作中才可以更好的胜任职位，写出安全、可靠、稳定的软件，服务于大众。
还有一些深刻的体会就是算法很重要，所以学好数据结构，算法等课程，无疑是打好了地基，在以后各个编程的解决中都可以起到至关重要的作用。

Welcome To
Download !!!

欢迎您的下载，资料仅供参考！

精品资料