《数据结构课程设计_表达式求值【完整版】》由会员分享，可在线阅读，更多相关《数据结构课程设计_表达式求值【完整版】（18页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计表达式求值 第 1 页 共 18 页XXXXXX 大 学数据结构课程设计报告班级：学号：姓名：指导老师：数据结构课程设计表达式求值 第 2 页 共 18 页目 录一 算术表达式求值1、需求分析2、程序的主要功能3、程序运行平台4、数据结构5、算法及时间复杂度6、测试用例7、程序源代码二 感想体会与总结数据结构课程设计表达式求值 第 3 页 共 18 页算术表达式求值一、需求分析一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，
2、如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。二、程序的主要功能（1） 从键盘读入一个合法的算术表达式，输出正确的结果。（2） 显示输入序列和栈的变化过程。三、程序运行平台Visual C+ 6.0 版本四、数据结构本程序的数据结构为栈。（1）运算符栈部分：struct SqStack /定义栈char *base; /栈底指针char *top; /栈顶指针int stacksize; /栈的长度;int InitStack (SqStack &s) /建立一个空栈 S if (!(s.base = (char *)mal
3、loc(50 * sizeof(char)exit(0);s.top=s.base;s.stacksize=50;return OK; char GetTop(SqStack s,char &e) /运算符取栈顶元素 if (s.top=s.base) /栈为空的时候返回 ERRORprintf(运算符栈为空 !n);return ERROR;else e=*(s.top-1); /栈不为空的时候用 e 做返回值，返回 S 的栈顶元素，并返回 OK数据结构课程设计表达式求值 第 4 页 共 18 页return OK; int Push(SqStack &s,char e) /运算符入栈 if
4、 (s.top-s.base = s.stacksize) printf(运算符栈满!n); s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char) ); /栈满的时候，追加 5 个存储空间if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=5;*(s.top)+=e; /把 e 入栈return OK; int Pop(SqStack &s,char &e) /运算符出栈if (s.top=s.base) /栈为空栈的时候，返回 ERRORprintf
5、(运算符栈为空 !n);return ERROR; elsee=*-s.top; /栈不为空的时候用 e 做返回值，删除 S 的栈顶元素，并返回 OKreturn OK; int StackTraverse(SqStack &s) /运算符栈的遍历 char *t;t=s.base ;if (s.top=s.base)printf(运算符栈为空 !n); /栈为空栈的时候返回 ERRORreturn ERROR;while(t!=s.top) printf( %c,*t); /栈不为空的时候依次取出栈内元素t+;数据结构课程设计表达式求值 第 5 页 共 18 页return ERROR;（2
6、）数字栈部分：struct SqStackn /定义数栈int *base; /栈底指针int *top; /栈顶指针int stacksize; /栈的长度;int InitStackn (SqStackn &s) /建立一个空栈 Ss.base=(int*)malloc(50*sizeof(int);if(!s.base)exit(OVERFLOW); /存储分配失败s.top=s.base;s.stacksize=50;return OK; int GetTopn(SqStackn s,int &e) /数栈取栈顶元素 if (s.top=s.base) printf(运算数栈为空 !n
7、); /栈为空的时候返回 ERRORreturn ERROR;else e=*(s.top-1); /栈不为空的时候，用 e 作返回值，返回 S 的栈顶元素，并返回 OKreturn OK; int Pushn(SqStackn &s,int e) /数栈入栈if (s.top-s.base =s.stacksize)printf(运算数栈满!n); /栈满的时候，追加 5 个存储空间 s.base=(int*)realloc (s.base,(s.stacksize+5)*sizeof(int) );if(!s.base) exit (OVERFLOW);s.top=s.base+s.sta
8、cksize; /插入元素 e 为新的栈顶元素s.stacksize+=5;*(s.top)+=e; /栈顶指针变化return OK;数据结构课程设计表达式求值 第 6 页 共 18 页 int Popn(SqStackn &s,int &e) /数栈出栈if (s.top=s.base)printf( 运算符栈为空 !n); /栈为空栈的视时候，返回 ERRORreturn ERROR;elsee=*-s.top; /栈不空的时候，则删除 S 的栈顶元素，用 e 返回其值，并返回OKreturn OK; int StackTraversen(SqStackn &s) /数栈遍历 int *
9、t;t=s.base ;if (s.top=s.base)printf( 运算数栈为空 !n); /栈为空栈的时候返回 ERRORreturn ERROR;while(t!=s.top) printf( %d,*t); /栈不为空的时候依次输出t+;return ERROR;五、算法及时间复杂度1、算法：建立两个不同类型的空栈，先把一个# 压入运算符栈。输入一个算术表达式的字符串（以# 结束），从第一个字符依次向后读，把读取的数字放入数字栈，运算符放入运算符栈。判断新读取的运算符和运算符栈顶得运算符号的优先级，以便确定是运算还是把运算符压入运算符栈。最后两个#遇到一起则运算结束。数字栈顶的数字
10、就是要求的结果。2、时间复杂度：O(n)数据压缩存储栈，其操作主要有：数据结构课程设计表达式求值 第 7 页 共 18 页建立栈 int Push(SeqStack *S, char x)入栈 int Pop(SeqStack *S, char x)出栈。以上各操作运算的平均时间复杂度为 O(n)，其主要时间是耗费在输入操作。6、测试用例如图所示。最终结果如图所示：数据结构课程设计表达式求值 第 8 页 共 18 页7、源代码/*第七题 算术表达式求值问题描述一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只
11、含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#” ，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法” 求算术表达式的值。基本要求（1） 从键盘读入一个合法的算术表达式，输出正确的结果。（2） 显示输入序列和栈的变化过程。*/#include #include #include #include #include #include #define OK 1#define ERROR 0#define STACK_INIT_SIZE 100 /#define STACKINCREMENT 10/=/ 以下定义两种栈，分别存放运算符
12、和数字/=/*运算符栈部分*struct SqStack /定义栈char *base; /栈底指针char *top; /栈顶指针int stacksize; /栈的长度;int InitStack (SqStack &s) /建立一个空栈 S if (!(s.base = (char *)malloc(50 * sizeof(char)数据结构课程设计表达式求值 第 9 页 共 18 页exit(0);s.top=s.base;s.stacksize=50;return OK; char GetTop(SqStack s,char &e) /运算符取栈顶元素 if (s.top=s.base) /栈为空的时候返回 ERRORprintf(运算符栈为空 !n);return ERROR;else e=*(s.top-1); /栈不为空的时候用 e 做返回值，返回 S 的栈顶元素，并返回OKreturn OK; int Push(SqStack &s,char e) /运算符入栈 if (s.top-s.base = s.stacksize) printf(运算符栈满 !n); s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char) ); /栈满的时候，追加 5 个存储空间
