表达式求值

数据结构课程设计 院 别 计算机与通信工程学院 专 业 计算机科学与技术 班级学号 姓 名 指导教师 成 绩 2013 年 7 月 18 日 目录 一、设计课题 3 二、需求分析 3 三、算法设计 3 四、调试分析 9 五、用户手册 10 六、测试结果 10 七、附录（源代码） 13 八、参考文献 21 设计课题： 表达式求值 二、需求分析： 当用户输入一个合法的算术表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的操作数要求在实数范围内；对于异常表达式能给出错误提示。 算法设计： 概要说明：为实现上述程序功能， 1. 首先置操作数栈为空栈，表达式起始符＃为运算符栈的栈底元素； 2. 依次扫描表达式中每个字符，若是操作数则进OPND栈；若是运算符，则 和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。 3. 先做一个适合个位的+-*/运算, 其次就要考虑到对n位和小数点的运算。 模块间调用关系： 调用 主程序模块————>输出模块 详细说明（ADT描述） ： ADT SqStack{ 数据对象：D={ | ∈ElemSet,i=1,2,…，n, n≧0} 数据对象：R1={< >| , ,i=2,…，n} 约定 端为栈顶， 端为栈底。 基本操作： 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 流程图及主要函数模块说明: 数据类型： typedef struct { double *base; double *top; int stacksize; }SqStack1; typedef struct { char *base; char *top; int stacksize; }SqStack2; 2. Precede(char c1,char c2) 判断运算符优先权，返回优先权高的。 算符间的优先关系如下： + - * / ( ) # + > < < < < > > - > > < < < > > * > > > > < > > / > > > > < > > ( < < < < < = ) > > > > > > # < < < < < = 表 1 算法伪代码如下： 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 #*(- 3 7 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<<"请输入您要求解的表达式并以“#”结尾："<='0'&&c<='9') { c-='0'; d1=d1*10+c; e=d1; c=getchar(); }//while if(c=='.') { c=getchar(); while(c>='0'&&c<='9') { d2/=10; c-='0'; e+=d2*c; c=getchar(); }//while }//if //cout<<"chuliwan=="<'://退栈并将运算结果入栈 // cout<<"world"< #include #include #include using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int Status; typedef struct { double *base; double *top; int stacksize; }SqStack1; typedef struct { char *base; char *top; int stacksize; }SqStack2; Status InitStack1(SqStack1 &S) { S.base=(double *)malloc(STACK_INIT_SIZE*sizeof(double)); if(!S.base) exit (OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }//InitStack1 Status InitStack2(SqStack2 &S) { S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char)); if(!S.base) exit (OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }//InitStack2 Status GetTop1(SqStack1 S,double &e) { //若栈不空，则用e返回S的栈顶元素，并返回OK;否则返回ERROR if(S.top==S.base) return ERROR; e= *(S.top-1); //返回栈顶元素 return OK; }//GetTop1 char GetTop2(SqStack2 S) { //若栈不空，则用e返回S的栈顶元素，并返回OK;否则返回ERROR if(S.top==S.base) { //cout<<"aaa"; return ERROR;} char e= *(S.top-1); //返回栈顶元素 //cout<=S.stacksize) //栈满，追加存储空间 { S.base=(double*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(float)); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; }//if *S.top++=e; return OK; }//Push1 Status Push2(SqStack2 &S,char e) { //插入元素e为新的栈顶元素 if(S.top-S.base>=S.stacksize) //栈满，追加存储空间 { S.base=(char*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char)); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; }//if *S.top++=e; return OK; }//Push2 Status Pop1(SqStack1 &S,double &e) { //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if(S.top==S.base) {//cout<<"aaaa"; return ERROR; } e=*--S.top; //cout<<"this is"<','>','<','<','<','>','>', '>','>','<','<','<','>','>', '>','>','>','>','<','>','>', '>','>','>','>','<','>','>', '<','<','<','<','<','=','!', '>','>','>','>','!','>','>', '<','<','<','<','<','!','='}; switch(ch1) { //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(ch2) { //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]);//返回运算符 } double Operate(double a,char theta,double b) { switch(theta) { case'+':return(a+b);break; case'-':return(a-b);break; case'*':return(a*b);break; case'/':return(a/b);break; default: cout<<"输入错误！";return ERROR;break; } } /*Status DealReal(SqStack1 &S,char a) { //数字字符则进行处理并入栈 //cout<<"this a=="<='0'&&a<='9') { a-='0'; d1=d1*10+a; }//while if(a=='.') { a=getchar(); while(a>='0'&&a<='9') { d2/=10; a-='0'; d1+=d2*a; }//while }//if //cout<<"chuliwan=="<='0'&&c<='9') { c-='0'; d1=d1*10+c; e=d1; c=getchar(); }//while if(c=='.') { c=getchar(); while(c>='0'&&c<='9') { d2/=10; c-='0'; e+=d2*c; c=getchar(); }//while }//if //cout<<"chuliwan=="<'://退栈并将运算结果入栈 // cout<<"world"<