数据结构课程设计 实验报告.doc

《数据结构课程设计 实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构课程设计实验报告题目：2.3表达式求值问题1.问题描述表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*（7-4）/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：2274—*3/11+）和前缀式（如：+11/*23—743）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2.数据结构设计本题中使用顺序栈用来存取运算符和运算数，顺序栈类的定义如下：//

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

3、栈顶指针voidStackTranverse();//显示栈中元素};1.算法设计本题中规定的功能涉及的算法有：中缀表达式求值、将中缀表达式转换为后缀表达式、将中缀表达式转换为前缀表达式、后缀表达式求值、前缀表达式求值。（1）中缀表达式求值①首先定义了两个栈，分别用于存取运算符和运算数，如下：SqStackOP(20);SqStackOD(20);②然后依次读取表达式的一个字符C，如果C是运算数，入运算数栈OP.Push(C)；如果C是运算符，把它与栈顶元素的优先级比较：若“<”:该运算符进栈，读入下一个

4、字符，OP.Push(c)；若“=”:运算符退栈，消去一个括号读入下一个字符;若“>”，从运算符栈退出一个运算符，从运算数栈里退出两个运算数进行运算，并将结果入运算数栈。这时需用到比较运算符优先级的函数：charPrecede(chart1,chart2)//算符的优先级比较重复上述过程直到把表达式扫描完，操作数栈的栈顶元素为计算结果。算法如下：case'<':OP.Push(c);//栈顶元素优先权低c=*exp++;break;case'=':x=OP.Pop();//脱括号并接收下一字符c=*exp++;break;case'

5、>':theta=OP.Pop();//退栈并将运算结果入栈if(theta=='('

6、

7、theta==')'){cout<<"表达式有误!";exit(0);}b=OD.Pop();if(b==0){cout<<"表达式有误!"<

8、运算符栈顶元素的算符优先级f1进行比较：若“f1f2”，从运算符栈退出一个运算符，从运算数栈里输出所有比f2优先级高的运算符，直至栈顶算符优先级小于f2，f2入运算符栈。具体算法如下：case'<':OP.Push(c);//栈顶元素优先权低c=*exp++;break;case'=':x=OP.Pop();//脱括号并接收下一字符c=*exp++;break;case'>':postexp[i++]=OP.Pop();break;//运算符

9、出栈输出（3）将中缀表达式转换为前缀表达式①将中缀式入栈再依次从栈中读取元素：如果是操作数把它加入一个数组中;如果是运算符：若栈空或栈顶是右括号或此元素的优先级大于等于栈顶元素，则此运算符入栈；否则，栈顶运算符出栈并加入数组中；若是左括号，栈中元素逐个出栈加入数组中，直到遇到右括号。②最后数组中的元素序列为中缀式的逆序，将数组中的元素入栈再出栈就得到前缀式。部分算法如下：SqStackST(20);SqStackSP(20);SqStackOP(20);while(*exp!='=')//利用栈得

10、到中缀式的逆序ST.Push(*exp++);while(!ST.StackEmpty()){x=ST.Pop();if((x>='0'&&x<='9')

11、

12、x=='.'){s[j++]=x;}if(x==')')OP.Push(x)