数据结构小论文 表达式求值运算.doc

表达式求值运算一、数据结构的概念数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。根据数据元素间关系的不同特性，通常有下列四类基本的结构： 集合结构。该结构的数据元素间的关系是“属于同一个集合”。 线性结构。该结构的数据元素之间存在着一对一的关系。 树型结构。该结构的数据元素之间存在着一对多的关系。 图形结构。该结构的数据元素之间存在着多对多的关系，也称网状结构。常用结构有链表、栈、队列、数组、树、图、堆、散列表。二、运用的数据结构栈栈是只能在某一端插入和删除的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据，即最后一个数据被第一个读出来。三、构建的数学模型四、程序代码#include stdio.h#include #include #include using namespace std;int in(char c)switch (c)case+:case-:case*:case/:case(:case):case#:return 1;default: return 0;/判断C是否是运算符char precede(char t1,char t2)char f;switch(t2)case+:case-:if(t1=(|t1=#)f=;break;case*:case/:if(t1=*|t1=/|t1=)f=;elsef=;break;case(:if(t1=)printf(input errorn);return (0);elsef=;break;case#:switch(t1)case#:f=;break;case(:printf(input errorn);return (0);default:f=;return f;/判断两个运算符的优先级int operate(int b,char theta,int a)int c;switch(theta)case+:c=(a+b);break;case-:c=(a-b);break;case*:c=(a*b);break;case/:c=(a/b);return c;/对两个操作数进行计算，theta是运算符int evaluateexpress()stack opnd;/声明了1个存储int型元素的栈，存储操作数opndstack optr;/声明了1个存储char型元素的栈，存储运算符optrchar theta,c100;char d=#,0;/将#放入定义的d数组int a,x,b;/初始化操作数a,x,bchar n;optr.push(#);cinc;strcat(c,d);/合并c,d数组，输入算术表达式时不用在末尾输入#int i=0;while(ci!=0)if(!in(ci)ci-=0;int m;m=ci;int j=i+1;if(!in(cj)cj-=0;m=m*10+cj;i+;opnd.push(m);i+;elsen=optr.top();switch(precede(n,ci) /ci尚未入栈，n是运算符栈的栈顶元素case:theta=optr.top();optr.pop();a=opnd.top();opnd.pop();b=opnd.top();opnd.pop();opnd.push(operate(a,theta,b);continue;i+;x=opnd.top();opnd.pop();return x;int main()int n=evaluateexpress();coutnn;五、结果截图输入数据：1、1+（20+4）/（4-1） 2、2*9-6-（20+4）/（4-1）六、总结程序设计时，不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，也不要一味相信教科书上给的代码，碰到断点逐行调试找出问题能收获更多，利用栈表达式求值这个实验中很多人用7*7的二维数组存储运算符优先级表，我觉得这是对空间的一种浪费，故采用了参考书讲解的另一种算法。表达式求值定义了两个栈，操作数和操作符是