C语言实现表达式计算.docx
《C语言实现表达式计算.docx》由会员分享，可在线阅读，更多相关《C语言实现表达式计算.docx（23页珍藏版）》请在冰点文库上搜索。
C语言实现表达式计算
一、设计思想
两种算法首先都要建立两个栈，一个是存放操作数的数栈OdStack，一个是存放运算符的符栈OpStack。
数栈采用double型的用来存放浮点数，符栈采用char型的用来存放运算符，由于考虑到运算符有优先级的问题，所以事先做了一个Type用来存储运算符的优先级。
栈建立好了之后做栈的相关操作，初始化栈，入栈，出栈，看栈顶。
其中入栈要判满，出栈和看栈顶要判空。
中缀转后缀再计算的算法。
此算法的基本思路是先将中缀表达式转换成后缀表达式，之后再利用后缀表达式的算法对表达式进行计算。
首先，用一个char数组将中缀表达式读入，对数组中的每一个元素进行处理，区分哪些是数，哪些是运算符。
如果是数元素（或小数点元素），则依次存入用来存储后缀表达式的char数组，直到一个整合数存完之后用空格将其与后面的元素分开。
如果是运算符元素，则根据当前运算符的优先级和栈里面的运算符的优先级进行处理。
如果栈内元素的优先级小于当前元素的优先级或者栈内为空，则将当前运算符入栈；如果栈内元素的优先级大于等于当前元素的，则依次将出栈元素存入后缀表达式，并用空格将其与后面的元素分开，直到栈内元素的优先级小或者栈内为空。
对于左括号来说，无条件进栈，并只在有右括号出现的时候才有可能出栈。
对于右括号来说，无条件让栈内元素出栈，直到左括号出栈。
依次将每个元素进行处理直到中缀表达式索引完毕。
至此，已经实现了将中缀表达式转换成了后缀表达式，在数组的最后加上结束符以便下一步的调用。
第二步，读出后缀表达式并进行计算。
如果索引到空格则将索引标志后推1位。
之后要先对char型的数字元素进行整合，从后缀表达式中依次取出数字元素（连同小数点）存入一个新的char型数组，直到一整个数取完后通过atof函数将char型转换成浮点型存入数栈，并将新数组初始化用来存储下一个数。
如果是索引到运算符，则在数栈中出栈两个数字与当前运算符进行运算，先出栈的数字放在运算符后面，后出栈的数字放在运算符的前面，将运算以后的结果再次存入数栈。
依次进行计算直到后缀表达式索引完毕。
此时对栈内剩余元素进行操作。
每在符栈出栈一个运算符，就从数栈出栈两个数进行计算，算法同上，将运算以后的结果再次存入数栈。
循环操作直到符栈栈空，此时数栈出栈元素即为最后结果。
边转换边计算的算法。
此算法的基本思路是将中缀表达式按照转换后缀的表达式的方法逐步进行，边转换边进行计算和存储。
首先，用一个char数组将中缀表达式读入，对数组中的每一个元素进行处理，区分哪些是数，哪些是运算符。
如果是数元素（或小数点元素），则利用如上算法先进行元素整合，并将整合的元素通过atof函数将char型转换成浮点型存入数栈，并将新数组初始化用来存储下一个数。
如果是索引到运算符，则要先根据当前运算符的优先级和栈里面的运算符的优先级进行处理。
如果栈内元素的优先级小于当前元素的优先级或者栈内为空，则将当前运算符入栈；如果栈内元素的优先级大于等于当前元素的，则依次出栈元素进行计算。
每次计算要在数栈出栈两个整合后的数，先出栈的数字放在运算符后面，后出栈的数字放在运算符的前面，将运算以后的结果再次存入数栈。
如果遇到左括号则无条件进栈，并只在有右括号出现的时候才有可能出栈。
如果遇到右括号，则无条件让栈内元素出栈进行计算，直到左括号出栈为止。
如此计算将表达式所有元素全部索引。
之后再对栈内剩余元素进行操作。
每在符栈出栈一个运算符，就从数栈出栈两个数进行计算，算法同上，将运算以后的结果再次存入数栈。
循环操作直到符栈栈空，此时数栈出栈元素即为最后结果。
为了方便计算，计算过程使用了函数体。
主函数只负责输入中缀表达式和输出最后的运算结果。
同时，建立了优先级函数使用了swich语句为每个运算符赋值优先级，方便在计算过程中直接调用。
也建立了运算函数对每个运算符做特定的运算，也是使用了swich语句。
另外，最后为了能够识别一些错误，在运算过程中加入了错误的判定，比如出栈时栈空或者左右符号不符等。
在编写过程中发现数栈的看栈顶没有使用过，所以删除了数栈的看栈顶。
二、算法流程图
中缀转后缀再计算的算法分两个流程，第一步是中缀表达式转换成后缀表达式；
图1中缀转后缀算法流程图
第二步是将后缀表达式进行计算输出。
图2后缀计算算法流程图
边转换边计算的算法只一个流程即可。
图3边转换边计算算法流程图
三、源代码
下面给出的是用中缀转后缀再计算的算法实现的程序的源代码：
#include<>
#include<>
#defineN100/*N为数栈和表达式数组容量*/
#defineM50/*M为符栈和其他数组容量*/
typedefstruct/*定义运算符类型，level为运算符等级*/
{
charType;
intlevel;
}Type;
typedefstruct/*定义数栈*/
{
doublestack[N];
inttop;
}OdStack;
typedefstruct/*定义符栈*/
{
Typestack[M];
inttop;
}OpStack;
voidInit_OdStack（OdStack*s）/*定义初始化数栈*/
{（*s）.top=0;}
voidOdPush（OdStack*s,doublen）/*进数栈*/
{
if（（*s）.top==N-1）/*如果栈满则报错退出程序*/
Error（）;
（*s）.stack[（*s）.top]=n;
（*s）.top++;
}
doubleOdPop（OdStack*s）/*定义出数栈*/
{
if（（*s）.top==0）/*如果栈空则报错退出程序*/
Error（）;
else
{
（*s）.top--;
return（*s）.stack[（*s）.top];
}
}
voidInit_OpStack（OpStack*s）/*定义初始化符栈*/
{（*s）.top=0;}
voidOpPush（OpStack*s,Type*sign）/*定义进符栈*/
{
if（（*s）.top==M-1）/*如果栈满则报错退出程序*/
Error（）;
（*s）.stack[（*s）.top]=*sign;
（*s）.top++;
}
TypeOpPop（OpStack*s）/*定义出符栈*/
{
if（（*s）.top==0）/*栈空则报错退出程序*/
Error（）;
else
{
（*s）.top--;
return（*s）.stack[（*s）.top];
}
}
TypeOpPeek（OpStack*s）/*定义看符栈顶*/
{
Typeren;
if（（*s）.top==0）/*判栈空，空则赋等级0值*/
{
=0;
returnren;
}
else
return（*s）.stack[（*s）.top-1];
}
intError（）/*报错函数*/
{
printf（"Error!
"）;
getch（）;
exit
（1）;
}
intCom（chartempch）/*定义运算符等级*/
{
intlevel;/*给不同运算符定级*/
switch（tempch）
{
case'+':
case'-':
level=1;break;
case'*':
case'/':
case'%':
level=2;break;
}
returnlevel;
}
doubleOper（doublea,doubleb,chartempch）/*定义运算过程*/
{
doubleren;
switch（tempch）/*对不同运算符执行运算并返回结果*/
{
case'+':
ren=b+a;break;
case'-':
ren=b-a;break;
case'*':
ren=b*a;break;
case'/':
ren=b/a;break;
case'%':
ren=（int）b%（int）a;break;/*取模运算将数取整*/
}
returnren;
}
doubleCalu（char*exp1）
{
OdStackOdStack;/*定义数栈*/
OpStackOpStack;/*定义符栈*/
Typetempsign;/*定义Type型运算符*/
charexp2[N],tempexp[M],tempch;
/*定义后缀表达式数组exp2，整合数组tempexp，tempch为运算符*/
intindex1,index2,tempindex;/*index1为主要索引，index2为次要索引，tempindex为附加索引*/
doublenumber,a,b,c;/*number为整合数，a、b、c为运算数*/
Init_OdStack（&OdStack）;/*初始化数栈*/
Init_OpStack（&OpStack）;/*初始化符栈*/
index1=0;/*初始化索引，附加索引*/
index2=0;
tempindex=0;
tempexp[0]='\0';/*初始化整合数组*/
while（exp1[index1]!
='\0'）/*处理初始表达式转化成后缀表达式*/
{
if（（exp1[index1]>='0'&&exp1[index1]<='9'））/*处理数字元素*/
{
while（（exp1[index1]>='0'&&exp1[index1]<='9'）||exp1[index1]=='.'）
{
exp2[index2]=exp1[index1];/*连续的数字元素不分开并依次存入后缀表达式*/
index2++;
index1++;
}
exp2[index2]='';/*结束后用空格将其与后面的元素分开*/
index2++;
}
else
{
if（exp1[index1]=='+'||exp1[index1]=='-'||exp1[index1]=='*'||exp1[index1]=='/'||exp1[index1]=='%'）/*处理运算符元素*/
{
=exp1[index1];
=Com;/*求运算符等级*/
while（OpPeek（&OpStack）.level>=
/*当栈中符的等级大于当前等级时则取出符存入后缀表达式*/
{
exp2[index2]=OpPop（&OpStack）.Type;
index2++;
exp2[index2]='';/*每两个运算符之间用空格分开*/
index2++;
}
OpPush（&OpStack,&tempsign）;/*结束后将当前运算符入栈*/
index1++;
}
else
{
if（exp1[index1]=='（'）/*如果是左括号则无条件进栈*/
{
=exp1[index1];
=-1;/*进栈后等级为-1，以便遇到右括号出栈*/
OpPush（&OpStack,&tempsign）;
index1++;
}
else
{
if（exp1[index1]=='）'）/*右括号规则*/
{
while（OpPeek（&OpStack）.level!
=-1）
/*遇到右括号则不断出栈存入后缀表达式直到寻到左括号*/
{
exp2[index2]=OpPop（&OpStack）.Type;
index2++;
exp2[index2]='';/*每两个运算符之间用空格分开*/
index2++;
}
OpPop（&OpStack）;/*直到遇到左括号将左括号出栈*/
index1++;
}
else/*如果输入了非法字符则报错退出程序*/
Error（）;
}
}
}
}
while（OpPeek（&OpStack）.level!
=0）/*原表达式结束后对栈进行操作直到栈空*/
{
if（OpPeek（&OpStack）.level==-1）/*如果有为用掉的左括号则报错退出程序*/
Error（）;
exp2[index2]=OpPop（&OpStack）.Type;
index2++;
exp2[index2]='';
index2++;
}
exp2[index2]='\0';/*最后结束后缀表达式*/
printf（"\nThePostExpressionis:
\n%s",exp2）;/*得到后缀表达式*/
index1=0;/*索引归零，开始计算结果*/
while（exp2[index1]!
='\0'）/*循环直到后缀表达式结束*/
{
if（（exp2[index1]>='0'&&exp2[index1]<='9'））/*整合数并入栈*/
{
while（（exp2[index1]>='0'&&exp2[index1]<='9'）||exp2[index1]=='.'）
/*用附加索引判断数的长度并整合入整合数组*/
{
tempexp[tempindex]=exp2[index1];
index1++;
tempindex++;
}
tempexp[tempindex]='\0';/*结束整合数组*/
if（tempexp[0]!
='\0'）/*如果整合数组有值则转换成浮点型存入数栈*/
{
number=atof（tempexp）;
OdPush（&OdStack,number）;
tempexp[0]='\0';/*入栈后初始化整合数组和附加索引以便下次整合*/
tempindex=0;
}
}
else
{
if（exp2[index1]==''）/*判断空格，有则跳过*/
{
while（exp2[index1]==''）
index1++;
}
else
{
if（exp2[index1]=='+'||exp2[index1]=='-'||exp2[index1]=='*'||exp2[index1]=='/'||exp2[index1]=='%'）
/*对加减乘除和取模进行运算*/
{
a=OdPop（&OdStack）;
b=OdPop（&OdStack）;
tempch=exp2[index1];
c=Oper（a,b,tempch）;
OdPush（&OdStack,c）;/*将计算结果放入数栈*/
index1++;
}
}
}
}
returnOdPop（&OdStack）;/*弹出结果*/
}
main（）
{
charstr[N];/*定义数组以存储表达式*/
doubleresult;/*定义result以存储结果*/
printf（"PleaseEntertheExpression:
\n"）;
scanf（"%s",str）;
result=Calu（str）;/*计算表达式并返回结果值*/
printf（"\nTheresultis:
\n%f",result）;
getch（）;
}
下面给出的是用边转换边运算的算法实现的程序的源代码：
#include<>
#include<>
#defineN100/*N为数栈和表达式数组容量*/
#defineM50/*M为符栈和其他数组容量*/
typedefstruct/*定义运算符类型，level为运算符等级*/
{
charType;
intlevel;
}Type;
typedefstruct/*定义数栈*/
{
doublestack[N];
inttop;
}OdStack;
typedefstruct/*定义符栈*/
{
Typestack[M];
inttop;
}OpStack;
voidInit_OdStack（OdStack*s）/*定义初始化数栈*/
{（*s）.top=0;}
voidOdPush（OdStack*s,doublen）/*进数栈*/
{
if（（*s）.top==N-1）/*如果栈满则报错退出程序*/
Error（）;
（*s）.stack[（*s）.top]=n;
（*s）.top++;
}
doubleOdPop（OdStack*s）/*定义出数栈*/
{
if（（*s）.top==0）/*如果栈空则报错退出程序*/
Error（）;
else
{
（*s）.top--;
return（*s）.stack[（*s）.top];
}
}
voidInit_OpStack（OpStack*s）/*定义初始化符栈*/
{（*s）.top=0;}
voidOpPush（OpStack*s,Type*sign）/*定义进符栈*/
{
if（（*s）.top==M-1）/*如果栈满则报错退出程序*/
Error（）;
（*s）.stack[（*s）.top]=*sign;
（*s）.top++;
}
TypeOpPop（OpStack*s）/*定义出符栈*/
{
if（（*s）.top==0）/*栈空则报错退出程序*/
Error（）;
else
{
（*s）.top--;
return（*s）.stack[（*s）.top];
}
}
TypeOpPeek（OpStack*s）/*定义看符栈顶*/
{
Typeren;
if（（*s）.top==0）/*判栈空，空则赋等级0值*/
{
=0;
returnren;
}
else
return（*s）.stack[（*s）.top-1];
}
intError（）/*报错函数*/
{
printf（"Error!
"）;
getch（）;
exit
（1）;
}
intCom（chartempch）/*定义运算符等级*/
{
intlevel;/*给不同运算符定级*/
switch（tempch）
{
case'+':
case'-':
level=1;break;
case'*':
case'/':
case'%':
level=2;break;
}
returnlevel;
}
doubleOper（doublea,doubleb,chartempch）/*定义运算过程*/
{
doubleren;
switch（tempch）/*对不同运算符执行运算并返回结果*/
{
case'+':
ren=b+a;break;
case'-':
ren=b-a;break;
case'*':
ren=b*a;break;
case'/':
ren=b/a;break;
case'%':
ren=（int）b%（int）a;break;/*取模运算将数取整*/
}
returnren;
}
doubleCalu（char*exp）/*定义计算过程，依次读入字符*/
{
OdStackOdStack;/*定义数栈*/
OpStackOpStack;/*定义符栈*/
Typetempsign;/*定义Type型运算符*/
chartempexp[M],tempch;/*定义整合数组tempexp，tempch为运算符*/
intindex,tempindex;/*index为索引，tempindex为附加索引*/
doublenumber,a,b,c;/*number为整合数，a、b、c为运算数*/
Init_OdStack（&OdStack）;/*初始化数栈*/
Init_OpStack（&OpStack）;/*初始化符栈*/
index=0;/*初始化索引，附加索引*/
tempindex=0;
tempexp[0]='\0';/*初始化整合数组*/
while（exp[index]!
='\0'）/*执行操作直到表达式结束*/
{
if（（exp[index]>='0'&&exp[index]<='9'））/*整合数并入栈*/
{
while（（exp[index]>='0'&&exp[index]<='9'）||exp[index]=='.'）
/*用附加索引判断数的长度并整合入整合数组*/
{
tempexp[tempindex]=exp[index];
index++;
tempindex++;
}
tempexp[tempindex]='\0';/*结束整合数组*/
if（tempexp[0]!
='\0'）/*如果整合数组有值则转换成浮点型存入数栈*/
{
number=atof（tempexp）;
OdPush（&OdStack,number）;
tempexp[0]='\0';/*入栈后初始化整合数组和附加索引以便下次整合*/
tempindex=0;
}
}
else
{
if（exp[index]=='+'||exp[index]=='-'||exp[index]=='*'||exp[index]=='/'||exp[index]=='%'）
/*对加减乘除和取模进行运算*/
{
=exp[index];
=Com;/*求运算符等级*/
while（OpPeek（&OpStack）.level>=
/*当栈中符的等级大于当前等级时则取出符进行运算*/
{
tempch=OpPop（&OpStack）.Type;
a=OdPop（&OdStack）;
b=OdPop（&OdStack）;
c=Oper（a,b,tempch）;
OdPush（&OdStack,c）;/*将计算结果放入数栈*/
}
OpPush（&OpStack,&tempsign）;/*直到无法运算将当前符放入栈中*/
index++;
}
else
{
if（exp[index]=='（'）/*如果是左括号则无条件进栈*
升级会员 