发布时间 : 星期一 文章数据结构课程设计-表达式求值问题更新完毕开始阅读32779062ba68a98271fe910ef12d2af90242a8a5
实验 表达式求值问题
1.问题描述
表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*（7-4）/3.中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀表达式（如：11 22 7 4 - * 3 / +）和前缀表达式（+ 11 / * 22 - 7 4 3）。后缀表达式
和前缀表达式中没有括号，给计算带来方便。如后缀表达式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。
2.数据结构设计
（1）顺序栈类定义：首先应在类中定义成员函数，以此来完成顺序栈的相关操作，如下： class SqStack { };
（2）顺序栈类实现：对顺序栈进行初始化，初始化的首要操作就是创建一个空顺序栈。
Step1：申请一组连续的内存空间为顺序栈使用： base=new T[m]; if(base==NULL) { private:
T *base; //栈底指针 int top; //栈顶 int stacksize; //栈容量
public:
SqStack(int m); //构建函数 ~SqStack(){delete [] base;top=0;stacksize=0;} //析构函数 void Push(T x); //入栈 T Pop(); //出栈 T GetTop(); //获取栈顶元素 int StackEmpty(); void ClearStack(); void StackTop();
//测栈空
//清空栈 //返回栈顶指针 //显示栈中元素
void StackTranverse();
}
cout<<\栈创建失败，退出!\exit(1);
Step2：给栈顶、栈容量赋相应的值： stacksize=m; top=-1;
（2）顺序栈入栈：入栈需要在栈顶插入一个新元素并相应的调整栈顶。
Step1：首先判断是否栈满，如果栈满，抛出“上溢”信息，无法入栈，否则转入Step2； if(top==stacksize-1) throw \栈满，无法入栈\Step2：栈顶指针增加1； top++;
Step3：新元素插入栈顶位置； base[top]=x;
（3）顺序栈出栈：出栈需要取出栈顶元素，并相应的调整栈顶指针。
Step1：首先判断是否栈空，如果栈空，抛出“下溢”信息，无法出栈，否则转入Step2； if(top==-1) throw \栈空，不能出栈\Step2：取出栈顶元素，栈顶指针减1； T x;
x=base[top--]; Step3：返回栈顶元素； return x；
（4）顺序栈取栈顶元素：取栈顶元素是取出栈顶元素的值，但不改变栈。
Step1：首先判断是否栈空，如果栈空，抛出“下溢”信息，无法出栈，否则转入Step2； if(top==-1) throw \栈空，栈顶无元素\Step2：取出栈顶元素，返回栈顶元素； return base[top];
（5）判断栈空：判断是否栈空，返回 Step1：如果栈空，返回1，否则转Step2； if(top==-1)
return 1;
Step2：否则返回0； return 0;
（6）清空栈：将栈清空。 top=-1
（7）返回栈顶指针：
cout<<\栈顶top= \
（8）输出栈元素：将栈顶指向i，从栈顶输出到栈底。 Step1：将栈顶指针赋予i； int i=top;
Step2：如果栈不为空，则输出； while(i>=0)
cout< 3. 算法设计 本实验要求读入中缀表达式，求中缀表达式，将中缀表达式转换成前，后缀表达式，利用前，中，后缀表达式求值，并且能够输出等等操作，这就需要构建相关算法。 （1）首先要将表达式中操作符优先级进行排序，优先级从高到低依次为（，），*，/，+，-，算法如下，利用选择语句比较： char Precede(char t1,char t2) {//运算符的优先级比较 char f; switch(t2) { case '+': case '-':if(t1=='('||t1=='=') f='<'; else f='>'; break; case '*': case '/':if(t1=='*'||t1=='/'||t1==')') f='>'; else f='<'; break; case '(':if(t1==')') { cout<<\ exit(0); } else f='<'; break; case ')':switch(t1) { case '(':f='='; break; case '=':cout<<\ exit(0); default: f='>'; } break; case '=':switch(t1) { case '=':f='='; break; case '(':cout<<\ exit(0); default: f='>'; } } return f; } （2）其次，就是判断输入元素是否为运算符，若为运算符，就输出1，否则输出0； int In(char c) { // 判断c是否为运算符 switch(c) { case'+': case'-': case'*': case'/': case'(': case')': case'=':return 1;