算术表达式求值实习报告

算术表达式求值实习报告09040502班 学号:052415 朱博凯需求分析本程序需要用户自行输入表达式（运算符可以是加（+）；减（-）；乘（*）；除（/）；幂（^）；括号（（））），数字可以是整数也可以是浮点数，并按回车键结束！程序功能：对算术表达式进行计算，输出结果，并输出其后缀表达式！测试数据：8； 1+2+3+4；88-1*3； 1024/8*16；1024/(8*16)； (22+3)*(8/2)；3-3-3； 8/(9-9)； 2*(5+3(2+4(3+6)))概要设计为实现上述程序功能，应以两个带头节点的栈分别存储表达式中的数和运算符。栈的抽象数据类型定义ADTStack{

数据对象：d={ai|ai∈elemset,i=1,2,3,……，n，n≥0}数据关系：r={<ai-1,ai,)>|ai-1,ai∈d,i=2,3,……，n} 约定a1为栈底，an为栈顶。基本操作：（1）InitStack(&S)

操作结果：构造一个空栈S。

（2）DestroyStack(&S)

初始条件：栈S已存在。

操作结果：销毁栈S。

（3）ClearStack（&S）

初始条件：栈S已存在。。

操作结果：将栈清空为空栈。

（4）StackEmpty(&S)

初始条件：栈S已存在。

操作结果：若栈S为空栈，则返回TRUE，否则FALSE。

（5）StackLength（&S）

初始条件：栈S已存在。

操作结果：返回栈的长度（或者说深度）。

（6）GetTop（S，&e）

初始条件：栈S已存在且非空。

操作结果：用e返回S的栈顶元素。

（7）Push（&S,e）

初始条件：栈S已存在。

操作结果：在栈顶插入新的元素e。

（8）Pop（&S,&e）

初始条件：栈S已存在且非空。

操作结果：删除栈S的栈顶元素，并且用e返回它的值。

（9）StackTraverse（S，visit（））

初始条件：栈S已存在。

操作结果：遍历访问栈，一次对S的每个元素调用函}ADTStack程序包括6个模块主程序模块：栈的初始化：分别初始化两个栈，一个操作数栈，一个操作符栈；栈的创建：接受数据，分别创建两个栈；输出后缀表达式；表达式计算；输出计算结果；各模块间调用关系：主程序模块初始化两个栈栈的创建输出后缀表达式表达式计算输出计算结果详细设计元素类型、结点类型typedefstruct{ char*base; char*top; intstacksize;}SqStack1; //操作符栈typedefstruct{ double*base; double*top; intstacksize;}SqStack2; //操作数栈栈的实现

typedefstruct{ char*base; char*top; intstacksize;}SqStack1;

//栈类型

栈的基本操作设置如下：

voidInitStack(Stack&S)

//初始化，设S为空栈（S.top=NULL）

voidDestroyStack(Stack&S)

//销毁栈S，并释放所占空间

voidClearStack(Stack&S)

//将S清为空栈

intStackLength(StackS)

//返回栈S的长度S.size

StatusStackEmpty(StackS)

//若S为空栈（S.top==NULL），则返回TRUE；否则返回FALSE

StatusGetTop(StackS,ElemTypee)

//若栈S不空，则以e带回栈顶元素并返回TRUE，否则返回FALSE

StatusPush(Stack&S,ElemTypee)

//若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE，

//否则返回FALSE

voidStackTraverse(StackS,Status(*visit)(ElemTypee))

//从栈底到栈顶依次对S中的每个结点调用函数visit其中部分操作的算法：

StatusPush(Stack&S,ElemTypee)

{

//若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE；

//否则栈不变，并返回FALSE

if(MakeNode(p,e)){

P.next=S.top;S.top=p;

S.size++;

ReturnTRUE;

}elsereturnFALSE;

}

StatusPop(Stack&S,ElemType&e)

{

//若栈不空，则删除S的栈顶元素并以e带回其值，且返回TRUE，

//否则返回FALSE，且e无意义

if(StackEmpty(S))returnFALSE;

else{

p=S.top;S.top=S.top->next;

e=p->:data;S.size--;

returnTRUE;

}

}主函数和其他函数的伪码voidmain() //主函数{ doubleresult; printf("*************************\n"); //程序界面 printf("*表达式计算*\n"); printf("*************************\n"); printf("请输入一组表达式(以#号结束):\n"); result=EvaluateExpression();printf("\n\n计算结果是(结果保留两位小数):%.2f\n\n\n",result); //输出计算结果}voidCHAR_InitStack(SqStack1&S) //操作符栈初始化{ S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE;}voidDOUBLE_InitStack(SqStack2&S) //操作数栈初始化{ S.base=(double*)malloc(STACK_INIT_SIZE*sizeof(double)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE;}charCHAR_GetTop(SqStack1S) //操作符栈取栈顶元素{ chare; if(S.top==S.base)return-1; e=*(S.top-1); returne; //返回栈顶元素}doubleDOUBLE_GetTop(SqStack2S) //操作数栈取栈顶元素{ doublee; if(S.top==S.base)return-1; e=*(S.top-1); returne; //返回栈顶元素}intCHAR_Push(SqStack1&S,chare) //操作符栈压栈{ if(S.top-S.base>=S.stacksize) //判断栈是否已满 { S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char)); //重新分配空间 if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return1;}intDOUBLE_Push(SqStack2&S,doublee) //操作数栈压栈{ if(S.top-S.base>=S.stacksize) //判断栈是否已满 { S.base=(double*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(double)); //重新分配空间 if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return1;}charCHAR_Pop(SqStack1&S,char&e) //操作符栈删除顶元素{ if(S.top==S.base)return-1; e=*--S.top; //栈顶指针下移 returne; //返回被删元素}doubleDOUBLE_Pop(SqStack2&S,double&e) //操作数栈删除顶元素{ if(S.top==S.base)return-1; e=*--S.top; //栈顶指针下移 returne; //返回被删元素}intIn(charc) //判断c是否为操作符{ if(c=='('||c=='+'||c=='-'||c=='*'||c=='/'||c==')'||c=='#'||c=='^') return1; //如果是操作符返回1 else return0; //不是，返回0}charPrecede(chara,charb) //比较操作符优先级{ //按照优先级表比较charop; switch(a) { case'#': if(b=='#') op='='; elseop='<'; break; case'+': if(b=='*'||b=='/'||b=='('||b=='^') op='<'; elseop='>'; break; case'-': if(b=='*'||b=='/'||b=='('||b=='^') op='<'; elseop='>'; break; case'*': if(b=='('||b=='^') op='<'; elseop='>'; break; case'/': if(b=='('||b=='^') op='<'; elseop='>'; break; case'^': if(b=='(') op='<'; elseop='>'; break; case'(': if(b==')') op='='; elseop='<'; break; case')': op='>'; break;} returnop;}doubleOperate(doubled,chare,doublef) //计算{ doubleg; switch(e) { case'+': //加法 g=d+f; break; case'-': //减法 g=d-f; break; case'*': //乘法 g=d*f; break; case'/': //除法 g=d/f; break; case'^': //幂运算 g=pow(d,f); break;} returng;}doubleEvaluateExpression() //表达式转换{ charc=0,theta,x; doublea,b,number,n=0; CHAR_InitStack(OPTR); CHAR_Push(OPTR,'#'); DOUBLE_InitStack(OPND); c=getchar(); printf("\n后缀表达式为:"); while(c!='#'||CHAR_GetTop(OPTR)!='#') { if(!In(c)) { number=0; while(!In(c)) //不是运算符则进栈 { if(c=='.') //遇到小数点则退出循环 break; number=number*10+(c-48); //处理多位整数 z=10*x+y c=getchar(); } if(c=='.') //遇到小数点 { n=1; while(!In(c=getchar())) { number=number+(c-48)*(double)pow(0.1,n); //小数点后数字的处理z=x+(0.1)*y n++; } } DOUBLE_Push(OPND,number); printf("%.2f",number); } else switch(Precede(CHAR_GetTop(OPTR),c)) { case'<': //栈顶元素优先级低 CHAR_Push(OPTR,c); c=getchar(); break; case'=': //脱括号并接收下一个字符 CHAR_Pop(OPTR,x); c=getchar(); break; case'>': //退栈并将运算结果入栈 CHAR_Pop(OPTR,theta); printf("%c",theta); DOUBLE_Pop(OPND,a); DOUBLE_Pop(OPND,b); DOUBLE_Push(OPND,Operate(b,theta,a)); break; } } return(DOUBLE_GetTop(OPND));}//intEvaluateExpression函数间调用关系mainmainEvaluateExpressionInitStackPushGetTopInPreced