C语言表达式求值Word下载.docx
- 文档编号:6409341
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:20
- 大小:99.01KB
C语言表达式求值Word下载.docx
《C语言表达式求值Word下载.docx》由会员分享,可在线阅读,更多相关《C语言表达式求值Word下载.docx(20页珍藏版)》请在冰点文库上搜索。
算符优先关系矩阵
+
-
*
/
(
)
#
>
<
=
3、算符表示
为了使算符与优先关系矩阵的行列号对应,把表达式中可能有的算符放入一维数组中,可以用字符在一维数组中的下标作为字符的标识码。
本计算中,算法表示如下:
一
0123456
即用0表示算符“+”,用1表示算符“一”,等。
定义的字符数组为:
chara[]={'
+'
'
-'
*'
7'
('
)'
#'
};
4、优先关系矩阵的表示
大于关系用1表示
小于关系用一1表示
等于关系用0表示
若两个算符间不存在关系,则用一个特定的数值表示,如用整数的上限值32767表示,
可定义一个宏常量来表示:
#defineNO32767
则其优先关系矩阵为:
intPriorityTable[7][7]={{1,1,-1,-1,-1,1,1},
{1,1,-1,-1,-1,1,1},
{1,1,1,1,-1,1,1},
{-1,-1,-1,-1,-1,0,NO},
{1,1,1,1,NO,1,1},
{-1,-1,-1,-1,-1,NO,0}
5、算术表达式求值算法的实现原理
处理过程:
设置两个栈:
操作数栈OPND^运算符栈OPTR
1、首先置操作数栈为空栈,把“#”移进运算符栈(实际放入栈中的是字符“#”在
字符数组中的下标,对其它算符也是一样)。
2、从左至右扫描表达式,凡遇到操作数一律进OPN[栈;
若遇到运算符,则把栈顶
运算符与扫描运算符的优先数进行比较:
若
-1:
扫描运算符进OPTF栈
0:
若“(”和“)”,栈顶符号出栈;
若为#,运算结束。
1:
取OPN[栈顶操作数与OPTF栈顶算符进行运算,参与运算的操作数和
运算符出栈,运算结果进OPN[栈
NO:
表示表达式有错。
若表达式处理完,OPTF栈为#,OPN[栈中只剩一项,表示表达式的运算结果,则分析
成功。
若达不到这种状态,表明表达式有错。
五、实现
1、数据存储结构
假设一个表达式不可能很长,如不超过屏幕上一行的宽度(80个字符),在对表达式处理之前先把表达式放入一个一维字符数组中,用户可以不输入表达式前后的“#”,由处理程序自动加入。
由于表达式的长度有限,运算符栈和操作数栈的长度野优先,假定不超过20,所以都
采用顺序存储结构比较合适。
用C语言可定义如下:
#defineEXPLENGT100
#defineSTACKSIZE20
charexpr[EXPLENGT];
intOPTR[STACKSIZE];
//运算符栈,元素为运算符对应的整数编码
doubleOPND[STACKSIZE];
//操作数栈,元素为表达式中的运算数据
2、运算符宏定义
为了判断运算符的方便,增强程序的可读性,定义如下宏常量:
#definePLUS0
//
运算符+
#defineMINUS1
运算符-
#definePOWER2
运算符*
#defineDIVIDE3
运算符/
#defineLEFTP4
运算符(
#defineRIGHP5
运算符)
#defineSTARTEND6
运算符#
#defineDIGIT7
数字字符
#definePOINT8
小数点
3、基本功能
(1)输入算术表达式
(2)计算表达式的值
4、辅助功能
(1)菜单选择
(2)获取字符类型编码
5、程序结构
2个。
该程序由5个函数组成,其中主函数1个,基本功能函数2个,辅助功能函数
函数间的调用关系图1所示。
图1程序结构图
6、函数说明
(1)主函数main
功能:
根据菜单选择确定要操作的内容:
表达式输入
表达式计算
计算结果输出
退出系统
格式:
voidInputExpression(charstr[])
参数:
charstr[]—存放输入的表达式返回值:
无
(4)表达式计算函数:
excute
功能:
完成表达式的计算
intexcute(char*str,double*Result)参数:
char*str—要计算的表达式字符串double*Result—计算结果值返回值:
1—计算成功
0—计算失败
(5)确定当前字符类型函数:
GetCharType功能:
确定当前要处理的字符的类型格式:
intGetCharType(charch)参数:
charch—当前要处理的字符返回值:
若为算符,返回字符的编码(一维数组下标)若为数字,返回符号常熟DIGIT(数字)若为小数点,返回符号常熟POINT(小数点)
若不是定义的表达式的字符,返回-1。
六、算法描述
1、表达式计算算法描述
设栈顶指针:
inttopTr—运算符栈顶指针topNd—操作数栈顶指针
表达式字符指针:
intpp—指向表达式中当前要处理的字符开始时,把表达式开始符“#”(编码)放入栈中。
设当前要处理的字符类型为CharType。
以当前要处理的字符为参照来确定下一步要作
的处理:
•若当前字符为非法字符:
则结束处理,返回出错标志(0);
•若当前字符是数字:
表示遇到表达式中的操作数,则识别出该操作数;
•若当前字符是小数点:
表示遇到以小数点开头的操作数,则识别出该操作数;
•若当前字符是+、-、*、/运算符:
则用栈顶运算符与当前运算符比较优先性:
若对应的数组元素为-1,则当前运算符(运算符编码)进栈,调整pp指向下
一个字符。
若对应的数组元素为1,则取运算符栈顶运算符和操作数栈顶操作数进行运算,参与运算的运算符和操作数出栈,运算结果进操作数栈。
实现为:
OPND[topNd-2]=OPND[topNd-2]opOPBD[topNd-1];
topNd--;
topTr--;
•若当前字符是左括号(:
则左括号进栈,pp指向下一个字符
•若当前字符是右括号):
O若栈顶是左括号,则左括号出栈,pp指向下一个字符
O若栈顶是运算符,则取运算符栈顶运算符和操作数栈顶操作数进行运算,参
与运算的运算符和操作数出栈,运算结果进操作数栈。
topNd--;
topTr--;
重复该操作,直到栈顶出现左括号“(”。
O若栈顶是#,则左括号和右括号不配对,结束处理,返回出错标志(0)
•若当前字符为#:
依次从运算符栈取出运算符和从操作数栈取出操作数进行计算,直到运算符栈的栈顶为#为止。
若运算符栈顶为#,当前字符也为#,则表达式计算结束,返回计算结果值和计算成功标志
(1)。
2、字符型数字常数转换为数值型常数的方法因为程序处理的表达式是以字符串形式出现的,表达式中每个数值型常数也是有一个一个的数字字符组成。
处理程序必须把字符串形式的常数转换为数值形式的常数。
(1)整数的转换方法我们知道,一个数值型常数3256可以表示为:
3256=((3*10+2)*10+5)*10+6
相应的,一个字符串型的数字常数“3256”转换为数值型常数可以表示为:
(((‘3'
-48)*10+(‘2'
-48))*10+(‘5'
-48))*10+(‘6'
-48)
每个字符的ASCII码指减去48就是该字符对应数字值。
实现方法:
依次读入数字字符,用前面读入子字符串对应的数值型值乘以10,再加上
当前字符的数字值,就是当前读入子字符串对应的数值型值。
用C语言描述如下:
number=0;
while(str[pp]>
='
0'
&
&
str[pp]<
9'
{number=number*10+(str[pp]-48);
pp++;
}
(2)小数的转换方法
一个小数常数0.2345可以表示为:
0.2345=2/10+3/100+4/1000+5/10000相应的,一个字符串表示的小数“0.2345”转换为数值型小数可以表示为:
“0.2345”=(‘2'
-48)/10+(‘3'
-48)/100+(‘4'
-48)/1000+(‘5'
-48)/10000假设当前字符指针指向小数点字符,转换方法描述为:
temp=10.0;
{number=number+(str[pp]-48)/temp;
temp=temp*10;
(3)既有整数又有小数部分的实数的转换算法综合前面两部分算法,既有整数又有小数部分的实数的转换算法描述如下:
number=0;
)//处理实数的整数部分
if(str[pp]=='
.'
)//遇到小数点
{temp=10.0;
)//处理实数的小数部分
七、思考题
1、若表达式中的数据带有正负号的实数字符串该怎样进行转换?
2、对于指数形式的实数字符串该怎样进行转换?
八、部分函数代码
#include<
stdio.h>
#include<
string.h>
conio.h>
#defineDIGIT7#definePOINT8
#defineNUM7#defineNO32767#defineSTACKSIZE20//运算符
/'
//优先关系矩阵,规定:
=为0,>
为1,<
为-1,空为NOintPriorityTable[7][7]={{1,1,-1,-1,-1,1,1},
{1,1,-1,-1,-1,1,1},
{1,1,1,1,-1,1,1},{1,1,1,1,-1,1,1},
{-1,-1,-1,-1,-1,0,NO},{1,1,1,1,NO,1,1},{-1,-1,-1,-1,-1,NO,0}
intmenu(void);
/*{intn;
printf("
\n\n"
);
MENU\n"
********************************************\n"
operations\n"
1.
2.
3.
4.
输入表达式\n"
计算表达式\n"
输出计算结果\n"
退出\n"
choice(1,2,3,4):
"
scanf("
%d"
&
n);
returnn;
}*/
/***************************/
/***************************/voidInputExpression(charstr[])
{intlen;
Inputexpressionstring:
\n"
scanf("
%s"
str);
len=strlen(str);
str[len]='
;
str[len+1]='
\0'
/*确定当前字符类型*/
/*************************************************/intGetCharType(charch){inti;
for(i=0;
i<
NUM;
i++)if(ch==a[i])return(i);
if(ch>
ch<
)return(DIGIT);
if(ch=='
)return(POINT);
return(-1);
/*************************************************/
intEXCUTE(char*str,double*Result)
doublenumber,temp,OPND[STACKSIZE];
OPTR[0]=STARTEND;
topTr=1;
topNd=0;
pp=0;
while((str[pp]))
{CharType=GetCharType(str[pp]);
//确定字符类型
switch(CharType)
{case-1:
//不是表达式中的字符,表达式有错
return(0);
caseDIGIT:
//
数字字符,实数的开始字符
)//
pp++;
temp=temp*10;
OPND[topNd]=number;
topNd++;
break;
casePOINT:
//小数点,以小数点开头的实数number=0;
casePLUS:
//+
处理实数的整数部分
处理实数的小数部分
caseMINUS:
//-
casePOWER:
//*
caseDIVIDE:
///
while(PriorityTable[OPTR[topTr-1]][CharType]==1){
if(OPTR[topTr-1]==PLUS)number=OPND[topNd-2]+OPND[topNd-1];
elseif(OPTR[topTr-1]==MINUS)number=OPND[topNd-2]-OPND[topNd-1];
elseif(OPTR[topTr-1]==POWER)
number=OPND[topNd-2]*OPND[topNd-1];
elseif(OPTR[topTr-1]==DIVIDE)
number=OPND[topNd-2]/OPND[topNd-1];
OPND[topNd]=number;
returnnumber;
OPTR[topTr]=CharType;
topTr++;
caseLEFTP:
//(
OPTR[topTr]=LEFTP;
caseRIGHP:
//)
while(OPTR[topTr-1]!
=LEFTP)
{
if(OPTR[topTr-1]==PLUS)
number=OPND[topNd-1]+OPND[topNd-2];
elseif(OPTR[topTr-1]==MINUS)
{number=OPND[topNd-2]-OPND[topNd-1];
{number=OPND[topNd-2]*OPND[topNd-1];
elseif(OPTR[topTr-1]==DIVIDE)
{number=OPND[topNd-2]/OPND[topNd-1];
caseSTARTEND:
//遇到表达式结束符while(OPTR[topTr-1]!
=STARTEND){
number=OPND[topNd-2]-OPND[topNd-1];
if(topNd==1)
{*Result=OPND[0];
return
(1);
elsereturn(0);
voidmain()
{intnum,flag;
doubleresult;
charstr[256];
str[0]=0;
while
(1)
{num=menu();
switch(num){
case1:
//输入表达式InputExpression(str);
flag=0;
printf("
%s\n"
getchar();
break;
case2:
//计算表达式if(str[0]==0)
{printf("
ExpressonisEmpty!
}if(!
EXCUTE(str,&
result))
Theexpressionhaserror!
}else
{printf(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 表达式 求值