数据结构课程设计院别计算机与通信工程学院专业计算机科学与技术班级学号姓名指导教师成绩2013 年7 月18 日目录一、设计课题 (3)二、需求分析 (3)三、算法设计 (3)四、调试分析 (9)五、用户手册 (10)六、测试结果 (10)七、附录（源代码） (13)八、参考文献 (21)一、设计课题： 表达式求值 二、需求分析：当用户输入一个合法的算术表达式后，能够返回正确的结果。
能够计算的运算符包括：加、减、乘、除、括号；能够计算的操作数要求在实数范围内；对于异常表达式能给出错误提示。
三、算法设计：概要说明：为实现上述程序功能，1. 首先置操作数栈为空栈，表达式起始符＃为运算符栈的栈底元素；2. 依次扫描表达式中每个字符，若是操作数则进OPND 栈；若是运算符，则和OPTR 栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。
3. 先做一个适合个位的+-*/运算, 其次就要考虑到对n 位和小数点的运算。
模块间调用关系：调用主程序模块————>输出模块详细说明（ADT 描述） ：ADT SqStack{数据对象：D={i a |i a ∈ElemSet,i=1,2,…，n, n ≧0} 数据对象：R1={<1,-i i a a >|1-i a ,D a i ∈,i=2,…，n}约定n a 端为栈顶，i a 端为栈底。
基本操作：InitStack(&S)操作结果：构造一个空栈S 。
GetTop(S)初始条件：栈S 已存在。
操作结果：用P 返回S 的栈顶元素。
Push(&S ，e)初始条件：栈S 已存在。
操作结果：插入元素ch 为新的栈顶元素。
Pop(&S ，e)初始条件：栈S 已存在。
操作结果：删除S 的栈顶元素。
In(c)操作结果：判断字符是否是运算符，运算符即返回1。
Precede(c1, c2)初始条件：c1,c2为运算符。
操作结果：判断运算符优先权，返回优先权高的。
Operate(a,op,b)初始条件：a,b为整数，op为运算符。
操作结果：a与b进行运算，op为运算符，返回其值。
EvaluateExpression()初始条件：输入表达式合法。
操作结果：返回表达式的最终结果。
}ADT Stack流程图及主要函数模块说明:1.数据类型：typedef struct{ double *base;double *top;int stacksize;}SqStack1;typedef struct{ char *base;char *top;int stacksize;}SqStack2;2. Precede(char c1,char c2) 判断运算符优先权，返回优先权高的。
算符间的优先关系如下：算法伪代码如下：char Precede(char c1,char c2){static char array[49]={'>', '>', '<', '<', '<', '>', '>','>', '>', '<', '<', '<', '>', '>','>', '>', '>', '>', '<', '>', '>','>', '>', '>', '>', '<', '>', '>','<', '<', '<', '<', '<', '=', '!','>', '>', '>', '>', '!', '>', '>','<', '<', '<', '<', '<', '!', '='}; //用一维数组存储49种情况switch(c1){/* i为下面array的横标 */case '+' : i=0;break;case '-' : i=1;break;case '*' : i=2;break;case '/' : i=3;break;case '(' : i=4;break;case ')' : i=5;break;case '#' : i=6;break;}switch(c2){/* j为下面array的纵标 */case '+' : j=0;break;case '-' : j=1;break;case '*' : j=2;break;case '/' : j=3;break;case '(' : j=4;break;case ')' : j=5;break;case '#' : j=6;break;}return (array[7*i+j]); /* 返回运算符array[7*i+j]为对应的c1,c2优先关系*/ }3. int EvaluateExpression()主要操作函数。
算法概要流程图：利用该算法对算术表达式3*(7-2)求值操作过程如下：步骤OPTR栈OPND栈输入字符主要操作1 # 3*(7-2)# Push(OPND,’3’)2 #3 *(7-2)# Push(OPTR,’*’)3 #* 3 (7-2)# Push(OPNR,’(’)4 #*( 3 7-2)# Push(OPND,’7’)5 #*( 3 7 -2)# Push(OPNR,’-’)6 #*(- 37 2)# Push(OPND,’2’)7 #*(- 3 7 2 )# Operate(‘7’,’-’,’2’)8 #*( 3 5 )# Pop(OPTR)9 #* 3 5 # Operate(‘3’,’*’,5’)10 # 15 # Return(GetTop2(OPND))表2算法伪代码如下：Status EvaluateExpression(){//算术表达式求值的算符优先算法。
设OPTR和OPND分别为运算符栈和运算数栈，//OP为运算符集合SqStack1 OPND;SqStack2 OPTR;char c,x,theta,y,d;double a=0,b=0,k=0,z=0;InitStack1(OPND);InitStack2(OPTR);Push2(OPTR,'#');cout<<"请输入您要求解的表达式并以“#”结尾："<<endl;y=GetTop2(OPTR);c=getchar(); //printf("字符是%c\n",c);while (c!='#'||GetTop2(OPTR)!='#'){if(!In(c)){double d1=0,d2=1,e=0;// cout<<"kitty";// DealReal(OPND,c);d1=0;while(c>='0'&&c<='9'){c-='0';d1=d1*10+c;e=d1;c=getchar();}//whileif(c=='.'){c=getchar();while(c>='0'&&c<='9'){d2/=10;c-='0';e+=d2*c;c=getchar();}//while}//if//cout<<"chuliwan=="<<d1<<endl;Push1(OPND,e);// c=getchar();//printf("字符是%c\n",c);}else{y=GetTop2(OPTR);//cout<<y<<endl;d=Precede(y,c);//cout<<"this is"<<y<<" "<<d;switch(d){case'<'://栈顶元素优先权低Push2(OPTR,c);c=getchar();break;case'='://脱括号并接收下一字符Pop2(OPTR,x);c=getchar();break;case'>'://退栈并将运算结果入栈// cout<<"world"<<endl;Pop2(OPTR,theta);Pop1(OPND,b);//cout<<b<<endl;Pop1(OPND,a);Push1(OPND,Operate(a,theta,b));break;case'!':cout<<"请输入正确的表达式："<<endl;break;}//switch}}//whileGetTop1(OPND,k);cout<<"表达式结果为： "<<k<<endl;return OK;}//EvaluateExpression4. Operate为进行二元运算aθb的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算的结果。
