数据结构实验报告姓名：学号：专业：信息技术班级：任课老师：辅导教师：试验编号：试验三小组成员：一、实验项目:表达式求值问题二、实验目的：用字符序列的形式从终端输入语法正确的、不含变量的表达式，利用给定的算符优先关系，实现对算术四则混合运算表达式的求值，并演示在求值过程中运算栈、操作数栈、输入字符和主要操作的变化过程。三、实验内容：在计算诸如8+5*（7-3）之类的表达式，例如上述表达式可描述为：7减去3得4，5乘以4得20，8加20得到28，因此表达式的值为28。运算规则：有括号先算括号内；无括号时，先做乘除法，再做加减法；对于相同级别的运算按从左到右次序计算。四、需求分析1、本程序利用栈进行对四则运算的操作；2、并要求演示在求值过程中运算栈、操作数栈、输入字符和主要操作的变化过程。五、概要设计1、函数的构造：structnode//栈元素{chara;};structSqstack//栈{node*base;//指向栈的最底层node*top;//栈顶指针intstacksize;//当前已分配的存储空间,以元素为单位};2、部分函数功能简介voidInitstack(Sqstack&s)//构造一个栈。charGettop(Sqstacks)//返回栈顶元素。intPush(Sqstack&s,nodee)//插入e为新的栈顶元素。charPop(Sqstack&s,node&e)//删除栈顶元素并用e返回其值。boolIn(node&e)//判断元素是否为运算符。intPrecede(node&a,node&b)//判断元素的优先级。nodeOperate(nodea,nodetheta,nodeb)//对a，theta，b进行二元运算。六、详细设计#include<iostream>usingnamespacestd;#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量structnode//栈元素{chara;};structSqstack//栈{node*base;//指向栈的最底层node*top;//栈顶指针intstacksize;//当前已分配的存储空间,以元素为单位};voidInitstack(Sqstack&s)//构造一个栈{s.base=(node*)malloc(STACK_INIT_SIZE*sizeof(node));if(!s.base)exit(1);s.top=s.base;s.stacksize=STACK_INIT_SIZE;}charGettop(Sqstacks)//返回栈顶元素{nodee;if(s.top==s.base)return0;e=*(s.top-1);returne.a;}intPush(Sqstack&s,nodee)//插入e为新的栈顶元素{if(s.top-s.base>=s.stacksize){s.base=(node*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(node));if(!s.base)exit(1);s.top=s.base+s.stacksize;s.stacksize=s.stacksize+STACKINCREMENT;}*s.top=e;s.top++;return1;}charPop(Sqstack&s,node&e)//删除栈顶元素并用e返回其值{if(s.top==s.base)return0;s.top--;e=*s.top;return1;}boolIn(node&e)//判断元素是否为运算符{if(e.a=='+'||e.a=='-'||e.a=='*'||e.a=='/'||e.a=='('||e.a==')'||e.a=='#')return1;elsereturn0;}intPrecede(node&a,node&b)//判断元素的优先级{if(a.a=='+'){if(b.a=='+')return1;if(b.a=='-')return1;if(b.a=='*')return-1;if(b.a=='/')return-1;if(b.a=='(')return-1;if(b.a==')')return1;if(b.a=='#')return1;}if(a.a=='-'){if(b.a=='+')return1;if(b.a=='-')retu