用到的是算符优先法的思想,现摘自严蔚敏的数据结构(C语言版)的3.2.5章来详细说明算符优先法的思想:
(摘抄结束)
我给出的计算器功能有:支持欧拉数e,支持圆周率pi,支持运算符=,-,,/,求幂符号^,阶乘!,正弦sin,余弦cos,正切tan,以10为底的对数函数lg,以欧拉数为底的对数函数ln,优先级表为:(!表示不合法)
#include
#include
#include
#include
#include
//引用请注明出处:http://hi.baidu.com/liangxiaowen1989/blog/item/af972310f7119670ca80c413.html
#defineMAX_TOKEN_LEN100//标记最大长度
#defineEXPR_INCREMENT20//表达式长度的增量
typedefstruct{
doubleopnd;//操作数
charoptr[11];//运算符
intflag;//若为1,则为单目运算符,2则是双目运算符
}SElemType;//栈元素类型
typedefstructSNode{//栈
SElemTypedate;
structSNodenext;
}SNode,Stack;
struct{//用来存储一个操作数或运算符
charstr[MAX_TOKEN_LEN];
inttype;//类型,若为0,则为操作数,若为1则为运算符
}token;
struct{//expression,用来存储表达式
charstr;
intcur;//标记读取expr的当前位置
}expr;
StackOPND,OPTR;//操作数栈operand,运算符栈operator
intexpr_size;//表达式长度
voidInitStack(StackS){//初始化栈
S=(Stack)malloc(sizeof(SNode));
if(!(S)){
printf("动态申请内存失败!\n");
exit(0);
}//if
(S)->next=NULL;
}//InitStack
voidDestroyStack(StackS){//销毁栈
SNodep;
while(p=S){
S=p->next;
free(p);
}//while
}//DestroyStack
voidPush(StackS,SElemTypee){//入栈
SNodep;
p=(SNode)malloc(sizeof(SNode));
if(!p){
printf("动态申请内存失败!\n");
exit(0);
}//if
strcpy(p->date.optr,e.optr);
p->date.opnd=e.opnd;
p->date.flag=e.flag;
p->next=S->next;
S->next=p;
}//Push
voidPop(StackS,SElemTypee){//出栈
SNodep;
p=S->next;
if(!p){
printf("栈为空,不能出栈!\n");
exit(0);
}//if
S->next=p->next;
strcpy(e->optr,p->date.optr);
e->opnd=p->date.opnd;
e->flag=p->date.flag;
free(p);
}//Pop
voidget_expr(){//获取expr字符串
charp;
intsize;
expr.cur=0;
expr_size=100;
expr.str=(char)malloc(expr_sizesizeof(char));
if(!expr.str){
printf("内存分配失败!\n");
exit(0);
}//if
size=0;
p=expr.str;
while((p=getchar())!=''\n''){
if(p!=''www.huisheliren.com''){
if((p>=''A'')&&(p<=''Z'')){
p=p+32;//将大写转换成小写
}//if
p++;
size++;
if(size==expr_size-1){//此时expr.str已满,将其扩大
expr_size+=EXPR_INCREMENT;
expr.str=(char)realloc(expr.str,expr_sizesizeof(char));
if(!expr.str){
printf("内存分配失败!\n");
exit(0);
}//if
p=&expr.str[size];//realloc后需重新指定p
}//if
}//if
}//while
p++=''#'';
p=''\0'';
}//get_expr
intIsOpnd(charch){//判断ch是否是操作数的一部分
if((ch>=''0'')&&(ch<=''9'')||(ch==''.'')){
return1;
}//if
if((ch==''-'')||(ch==''+'')){//如若+-前面是''#''或''('',则为正负号
if((expr.cur==0)||(expr.str[expr.cur-1]==''('')){
return1;
}//if
}//if
return0;
}//IsOpnd
voidgettoken(){//获取一个标记
charp=token.str;
p=expr.str[expr.cur];
if(IsOpnd(p)){
while(IsOpnd(++p=expr.str[++expr.cur]));//注意是分号结尾
p=''\0'';
token.type=0;//将标记类型设定为操作数
return;
}//if
if((p>=''a'')&&(p<=''z'')){//接收sin,tan,ln之类的函数运算符或操作数
while((expr.str[expr.cur+1]>=''a'')&&(expr.str[expr.cur+1]<=''z'')){
++p=expr.str[++expr.cur];
}//while
}//if
++expr.cur;
++p=''\0'';
if(!strcmp(token.str,"e")){//e为欧拉数,既自然对数的底数
sprintf(token.str,"%.16g",exp(1));//springf是库函数,功能是将显示在屏幕上的内容储存在字符串中
token.type=0;
return;
}//if
if(!strcmp(token.str,"pi")){//pi为圆周率
//sprintf(token.str,"%.16g",exp(1));//springf是库函数,功能是将显示在屏幕上的内容储存在字符串中
strcpy(token.str,"3.1415926535897932");
token.type=0;
return;
}//if
token.type=1;//将标记类型设定为运算符
}//gettoken
charPrecede(SElemTypeoptr1,SElemTypeoptr2){//返回优先关系
charstr1,str2;
str1=optr1->optr;
str2=optr2->optr;
if(!strcmp(str1,"ln")||!strcmp(str1,"lg")||!strcmp(str1,"sin")||!strcmp(str1,"cos")||!strcmp(str1,"tan")){
optr1->flag=1;//这些均为单目运算符
return(!strcmp(str2,"(")||!strcmp(str2,"^")||!strcmp(str2,"!"))?''<'':''>'';
}//if
if(!strcmp(str1,"!")){
optr1->flag=1;
return''>'';
}//if
optr1->flag=2;
switch(str1[0]){
case''+'':case''-'':return(!strcmp(str2,"+")||!strcmp(str2,"-")||!strcmp(str2,")")||!strcmp(str2,"#"))?''>'':''<'';
case'''':case''/'':return(!strcmp(str2,"+")||!strcmp(str2,"-")||!strcmp(str2,"")||
!strcmp(str2,"/")||!strcmp(str2,")")||!strcmp(str2,"#"))?''>'':''<'';
case''('':return!strcmp(str2,")")?''='':''<'';
case'')'':return''>'';
case''^'':return(!strcmp(str2,"(")||!strcmp(str2,"!")||!strcmp(str2,"^"))?''<'':''>'';
case''#'':return!strcmp(str2,"#")?''='':''<'';
}//switch
}//Precede
longfactorial(longn){//阶乘
return(n<=1)?1:nfactorial(n-1);
}//factorial
SElemTypeOperate(SElemTypeopnd1,SElemTypeoptr,SElemTypeopnd2){//计算
SElemTypetemp;
if(optr.flag==1){
if(!strcmp(optr.optr,"!"))temp.opnd=factorial((long)opnd2.opnd);
elseif(!strcmp(optr.optr,"lg"))temp.opnd=log10(opnd2.opnd);
elseif(!strcmp(optr.optr,"ln"))temp.opnd=log(opnd2.opnd);
elseif(!strcmp(optr.optr,"sin"))temp.opnd=sin(opnd2.opnd);
elseif(!strcmp(optr.optr,"cos"))temp.opnd=cos(opnd2.opnd);
elseif(!strcmp(optr.optr,"tan"))temp.opnd=tan(opnd2.opnd);
returntemp;
}//if
switch(optr.optr[0]){
case''+'':temp.opnd=opnd1.opnd+opnd2.opnd;break;
case''-'':temp.opnd=opnd1.opnd-opnd2.opnd;break;
case'''':temp.opnd=opnd1.opndopnd2.opnd;break;
case''/'':temp.opnd=opnd1.opnd/opnd2.opnd;break;
case''^'':temp.opnd=pow(opnd1.opnd,opnd2.opnd);
}//switch
returntemp;
}//Operate
intmain(){
SElemTypeoptr,opnd1,opnd2;
printf("\n欢迎使用简易科学计算器!\n");
printf("欧拉数为e,圆周率为pi,退出则输入quit!\n");
printf("优先级:括号高于''!''高于''^''高于lg,ln,sin,cos,tan高于,/高于+,-\n");
printf("请输入计算表达式:\n\n");
while(1){
get_expr();
if(!strcmp(expr.str,"quit#")){
return0;
}//if
InitStack(&OPTR);
InitStack(&OPND);
strcpy(optr.optr,"#");
Push(OPTR,optr);
gettoken();//从expr.str中获取一个标记(操作数或运算符)
while(strcmp(token.str,"#")||strcmp(OPTR->next->date.optr,"#")){
if(token.type){//说明token存储的是运算符
strcpy(optr.optr,token.str);
switch(Precede(&(OPTR->next->date),&optr)){
case''<''://栈顶元素优先权低
strcpy(optr.optr,token.str);
Push(OPTR,optr);
gettoken();
break;
case''=''://脱括号并接收下一字符
Pop(OPTR,&optr);
gettoken();
break;
case''>''://退栈并将运算结果入栈
Pop(OPTR,&optr);
Pop(OPND,&opnd2);
if(optr.flag==2){//是双目运算符才需另一个操作符
Pop(OPND,&opnd1);
}//if
Push(OPND,Operate(opnd1,optr,opnd2));
}//switch
}//if
else{//说明token存储的是操作数
opnd1.opnd=atof(token.str);
Push(OPND,opnd1);//atof将token.str转换为双精度数
gettoken();//获取下一个标记
}//else
}//while
printf("%.16g\n\n",OPND->next->date.opnd);
free(expr.str);
DestroyStack(&OPTR);
DestroyStack(&OPND);
}//while
free(expr.str);
return0;
}//main
//实例测试:23.243(5-(2-13/.23)/(2-9.235)-((4-20)/2)-32(3+2.23/(23)))
//标准答案为:-2380.7610725282693238114006817341
//实例测试2:23.243(5-(2!-13/0.23)/(2!-9.235)-((4!-20)!/2!)-32(3!+2.23/(23)!))
//答案:-4802.8159654171577130910009145737
//实例测试3:23.243(5^(4+2!)-(2!^2-13/0.23)/(2^4!-9.235)-((4!-20)!/2!)-32(3!^2!+2.23/(23)!))
//答案:336114.71943320758873596787452698
|
|