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

《数据结构课程设计-表达式求值问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验表达式求值问题1.问题描述表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*（7-4）/3.中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀表达式（如：112274-*3/+）和前缀表达式（+11/*22-743）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀表达式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2.数据结构设计（1）顺序栈类定义：首先应在类中定义成员函数，以此来完成顺序栈的相关操作，如下：classSqS

2、tack{private:T*base;//栈底指针inttop;//栈顶intstacksize;//栈容量public:SqStack(intm);//构建函数~SqStack(){delete[]base;top=0;stacksize=0;}//析构函数voidPush(Tx);//入栈TPop();//出栈TGetTop();//获取栈顶元素intStackEmpty();//测栈空voidClearStack();//清空栈voidStackTop();//返回栈顶指针voidStackTranverse();//显示栈中元素}

3、;（2）顺序栈类实现：对顺序栈进行初始化，初始化的首要操作就是创建一个空顺序栈。Step1：申请一组连续的内存空间为顺序栈使用：base=newT[m];if(base==NULL){cout<<"栈创建失败，退出!"<

4、;Step2：栈顶指针增加1；top++;Step3：新元素插入栈顶位置；base[top]=x;（3）顺序栈出栈：出栈需要取出栈顶元素，并相应的调整栈顶指针。Step1：首先判断是否栈空，如果栈空，抛出“下溢”信息，无法出栈，否则转入Step2；if(top==-1)throw"栈空，不能出栈";Step2：取出栈顶元素，栈顶指针减1；Tx;x=base[top--];Step3：返回栈顶元素；returnx；（4）顺序栈取栈顶元素：取栈顶元素是取出栈顶元素的值，但不改变栈。Step1：首先判断是否栈空，如果栈空，抛出“下溢”信息，无法出

5、栈，否则转入Step2；if(top==-1)throw"栈空，栈顶无元素";Step2：取出栈顶元素，返回栈顶元素；returnbase[top];（5）判断栈空：判断是否栈空，返回Step1：如果栈空，返回1，否则转Step2；if(top==-1)return1;Step2：否则返回0；return0;（6）清空栈：将栈清空。top=-1（7）返回栈顶指针：cout<<"栈顶top="<

6、e(i>=0)cout<

7、

8、t1=='=')f='<'

9、;elsef='>';break;case'*':case'/':if(t1=='*'

10、

11、t1=='/'

12、

13、t1==')')f='>';elsef='<';break;case'(':if(t1==')'){cout<<"ERROR1"<';}break;case'=':switch(t1){case'='

14、:f='=';break;case'(':cout<<"ERROR2"<';}}returnf;}（1）其次，就是判断输入元素