数据结构课程实践报告模板-表达式计算.doc

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

1、表达式计算1、问题描述与分析二级标题算数表达式一般都写成中缀形式，即运算符总是出现在两个操作数之间（单目运算符除外），称为中缀表达式。编译系统对中缀表达式的处理方法是先把它转换为后缀表达式。在后缀表达式中，运算符位于两个操作数的后面，并且没有括号，其运算符次序就是其执行计算的次序。后缀表达式计算过程的规则非常简单：从左到右依次扫描，当读到运算符时，就对该运算符前面的两个操作数执行相应的运算，直至得到表达式的结果。本程序主要模拟编译系统计算中缀表达式的过程，先将中缀表达式转换成相应的后缀表达式，再根据后缀表达式计算出

2、表达式的值。这个问题的解决主要是栈的一个应用。因为本程序仅是模拟，没有判断输入的中缀表达式是否合法，容错性不强，另外也仅能对一位数的中缀表达式进行转换和计算，功能上还有许多局限性，本程序处理的中缀表达式中仅允许出现六种运算符，且都是双目运算符。2、数据结构设计和基本算法设计方法的选择2.1中缀表达式转换成后缀表达式三级标题，段前段后不空行为完成中缀表达式转换成相应的后缀表达式，设计了infix2postfix类。为了方便用户使用，它只有4个接口函数，包括两个构造函数，一个设置中缀表达式的函数setInfixExp和

3、一个返回后缀表达式的函数postfixExp。所有表达式均采用string来存储，运算符用堆栈来临时存储，并用map的数据结构来定义优先级。下面给出了infix2posfix类的声明和部分定义。classinfix2postfix{public:infix2postfix(){};infix2postfix(conststring&infixExp):infix(infixExp){};voidsetInfixExp(conststring&infixExp){infix=infixExp;};stringpost

4、fixExp();private:stringinfix;//用于转换的中缀表达式stringpostfix;//后缀表达式stackstk;//用于存储运算符的堆栈mapoper_prio;//用于存储运算符的优先级voidset_priority();//设置运算符('+','-','*','/','%','^')的优先级};中缀表达式转换成后缀表达式功能的实现是栈的一个典型应用，主要应用栈的“后进先出”的特性及预先设计好的运算符优先级。在转换过程中设置了下运算符栈。本程

5、序的栈直接使用了C++标准模板库STL提供的stack容器。2.2根据后缀表达式计算出表达式的值设计了postfixEval类来实现后缀表达的计算，它只有3个接口函数以方便用户调用。这3个公有函数分别为默认的构造函数、设置后缀表达式的函数setPostfixExp，计算后缀表达式的函数evaluate。下面给出了postfixEval类的声明和部分定义。/*postfixEval类的声明*/classpostfixEval{public:postfixEval(){};//设置后缀表达式voidsetPostfix

6、Exp(conststring&postfixExp){postfix=postfixExp;};//计算后缀表达式并返回其值intevaluate();private:stringpostfix;//待求值的后缀表达式stackstk;voidgetOperands(int&left,int&right);//从堆栈中取得左右操作数intcompute(intleft,intright,charop)const;boolisOperator(charch)const;//判断是否为运算符};后缀表达式的

7、计算也是栈的典型应用，在计算过程中需要设置一个操作数栈。3、软件结构设计由于本程序主要是实现模拟表达式的计算，因此主要有两个功能模块：中缀表达式转换成后缀表达式和根据后缀表达式计算出表达式的值。如果是解决某一问题，在此可不必给出功能模块图，只有类似于学生成绩管理系统这类题目应该给出功能模块图，其他的只需要叙述清楚有什么功能即可。4、算法设计与实现4.1中缀表达式转换成后缀表达式的算法设计中缀表达式转换成后缀表达式的步骤为：1）设置一个运算符栈，初始时效地栈顶运算符置为"#"。2）按顺序扫描中缀表达式，当输入为操作数

8、时就将其输出到后缀表达式中。3）当输入为运算符时，则比较输入运算符和栈顶运算符的优先级。若输入运算符的优先级高于栈顶运算符的优先级，则将输入运算符入栈；否则，栈顶运算符的优先级高于或等于输入运算符的优先级，弹出栈顶运算符至后缀表达式，然后重新比较输入运算符和更新后的栈顶运算符的优先级。4）当输入运算符为"("时，直接将"("入栈。5）当输入运算符为")"时，