数据结构课程设计-表达式求值.doc

资源描述

《数据结构》课程设计表达式求值目录 1. 课程设计的目的····························3 2. 需求分析··································3 3. 概要设计··································4 4. 详细设计··································5 5. 调试分析··································8 6. 用户手册··································9 7. 测试结果··································9 8. 程序清单···································9 9. 小结·······································13 10. 参考文献···································13 1. 课程设计的目的 1)、对数据结构基本理论和存储结构及算法设计有更加深入的理解； 2)、了解栈的特性，以便在实际问题背景下灵活运用他们； 3)、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力; 4)、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; 5)、提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 2. 需求分析编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。主要功能描述如下： ①从键盘上输入表达式; ②分析该表达式是否合法(是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中;是规定的运算符，则根据规则进行处理,在处理过程中，将计算该表达式的值;若是其它字符，则返回错误信息。 ③若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。这是一个利用栈结构完成的程序。为了实现运算符优先算法，可以使用两个栈，一个操作符栈OPTR，一个操作数栈OPND。①首先置操作数栈为空栈，表达式结束符#为操作符栈的栈底元素。②依次读入表达式中的每一个字符，若是操作数则如OPND栈；若是操作符则OPTR栈的栈顶运算符比较它们的优先级然后再做相应操作。 3、概要设计（1）主界面设计有提示表达式输入和以#结束的信息即可。如下所示：（2）存储结构设计采用顺序栈结构类型存储表达式计算中的数据，程序中应该建立两个栈，一个栈存放操作数，一个存放操作符。（3）算术优先级判断 char Precede(char op1,char op2) //操作符优先级判断处理 { if(op2=='#') return '>'; if(op1=='+' || op1=='-') { if(op2=='+' || op2=='-' || op2==')') return '>'; return '<'; } if(op1=='*' || op1=='/') { if(op2=='(') return '<'; return '>'; } if(op1=='(') { if(op2==')') return '='; return '<'; } if(op1=='#') { if(op2=='#') return '='; else return '<'; } return '>'; } 4、详细设计（1）结构定义 typedef union _Elem //栈元素类型定义，用Union可以表示运算数或运算符 { double fval; char cval; }ElemType; typedef struct _Stack //定义栈类型 { ElemType data[MAX_LENGTH]; int cur; }Stack; （2）函数定义 BOOL InitStack(Stack* T) //初始化栈 { if(T==0) return false; T->cur = 0; return true; } BOOL Push(Stack* T, ElemType e) //出栈以e返回 { if(T==0) return false; if(T->cur>=MAX_LENGTH-1) return false; T->cur ++; T->data[T->cur] = e; return true; } BOOL Top(Stack* T, ElemType* e) //以e取栈顶元素 { if(T==0 || e==0) return false; if(T->cur<0) return false; *e = T->data[T->cur]; return true; } BOOL Pop(Stack*T, ElemType* e) //出栈，以e返回 { if(T==0) return false; if(T->cur<0) return false; if(e!=0) *e = T->data[T->cur]; T->cur --; return true; } int GetLength(Stack* T) //得到栈的长度 { if(T==0) return -1; return T->cur + 1; } int IsOperator(int c) //判断是否为操作符 { if(c=='+' || c=='-' || c=='*' || c=='/' || c=='(' || c==')' || c=='#') return 1; return 0; } //读入表达式的下一项（运算数或运算符） OType ReadNextTerm(ElemType* e) { int c = getchar(); if(c==EOF) return 0; if(IsOperator(c)) { e->cval = c; printf("%c",c); return Operator; } if(isdigit(c)) { double v; ungetc(c,stdin); scanf("%lf",&v); e->fval = v; printf("%f",v); return Operand; } return Fail; } char Precede(char op1,char op2) //操作符优先级判断处理 { if(op2=='#') return '>'; if(op1=='+' || op1=='-') { if(op2=='+' || op2=='-' || op2==')') return '>'; return '<'; } if(op1=='*' || op1=='/') { if(op2=='(') return '<'; return '>'; } if(op1=='(') { if(op2==')') return '='; return '<'; } if(op1=='#') { if(op2=='#') return '='; else return '<'; } return '>'; } 5、调试分析（1）合法数据测试（2）非法数据测试（未以#结尾，便一直等待输入） 6、用户手册本程序在CodeBlock上编译，若在vc6上编译可能出现错误，表达式输入时要以#结束。界面上有提示。如上截图所示。 7、测试结果运行正常，截图如下: 8、程序清单 /*************表达式求值*******************/ #include <stdio.h> #include <math.h> #include <ctype.h> #include <stdlib.h> #define MAX_LENGTH 100//栈的最大长度 typedef enum {Fail = 0, Operator=1, Operand=2} OType; typedef enum {false=0,true=1} BOOL; typedef union _Elem //栈元素类型定义，用Union可以表示运算数或运算符 { double fval; char cval; }ElemType; typedef struct _Stack //定义栈类型 { ElemType data[MAX_LENGTH]; int cur; }Stack; BOOL InitStack(Stack* T) //初始化栈 { if(T==0) return false; T->cur = 0; return true; } BOOL Push(Stack* T, ElemType e) //出栈以e返回 { if(T==0) return false; if(T->cur>=MAX_LENGTH-1) return false; T->cur ++; T->data[T->cur] = e; return true; } BOOL Top(Stack* T, ElemType* e) //以e取栈顶元素 { if(T==0 || e==0) return false; if(T->cur<0) return false; *e = T->data[T->cur]; return true; } BOOL Pop(Stack*T, ElemType* e) //出栈，以e返回 { if(T==0) return false; if(T->cur<0) return false; if(e!=0) *e = T->data[T->cur]; T->cur --; return true; } int GetLength(Stack* T) //得到栈的长度 { if(T==0) return -1; return T->cur + 1; } int IsOperator(int c) //判断是否为操作符 { if(c=='+' || c=='-' || c=='*' || c=='/' || c=='(' || c==')' || c=='#') return 1; return 0; } //读入表达式的下一项（运算数或运算符） OType ReadNextTerm(ElemType* e) { int c = getchar(); if(c==EOF) return 0; if(IsOperator(c)) { e->cval = c; printf("%c",c); return Operator; } if(isdigit(c)) { double v; ungetc(c,stdin); scanf("%lf",&v); e->fval = v; printf("%f",v); return Operand; } return Fail; } char Precede(char op1,char op2) //操作符优先级判断处理 { if(op2=='#') return '>'; if(op1=='+' || op1=='-') { if(op2=='+' || op2=='-' || op2==')') return '>'; return '<'; } if(op1=='*' || op1=='/') { if(op2=='(') return '<'; return '>'; } if(op1=='(') { if(op2==')') return '='; return '<'; } if(op1=='#') { if(op2=='#') return '='; else return '<'; } return '>'; } int main(int argc,char* argv[]) { Stack operatorStack;//运算符栈 Stack operandStack;//运算数栈 InitStack(&operatorStack); InitStack(&operandStack); printf("\n/********************欢迎使用表达式求值程序**********************/\n\n"); printf("请输入一个算术表达式(以#结束)，如:(3+2)*4/6-3#\n"); ElemType e; e.cval = '#'; Push(&operatorStack,e); int atype = ReadNextTerm(&e); ElemType top; Top(&operatorStack,&top); while(e.cval != '#'|| top.cval!='#') { if(atype==Operator) { switch(Precede(top.cval,e.cval)) { case '<': { Push(&operatorStack,e); //将操作符压栈 atype = ReadNextTerm(&e); break; } case '>': { ElemType v1,v2; Pop(&operandStack,&v1); //将两个操作数出栈 Pop(&operandStack,&v2); Pop(&operatorStack,0); switch(top.cval) { case '+': v2.fval += v1.fval;break; case '-' : v2.fval -= v1.fval; break; case '*' : v2.fval *= v1.fval; break; case '/' : v2.fval /= v1.fval; break; } Push(&operandStack,v2);//将操作数压栈 break; } case '=': { Pop(&operatorStack,0); atype = ReadNextTerm(&e); break; } } } else { Push(&operandStack,e); //将操作数压栈 atype = ReadNextTerm(&e); } Top(&operatorStack,&top); } Top(&operandStack,&e); printf("="); printf("%f\n",e.fval); printf("谢谢使用\n"); return 0; } 9、小结通过对本程序的编写，我对栈的应用更加的了解了，同时又是对原来知识的一种温习、巩固和提高。是将理论化为实践的一个过程。虽然设计的过程中吃了不少苦，但是我觉得这一切都是值得的。设计时使我充分认识到了自己的不足，完成后的成就感又大大增加了我的自信心。 10、参考文献严蔚敏，吴伟民编著. 数据结构(C 语言版)-- 清华大学出版社；严蔚敏，吴伟民米宁编著. 数据结构题集(C 语言版)-- 清华大学出版社；参考以前数据结构课上老师讲解的四则运算程序。

展开阅读全文