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

1、1【 实验题目及要求】 问题描述一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正实数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。基本要求（1） 从键盘或文件读入一个合法的算术表达式，输出正确的结果。（2） 显示输入序列和栈的变化过程。（3） 考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。(4) 实现非整数的处理（可选功能）。 2【源代码（C语言）】#include

2、<stdio.h>#include<stdlib.h>#include<string.h>#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 InitOptrSt

3、ack(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(

4、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("请输入表达

5、式以“#”开始，以“#”结束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 &#

6、39;<':OptrPush(&optr,ch);/栈顶优先级低ch = getchar();break;case '=':OptrPop(&optr,&noMean);/左右括号，把左括号出栈ch = getchar ();break;case '>':/栈顶优先级高 if(OpndPop(&opnd, &number2) && OpndPop(&opnd, &number1)OptrPop(&optr, &ci);num = Caculate(numb

7、er1, 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("运算结

8、果为 %.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-&

9、gt;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->t

10、op = 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.b

11、ase )return YES;elsereturn NO;int JudgeChar(char ch)if(ch >='0' && ch <= '9')return NO;elsereturn YES;float GetFloat(char* ch)int i; float num = 0;for( i = 0; *ch >= '0' && *ch <= '9' i+)num = num*10 + *ch - '0'*ch = getchar();retur

12、n num;char Precede(char a, char b)char ch; switch(a)case '+':case '-':if(b = '*' | b = '/' | b = '(')ch = '<'elsech = '>'break;case '*':case '/':if( b = '(')ch = '<'elsech = '>'break;case '

13、;(':if(b = ')')ch = '='else if(b = '#')printf("缺少反括号n");system ("PAUSE");exit(0);elsech = '<'break;case ')':if(b = '(')printf("两个括号之间没有符号相连！n");system("PAUSE");exit(0);ch = '>'break;case '#&

14、#39;: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)f

15、loat 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，对读入的字符进行判断，存入不同的栈内，每次读入一个字符就把该字符和运算符栈顶的优先级进行比较，

16、然后选择相应的操作，这是这个程序的核心代码，如下：switch(Precede(GetOptrTop(optr),ch)case '<':OptrPush(&optr,ch);/栈顶优先级低ch = getchar();break;case '=':OptrPop(&optr,&noMean);/左右括号，把左括号出栈ch = getchar ();break;case '>':/栈顶优先级高 if(OpndPop(&opnd, &number2) && OpndPop(&opnd, &number1)OptrPop(&optr, &ci);num = Caculate(number1, number2, ci