算术表达式求值.docx

数据结构实验报告实验内容：算术表达式求值班 级：计算机1203班成 员：黄健 20123871尹东辉 20123880张新华 20123884数据结构实验报告一课题概述1二概要设计原理1三详细程序清单及注释说明1四运行与测试及结果5五心得体会6六参考文献66一课题概述1.实验目的：栈和队列应用类实验题目参考2.实验内容：算术表达式求值 【问题描述】 由输入的四则算术表达式字符串，动态生成算术表达式所对应的后缀式，通过后缀式求值并输出。【实验要求】 设计十进制整数四则运算计算器。 （1）采用顺序栈等数据结构。可以将数据存储在顺序表中。 （2）给定表达式字符串，后缀表达式。 （3）对后缀表达式求值并输出。二概要设计原理1. 数据结构设计任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。2. 算法设计为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR，用以寄存运算符，另一个称做OPND，用以寄存操作数或运算结果。（1）首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；（2）依次读入表达式，若是操作符即进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕三详细程序清单及注释说明#include#include#include#include#define STACK_INIT_SIZE 100;typedef structint *base;int *top;int stacksize;SqStack1;typedef structchar *base;char *top;int stacksize;SqStack2;SqStack1 OPND;/运算数栈SqStack2 OPTR;/运算符栈char precede(char the,char c)/优先级if(the=+|the=-)if(c=+|c=-|c=)|c=#)return();else return();if(the=*|the=/)if(c=()return(); if(the=()if(c=)return(=);else return();if(the=#)if(c=#)return(=);else return(=48&c=0;k-) d=d+abk*pow(10,i-k-1); *OPND.top+=d; i=0;d=0; switch(precede(*(OPTR.top-1),c) case:theta=*-OPTR.top;abc=c; b=*-OPND.top;a=*-OPND.top; *OPND.top+=Operate(a,theta,b); break; printf(计算结果为：); return *(OPND.top-1);void main()printf(%dn,qiuzhi();四运行与测试及结果五心得体会这次实验设计让我更加了解并更加灵活运用大一学到的C程序设计和这个学期学到的数据结构。实验任务要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。这次课程设计让我有一个深刻的体会，编程最需要严谨，总是忘一些符号，比如分号或*等等，因为这些小失误浪费的时间也比较多。这个程序是我们4个人完成的，同时我认为我们的工作是一个团队的工作，团队需要个人，个人也离不开团队，必须发扬团结协作的精神。某个人的离群都可能导致导致整项工作的失败。实习中只有一个人知道原理是远远不够的，必须让每个人都知道，否则一个人的错误，就有可能导致整个工作失败。团结协作是我们成功的一