2报告正文.docx
《2报告正文.docx》由会员分享，可在线阅读，更多相关《2报告正文.docx（27页珍藏版）》请在冰点文库上搜索。
2报告正文
一、设计思想
计算算数表达式并求值，采取的共有两种方法：
1.先将算数表达式转化为后缀表达式，然后对后缀表达式进行计算。
2.对算数表达式进行直接的计算。
第一种算法
这种解决方案又分为两步：
1.将表达式先转化为后缀表达式的字符串数组
2.利用后缀表达式进行计算
在转化过程中，第一，建立一个存符号的栈，和一个字符串数组，用来存放转化以后的表达式
然后，对于得到的用户输入的字符串进行逐个的扫描，如果是数组或者小数点，则直接存放到数组中，并且在后面加入一个分隔符，如果是操作符，则和栈中的已存的进行比较，如果比栈中的操作符的优先级高，则直接入栈，如果优先级低或相等，则栈中元素出栈，存到字符串中，然后再次检查栈顶，直到栈中元素的优先级低于扫描操作符，则此操作符入栈，然后扫描下一个字符，直到遇到字符串的结束符号\0，扫描结束。
数组中存的就是后缀表达式。
得到后缀表达式后，进行计算，要用到数值栈。
首先要将字符表示的数字转化为浮点小数，然后进行扫描，遇到数值，放入栈中，遇到操作符，就从栈中取出两个数，进行计算后再放入栈中，扫描下一个，最后的计算结果就存到了栈中，直接取出栈内元素，就是计算的最后结果。
第二种算发
首先要建立两个栈，一个用来存放操作符，一个用来存放数值。
开始对用户输入的字符串进行扫描，如果是数字字符或者小数点，则将字符转化为浮点数存到数栈里，如果是操作符，则观察符号栈，如果栈顶元素的优先级低于观察的操作符，则操作符入栈，如果栈顶元素的优先级高于或者等于观察的操作符，则从数值栈中取出两个浮点数，从符号栈中取出栈顶的操作符，然后进行相应的数值计算，所得的结果再存到数值栈中，重复这样的操作，直到符号栈中栈顶元素的优先级低于观察的操作符，则此操作符入栈，然后对下一个字符进行扫描。
如果是左括号，则不进行优先级的比较，直接入栈，入栈后优先级为-1。
如果是右括号，则从数值栈中取两个操作数，符号栈中取出一个符号，然后进行计算后得数放入数栈中，不断进行此类操作，直到从栈中取出的是左括号为止，左括号去掉，扫描下一个。
扫描结束后，计算也结束了，计算的结果就存放在数值栈中，最后把数值栈中的数取出，就是所得的计算结果。
容错的算法简要：
括号匹配：
当扫描到左括号是，左括号直接入栈，扫描到右括号时，则左括号出栈，如果栈为空，则右括号多，如果最后栈中还有括号，则左括号多。
给出错误提示。
除数不为0：
当扫描到'/'时，就判断其后面的数字是否为0，如果为0报错。
取余运算：
取余运算时，操作数判断是否为整数，不为整数报错。
二、算法流程图
第一种算法:
先将表达式转化为后缀表达式，然后计算
其主函数流程图为：
其中将中缀表达式转化为后缀表达式的主要流程为：
后缀表达式的计算，实现的流程图为：
下面介绍直接计算出结果的算法的实现：
三、源代码
下面给出的是用先转后缀再计算和直接计算的算法实现的程序的源代码：
#include/*导入需要用到的各种包*/
#include
#include
typedefstruct/*定义结构体用来存储操作符*/
{
charop;/*存储字符*/
intlevel;/*存储优先级*/
}OpNode;
typedefstruct
{
OpNodeop[100];
inttop;
intsize;/*表示栈内元素的个数*/
}stack;/*定义符号栈*/
voidinit（stack*st）/*初始化栈*/
{
st->size=0;
st->top=0;
}
OpNodepop（stack*a）
{
if（a->size==0）/*如果栈为空结束操作*/
{
exit（-1）;
}
a->size--;
returna->op[--（a->top）];/*取出栈顶元素*/
}
voidpush（stack*a,OpNodeop）/*入栈函数*/
{
a->size++;
a->op[（a->top）++]=op;
}
OpNodetop（stack*a）/*观察栈顶函数*/
{
if（a->size==0）/*如果栈为空结束操作*/
{
printf（"stackisempty\n"）;
exit（-1）;
}
returna->op[（a->top）-1];/*只得到栈顶的值而不出栈*/
}
typedefstruct/*定义数值栈*/
{
doublenum[100];
inttop;/*栈顶指针*/
intsize;
}numstack;
voidinit2（numstack*st）/*初始化数值栈*/
{
st->size=0;
st->top=0;
}
doublepop2（numstack*a）/*数值栈出栈*/
{
if（a->size==0）/*出栈前的判空*/
{
exit（-1）;
}
a->size--;
returna->num[--（a->top）];/*得到栈顶的值*/
}
voidpush2（numstack*a,doublenum）/*入栈*/
{
a->size++;
a->num[（a->top）++]=num;
}
intmain（void）/*主函数*/
{
voidchange（charstr[],charexp[]）;/*声明要用到的各个函数*/
doubleCalResult（charexp[]）;/*声明后缀表达式的计算函数*/
doubleDirectcalresult（charstr[]）;
intcheck（charstr[],charchestr[100]）;
charstr[100],exp[100],chestr[100];/*str存储原算术表达式，exp存储对应的printf（"算术表达式为:
\n"）;后缀表达式,chestr存储容错字符'^'*/
gets（str）;
if（check（str,chestr））/*调用容错函数*/
{printf（"表达式错在：
\n"）;
printf（"%s\n",str）;
printf（chestr）;/*根据输入情况指出错误的地方*/
exit（-1）;
}
change（str,exp）;/*调用函数将中缀转化为后缀*/
printf（"后缀表达式为:
%s\n",exp）;
printf（"运算结果为：
%f\n",CalResult（exp））;/*调用函数计算后缀表达式*/
printf（"直接运算的结果为:
%f\n",Directcalresult（str））;/*调用直接计算函数*/
}
voidchange（charstr[],charch[]）/*将前缀表达式转化为后缀表达式*/
{
inti=0;/*str的索引*/
intk=0;
charc;/*字符串中取出的放在C中*/
stackst;/*定义符号栈*/
OpNodeop;
OpNodeops;
init（&st）;/*初始化符号栈*/
c=str[i++];
while（c!
='\0'）/*对字符串进行扫描*/
{
if（（c>='0'&&c<='9'）||c=='.'）/*如果字符为数字或小数点*/
{
while（（c>='0'&&c<='9'）||c=='.'）
{
ch[k++]=c;/*将字符直接放入数组中*/
c=str[i++];
}
ch[k++]='|';/*在其后面放入一个分隔符*/
}
if（c=='（'）/*如果字符是左括号*/
{
op.op='（';
op.level=-1;/*定义其优先级为-1*/
push（&st,op）;/*将左括号直接入栈*/
}
if（c=='）'）/*如果字符为右括号*/
{
op=top（&st）;/*首先观察栈顶*/
while（st.size!
=0&&op.op!
='（'）/*如果不是左括号并且栈不为空*/
{
op=pop（&st）;/*出栈并存入数组中*/
ch[k++]=op.op;
if（st.size>0）/*再次检查栈是否为空，*/
op=top（&st）;
elsebreak;/*为空就结束*/
}
pop（&st）;/*去掉左括号*/
}
if（c=='+'||c=='-'）/*如果是+-号*/
{
op.op=c;
op.level=1;/*优先级为1*/
if（st.size==0）
{
push（&st,op）;/*如果此时栈为空直接入栈*/
}
else
{
ops=top（&st）;/*观察栈顶*/
while（ops.level>=op.level）/*如果栈顶优先级高*/
{
ops=pop（&st）;
ch[k++]=ops.op;/*将栈顶元素取出存入数组中*/
if（st.size>0）
ops=top（&st）;/*进行判空操作，栈为空结束*/
else
break;
}
push（&st,op）;/*此时栈顶优先级低，入栈*/
}
}
if（c=='*'||c=='/'||c=='%'）
{
op.op=c;
op.level=2;/*优先级为1*/
if（st.size==0）
{
push（&st,op）;/*如果此时栈为空直接入栈*/
}
else
{
ops=top（&st）;/*观察栈顶*/
while（ops.level>=op.level）/*如果栈顶优先级高*/
{
ops=pop（&st）;/*将栈顶元素取出存入数组中*/
ch[k++]=ops.op;
if（st.size>0）
ops=top（&st）;/*进行判空操作，栈为空结束*/
else
break;
}
push（&st,op）;/*此时栈顶优先级低，入栈*/
}
}
c=str[i++];/*索引自加检索下一个字符*/
}
while（st.size!
=0）/*最后判断栈如果不为空*/
{
ops=pop（&st）;/*取出栈内元素存入数组中*/
ch[k++]=ops.op;
}
ch[k]='\0';/*将\0作为结尾存入数组*/
}
doubleCalResult（charexp[]）/*后缀表达式的计算*/
{
charc;
numstacknumst;/*建立数值栈*/
doubled1,d2,dr;
intk=0;/*后缀表达式的索引*/
inti=0;/*将字符转化为浮点数的索引*/
char*s;
chartrans[100];/*存字符表示的一段数字*/
init2（&numst）;/*实现数值栈*/
c=exp[k++];
while（c!
='\0'）/*开始扫描后缀表达式*/
{
if（c=='+'||c=='-'||c=='*'||c=='/'||c=='%'）/*如果是操作符*/
{
switch（c）
{
case'+':
/*如果是加法操作*/
d2=pop2（&numst）;
d1=pop2（&numst）;
dr=d1+d2;/*相加后入栈*/
push2（&numst,dr）;
break;
case'-':
/*如果是减法操作*/
d2=pop2（&numst）;
d1=pop2（&numst）;
dr=d1-d2;/*相减后入栈*/
push2（&numst,dr）;
break;
case'*':
/*如果是乘法操作*/
d2=pop2（&numst）;
d1=pop2（&numst）;
dr=d1*d2;/*相乘后入栈*/
push2（&numst,dr）;
break;
case'/':
/*如果是除法操作*/
d2=pop2（&numst）;
d1=pop2（&numst）;
dr=d1/d2;/*相除后入栈*/
push2（&numst,dr）;
break;
case'%':
/*如果是取余操作*/
d2=pop2（&numst）;
d1=pop2（&numst）;
dr=（double）（（int）d1%（int）d2）;/*类型转化并取余后入栈*/
push2（&numst,dr）;
break;
}
}
if（c>='0'&&c<='9'||c=='.'）/*如果是字符表示的数字*/
{
while（c>='0'&&c<='9'||c=='.'）
{
trans[i++]=c;/*将字符存入数组进行下一个的扫描*/
c=exp[k++];
}
trans[i++]='\0';/*将表示数字的字符串结束*/
i=0;
s=trans;/*将指针指向该数组*/
d1=atof（s）;/*利用函数将字符串转化为浮点数*/
push2（&numst,d1）;
}
c=exp[k++];
}
returnpop2（&numst）;/*最后结果将在数值栈中，取出作为返回值*/
}
doubleDirectcalresult（charstr[]）/*表达式的直接计算出结果*/
{
stackms;/*建立符号栈*/
numstackmns;/*建立数值栈*/
doublecalculate（doubleod1,doubleod2,OpNodeop）;
intindex=0;/*str的索引*/
intlen=strlen（str）;
charc;
chartrans[100];/*存放数值的一段字符*/
inti=0;/*trans的索引*/
char*s;
doubled;
OpNodetempn;/*存放当前扫描的操作符*/
OpNodetempln;
doubleoda,odb,odr;
doubleresult;/*作为返回值返回结果*/
init（&ms）;/*实现两个栈*/
init2（&mns）;
while（index{
c=str[index++];
if（c>='0'&&c<='9'||c=='.'）/*如果是数字字符或小数点*/
{
while（c>='0'&&c<='9'||c=='.'）
{
trans[i++]=c;/*将其存入数组扫描下一个*/
c=str[index++];
}
trans[i++]='\0';/*扫描完一个数结束数组*/
i=0;/*索引归0*/
s=trans;
d=atof（s）;
push2（&mns,d）;/*转化为浮点数入栈*/
}
if（c=='+'||c=='-'）/*如果是+-*/
{
tempn.level=1;/*优先级设为1*/
tempn.op=c;
if（ms.size==0）
{
push（&ms,tempn）;/*栈为空直接入栈*/
}
else
{
templn=top（&ms）;
while（templn.level>=tempn.level）/*栈顶优先级高*/
{
templn=pop（&ms）;/*取出操作数和操作符计算*/odb=pop2（&mns）;
oda=pop2（&mns）;
odr=calculate（oda,odb,templn）;
push2（&mns,odr）;/*结算结果入栈*/
if（ms.size>0）
{
templn=top（&ms）;/*如果栈空结束*/
}
else
break;
}
push（&ms,tempn）;/*操作符入栈*/
}
}
if（c=='*'||c=='/'||c=='%'）
{
tempn.level=2;/*定义优先级为2*/
tempn.op=c;
if（ms.size==0）
{
push（&ms,tempn）;/*栈空直接入栈*/
}
else
{
templn=top（&ms）;
while（templn.level>=tempn.level）/*栈顶优先级高*/
{
templn=pop（&ms）;/*取出操作数和操作符计算*/
odb=pop2（&mns）;
oda=pop2（&mns）;
odr=calculate（oda,odb,templn）;
push2（&mns,odr）;/*结算结果入栈*/
if（ms.size>0）
{
templn=top（&ms）;
}
else
break;/*如果栈空结束*/
templn=top（&ms）;
}
push（&ms,tempn）;/*操作符入栈*/
}
}
if（c=='（'）/*如果是左括号*/
{
tempn.level=-1;
tempn.op=c;/*直接入栈优先级定位-1*/
push（&ms,tempn）;
}
if（c=='）'）/*如果是右括号*/
{
while（tempn.op!
='（'）/*遇到左括号结束*/
{
templn=pop（&ms）;
odb=pop2（&mns）;/*从数栈中取两个数，从符号栈里取操作符*/
oda=pop2（&mns）;
odr=calculate（oda,odb,templn）;/*计算出结果入栈*/
push2（&mns,odr）;
if（ms.size>0）
tempn=top（&ms）;
else
break;/*如果栈空结束*/
}
pop（&ms）;/*取出左括号*/
}
}
tempn=top（&ms）;
while
（1）
{
templn=pop（&ms）;
odb=pop2（&mns）;/*从数栈中取两个数，从符号栈里取操作符*/
oda=pop2（&mns）;
odr=calculate（oda,odb,templn）;/*计算出结果入栈*/
push2（&mns,odr）;
if（ms.size>0）
tempn=top（&ms）;/*如果栈空结束*/
else
break;
}
result=pop2（&mns）;/*最后的结果在数值栈中返回*/
returnresult;
}
doublecalculate（doubleod1,doubleod2,OpNodeop）/*已知操作符和操作数的计算*/
{
switch（op.op）
{
case'+':
returnod1+od2;
case'-':
returnod1-od2;/*判断操作符是哪个执行相应计算*/
case'*':
returnod1*od2;
case'/':
returnod1/od2;
case'%':
return（double）（（int）od1%（int）od2）;
}
return0;/*如果上面的都没有执行返回0*/
}
intcheck（charstr[],charchestr[100]）/*容错函数*/
{
charc;
charcdivide;
inti=0;/*str的索引*/
stackche;/*括号匹配用到的栈*/
OpNodetemp;
intk=0;/*chestr的索引*/
intisinteger（charinteger[100]）;/*%计算是判断是否是整数*/
chars1[10];/*%操作时存储%左右的数字*/
chars2[10];
intindexs1=0;/*s1s2的索引*/
intindexs2=0;
init（&che）;
intflag=0;/*0--没有出错1--有错*/
inttag=0;
c=str[i];/*开始扫描*/
intj;/*数组chestr索引*/
for（j=0;j<99;j++）
{
chestr[j]='';/*数组初始化待以后加入'^'*/
}
chestr[j]='\0';
while（c!
='\0'）
{
if（c=='
升级会员 