数据结构课程设计之算术表达式求值.doc

1【 实验题目及要求】 问题描述一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正实数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。基本要求（1） 从键盘或文件读入一个合法的算术表达式，输出正确的结果。（2） 显示输入序列和栈的变化过程。（3） 考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。(4) 实现非整数的处理（可选功能）。 2【源代码（C语言）】#include#include#include#define MAXSIZE 20#define OK 1#define ERROR 0#define OVERLOW 0#define YES 1#define NO 0typedef structchar * base;char * top;int stacksize;/最大存储量OPTR;/字符存储栈typedef structfloat *base;float *top;int stacksize;/最大存储量OPND;/数值存储栈int InitOptrStack(OPTR *);/字符栈初始化函数int OptrPush(OPTR *, char);/进字符栈操作int OptrPop(OPTR*, char *);/出字符栈操作int OptrEmpty(OPTR );/判断字符栈是否为空char GetOptrTop(OPTR);/返回字符栈顶元素int InitOpndStack(OPND *);/数值栈初始化函数int OpndPush(OPND *, float);/进数值栈操作int OpndPop(OPND*, float*);/出数值栈操作int OpndEmpty(OPND );/判断数值栈是否为空int JudgeChar(char);/判断是否为字符float GetFloat(char *);/接收一个数字char Precede(char, char);/判断优先级操作float Caculate(float,float,char);/计算数值void main()char ch, noMean, ci;float num, number1, number2;OPTR optr;OPND opnd;/system(color 30);InitOptrStack(&optr);InitOpndStack(&opnd);while(1)printf(请输入表达式以“#”开始，以“#”结束n);doch = getchar();while(ch !=#);/忽略前面非#字符OptrPush(&optr, ch);ch = getchar();while(ch != # | GetOptrTop(optr) != #)if(!JudgeChar(ch)/如果输入的是数字num = GetFloat( &ch );OpndPush(&opnd, num);else/输入的是字符switch(Precede(GetOptrTop(optr),ch)case :/栈顶优先级高 if(OpndPop(&opnd, &number2) & OpndPop(&opnd, &number1)OptrPop(&optr, &ci);num = Caculate(number1, number2, ci );/出栈计算OpndPush(&opnd, num);elseprintf(输入过多运算符！n);system (PAUSE);exit(0);break;/witch/elseif(opnd.top -opnd.base = 2)printf(俩个括号之间缺少运算符！n);system (PAUSE);exit( 0 );OpndPop(&opnd,&num);/直接把OPND的栈元素赋值给 numprintf(运算结果为 %.3fn, num);system (PAUSE);int InitOptrStack(OPTR * OP)OP-base = (char*)malloc(MAXSIZE+1)*sizeof(char);OP-top = OP-base;OP-stacksize = MAXSIZE;return OK;int OptrPush(OPTR *OP, char ch)*(OP-top) = ch;OP-top+;return OK;int OptrPop(OPTR *OP, char *ch)if(OP-base = OP-top)return ERROR;elseOP-top-;*ch = *(OP-top);return OK;int OptrEmpty(OPTR OP)if(OP.top = OP.base )return YES;elsereturn NO;char GetOptrTop(OPTR OP)return *(OP.top -1);int InitOpndStack(OPND * OP)if(!(OP-base = (float*)malloc(MAXSIZE+1)*sizeof(float)exit(OVERLOW);OP-top = OP-base;OP-stacksize = MAXSIZE;return OK;int OpndPush(OPND *OP, float number)*(OP-top) = number;OP-top+;return OK;int OpndPop(OPND *OP, float* number)if(OP-top = OP-base)return ERROR;elseOP-top-;*number = *(OP-top);return OK;int OpndEmpty(OPND OP)if(OP.top = OP.base )return YES;elsereturn NO;int JudgeChar(char ch)if(ch =0 & ch = 0 & *ch = 9; i+)num = num*10 + *ch - 0;*ch = getchar();return num;char Precede(char a, char b)char ch; switch(a)case +:case -:if(b = * | b = / | b = ()ch = ;break;case *:case /:if( b = ()ch = ;break;case (:if(b = )ch = =;else if(b = #)printf(缺少反括号n);system (PAUSE);exit(0);elsech = ;break;case #:if(b = #)ch = =;else if(b = )printf(没有左括号！n);system(PAUSE);exit(0);elsech = ;break;default:printf(输入运算符超出范围!n);system (PAUSE);exit(0);break;return ch;float Caculate(float number1, float number2, char ci)float num;switch( ci)case +:num = number1 + number2;break;case -:num = number1 - number2;break;case *:num = number1 * number2;break;case /:num = number1 / number2;break;return num;3【算法思想】根据栈的原理，建立数字栈OPND和运算符号栈OPTR，对读入的字符进行判断，存入不同的栈内，每次读入一个字符就把该字符和运算符栈顶的优先级进行比较，然后选择相应的操作，这是这个程序的核心代码，如下：switch(Precede(GetOptrTop(optr),ch)case :/栈顶优先级高 if(OpndPop(&opnd, &number2) & OpndPop(&opnd, &number1)OptrPop(&optr, &ci);num = Caculate(number1, number2, ci );/出栈计算OpndPush(&opnd, num);elseprintf(输