课程实践报告模板(二本)
课程实践报告
专业年级
课程名称
指导教师
学生姓名
学 号
实践日期
实践地点
实践成绩
教务处制
201 年 月 日
注：可根据实际情况加页
第二篇：数据结构课程实践报告模板-表达式计算
表达式计算
1、问题描述与分析
算数表达式一般都写成中缀形式，即运算符总是出现在两个操作数之间（单目运算符除外），称为中缀表达式。编译系统对中缀表达式的处理方法是先把它转换为后缀表达式。在后缀表达式中，运算符位于两个操作数的后面，并且没有括号，其运算符次序就是其执行计算的次序。后缀表达式计算过程的规则非常简单：从左到右依次扫描，当读到运算符时，就对该运算符前面的两个操作数执行相应的运算，直至得到表达式的结果。
本程序主要模拟编译系统计算中缀表达式的过程，先将中缀表达式转换成相应的后缀表达式，再根据后缀表达式计算出表达式的值。这个问题的解决主要是栈的一个应用。 因为本程序仅是模拟，没有判断输入的中缀表达式是否合法，容错性不强，另外也仅能对一位数的中缀表达式进行转换和计算，功能上还有许多局限性，本程序处理的中缀表达式中仅允许出现六种运算符，且都是双目运算符。
2、数据结构设计和基本算法设计方法的选择
2.1 中缀表达式转换成后缀表达式
为完成中缀表达式转换成相应的后缀表达式，设计了infix2postfix类。为了方便用户使用，它只有4个接口函数，包括两个构造函数，一个设置中缀表达式的函数setInfixExp和一个返回后缀表达式的函数postfixExp。所有表达式均采用string来存储，运算符用堆栈来临时存储，并用map的数据结构来定义优先级。下面给出了infix2posfix类的声明和部分定义。
class infix2postfix
{
public:
infix2postfix(){};
infix2postfix(const string& infixExp):infix(infixExp){};
void setInfixExp(const string& infixExp){infix=infixExp;};
string postfixExp();
private:
- 1 -
string infix; //用于转换的中缀表达式
string postfix; //后缀表达式
stack<string> stk;//用于存储运算符的堆栈
map<string,int> oper_prio;//用于存储运算符的优先级
void set_priority();
//设置运算符('+','-','*','/','%','^')的优先级
};
中缀表达式转换成后缀表达式功能的实现是栈的一个典型应用，主要应用栈的“后进先出”的特性及预先设计好的运算符优先级。在转换过程中设置了下运算符栈。本程序的栈直接使用了C++标准模板库STL提供的stack容器。
2.2 根据后缀表达式计算出表达式的值
设计了postfixEval类来实现后缀表达的计算，它只有3个接口函数以方便用户调用。这3个公有函数分别为默认的构造函数、设置后缀表达式的函数setPostfixExp，计算后缀表达式的函数evaluate。下面给出了postfixEval类的声明和部分定义。
/*postfixEval类的声明*/
class postfixEval
{
public:
postfixEval(){};
//设置后缀表达式
void setPostfixExp(const string& postfixExp){postfix=postfixExp;};
//计算后缀表达式并返回其值
int evaluate();
private:
string postfix;//待求值的后缀表达式
stack<int>stk;
void getOperands(int&left,int&right);//从堆栈中取得左右操作数
int compute(int left,int right,char op) const;
bool isOperator(char ch) const;//判断是否为运算符
};
后缀表达式的计算也是栈的典型应用，在计算过程中需要设置一个操作数栈。
3、软件结构设计
- 2 -
由于本程序主要是实现模拟表达式的计算，因此主要有两个功能模块：中缀表达式转换成后缀表达式和根据后缀表达式计算出表达式的值。
4、算法设计与实现
4.1 中缀表达式转换成后缀表达式的算法设计
中缀表达式转换成后缀表达式的步骤为：
1）设置一个运算符栈，初始时效地栈顶运算符置为"#"。
2）按顺序扫描中缀表达式，当输入为操作数时就将其输出到后缀表达式中。
3）当输入为运算符时，则比较输入运算符和栈顶运算符的优先级。若输入运算符的优先级高于栈顶运算符的优先级，则将输入运算符入栈；否则，栈顶运算符的优先级高于或等于输入运算符的优先级，弹出栈顶运算符至后缀表达式，然后重新比较输入运算符和更新后的栈顶运算符的优先级。
4）当输入运算符为"("时，直接将"("入栈。
5）当输入运算符为")"时，将栈顶运算符出栈至后缀表达式，直至栈顶为"（"时，将"("出栈并抛弃，同时")"也抛弃。
6）中缀表达式扫描完毕后，将运算符栈依次出栈至后缀表达式直至栈顶为"#"时停止。
具体定义如下：
string infix2postfix::postfixExp()
{
postfix = "";
set_priority();
stk.push("#");
int i = 0;
string input,topstk;
for(;i<infix.size();)
{
topstk = stk.top();//取运算符栈的栈顶
input = infix.substr(i,1);//取出当前待输入的符号
if (!oper_prio[input])//如果输入的符号不是运算符，直接放入postfix
postfix+=input;
else {
//待输入的符号是个运算符，进一步判断它的优先级和运算符栈顶运算符的优先级
if (oper_prio[input]>oper_prio[topstk])//比运算符栈顶运算符的优先级高 {
if(input.compare(")")==0)
//若待输入的运算符为")",pop出栈直至"("，否则直接入栈
- 3 -
{
while(topstk.compare("(")!=0)
{
postfix+=topstk;
stk.pop();
topstk=stk.top();
}
stk.pop();
}
else
stk.push(input);
}
else//比运算符栈顶运算符的优先级低
{
if(input.compare("(")!=0)
{ //若待输入的运算符不为"(",pop出栈直到遇到栈顶运算符的优
//先级高的情况，否则直接入栈
postfix+=topstk;
stk.pop();
continue;
}
stk.push(input);
}
}
++i;
}
topstk=stk.top();
while (topstk.compare("#")!=0)
{
postfix+=topstk;
stk.pop();
topstk=stk.top();
}
return postfix;
}
4.2 计算后缀表达式的算法设计
后缀表达式计算的算法：设置一个用于存放操作数的栈，从左到右依次扫描后缀表达式，每读入一个操作数就将其入栈，每读入一个运算符就从操作数栈中取出两个栈顶元素施以该运算操作，并将运算结果作为新的操作数入栈。重复此过程直至将后缀表达式读完。最后，栈顶操作数即为该后缀表达式的运算结果。具体定义如下：
int postfixEval::evaluate()
- 4 -
{
int i,left,right,expValue;
char ch;
//扫描后缀表达式直至表达式结束
for(i=0;i<postfix.length();i++)
{
ch=postfix[i];//取得当前字符
if (isdigit(ch)) //如果为操作数，压入操作数栈
stk.push(ch-'0');
else if(isOperator(ch))
{ //若为运算符则取出其前两个操作数执行运算，并将结果压入操作数栈 getOperands(left,right);
stk.push(compute(left,right,ch));
}
}
expValue = stk.top();stk.pop();//操作数的栈顶即为最后的运算结果
return expValue;
}
5、调试分析
下面是中缀表达式计算的测试函数主体部分，它测试了中缀表达式转换成后缀表达式类infix2postfix，和后缀表达式的计算类postfixEval的使用情况。
int main(int argc, char *argv[])
{
string infix,postfix;
infix2postfix iexp;
postfixEval pexp;
cout<<"******本程序模拟一位数的中缀表达式转化为后缀表达式及其运算*******"<<endl; cout<<"请输入一个一位数的中缀表达式(q to quit!):"<<endl;
cin>>infix;
while(infix.compare("q")!=0)
{
cout<<"你输入的中缀表达式为："<<infix<<endl;
iexp.setInfixExp(infix);
postfix = iexp.postfixExp();
- 5 -
cout<<"其相应的后缀表达式为"<<postfix<<endl;
pexp.setPostfixExp(postfix);
cout<<"表达式的运算值="<<pexp.evaluate()<<endl<<endl;
cout<<"请再输入一个一位数的中缀表达式(q to quit!):"<<endl;
cin>>infix;
}
return 0;
}
运行结果如图5-1所示。
图5-1 程序运行截图
6、总结
1）综合实践过程的收获；
2）遇到问题以及解决问题的思路和方法；
3）程序调试能力的思考 ；
4）在综合实践设计过程中对《数据结构与算法分析》课程的认识等内容。
- 6 -
附录：程序代码清单
#include <iostream>
#include <stdlib.h>
#include <map>
#include <stack>
using namespace std;
/*infix2postfix类的声明*/
class infix2postfix
{
public:
infix2postfix(){};
infix2postfix(const string& infixExp):infix(infixExp){}; void setInfixExp(const string& infixExp){infix=infixExp;}; string postfixExp();
private:
string infix; //用于转换的中缀表达式
string postfix; //后缀表达式
stack<string> stk;//用于存储运算符的堆栈
map<string,int> oper_prio;//用于存储运算符的优先级 void set_priority();
//设置运算符('+','-','*','/','%','^')的优先级
};
/*postfixEval类的声明*/
class postfixEval
{
public:
postfixEval(){};
//设置后缀表达式
void setPostfixExp(const string& postfixExp){postfix=postfixExp;}; //计算后缀表达式并返回其值
int evaluate();
private:
string postfix;//待求值的后缀表达式
stack<int>stk;
void getOperands(int&left,int&right);//从堆栈中取得左右操作数 int compute(int left,int right,char op) const;
bool isOperator(char ch) const;//判断是否为运算符
};
void infix2postfix::set_priority()
- 7 -
{
oper_prio["#"] = 1;
oper_prio["("] = 2;
oper_prio["+"] = 3;
oper_prio["-"] = 3;
oper_prio["*"] = 4;
oper_prio["/"] = 4;
oper_prio["%"] = 4;
oper_prio["^"] = 5;
oper_prio[")"] = 6;
}
//求取并返回后缀表达式
string infix2postfix::postfixExp()
{
postfix = "";
set_priority();
stk.push("#");
int i = 0;
string input,topstk;
for(;i<infix.size();)
{
topstk = stk.top();//取运算符栈的栈顶
input = infix.substr(i,1);//取出当前待输入的符号
if (!oper_prio[input])//如果输入的符号不是运算符，直接放入postfix
postfix+=input;
else {//待输入的符号是个运算符，进一步判断它的优先级和运算符栈顶运算符的优先级 if (oper_prio[input]>oper_prio[topstk])//比运算符栈顶运算符的优先级高
{
if(input.compare(")")==0)
//若待输入的运算符为")",pop出栈直至"("，否则直接入栈
{
while(topstk.compare("(")!=0)
{
postfix+=topstk;
stk.pop();
topstk=stk.top();
}
stk.pop();
}
else
stk.push(input);
- 8 -
}
else//比运算符栈顶运算符的优先级低
{
if(input.compare("(")!=0)
{ //若待输入的运算符不为"(",pop出栈直到遇到栈顶运算符的
//优先级高的情况，否则直接入栈
postfix+=topstk;
stk.pop();
continue;
}
stk.push(input);
}
}
++i;
}
topstk=stk.top();
while (topstk.compare("#")!=0)
{
postfix+=topstk;
stk.pop();
topstk=stk.top();
}
return postfix;
}
int postfixEval::evaluate()
{
int i,left,right,expValue;
char ch;
//扫描后缀表达式直至表达式结束
for(i=0;i<postfix.length();i++)
{
ch=postfix[i];//取得当前字符
if (isdigit(ch)) //如果为操作数，压入操作数栈
stk.push(ch-'0');
else if(isOperator(ch))
{ //若为运算符则取出其前两个操作数执行运算，并将结果压入操作数栈 getOperands(left,right);
stk.push(compute(left,right,ch));
}
}
expValue = stk.top();stk.pop();//操作数的栈顶即为最后的运算结果
return expValue;
}
- 9 -
void postfixEval::getOperands(int& left,int& right)
{
right = stk.top();
stk.pop();
left = stk.top();
stk.pop();
}
int postfixEval::compute(int left,int right,char op) const
{
int value;
switch(op)
{
case '+':value = left+right;
break;
case '-':value = left-right;
break;
case '*':value = left*right;
break;
case '/':if (right == 0)
cout<<"postfixEval出现 除0 错误"<<endl; value = left/right;
break;
case '%':if (right == 0)
cout<<"postfixEval出现 除0 错误"<<endl; value = left%right;
break;
case '^':if (left==0 && right == 0)
cout<<"postfixEval出现未定义的0^0现象"<<endl; value=1;
while(right>0)
{
value *=left;
right--;
}
break;
}
return value;
}
bool postfixEval::isOperator(char ch) const
{
- 10 -
return ch=='+'||ch=='-' || ch=='*'||ch=='/'||ch=='%'||ch=='^';
}
int main(int argc, char *argv[])
{
string infix,postfix;
infix2postfix iexp;
postfixEval pexp;
cout<<"****本程序模拟一位数的中缀表达式转化为后缀表达式及其运算*******"<<endl; cout<<"请输入一个一位数的中缀表达式(q to quit!):"<<endl;
cin>>infix;
while(infix.compare("q")!=0)
{
cout<<"你输入的中缀表达式为："<<infix<<endl;
iexp.setInfixExp(infix);
postfix = iexp.postfixExp();
cout<<"其相应的后缀表达式为"<<postfix<<endl;
pexp.setPostfixExp(postfix);
cout<<"表达式的运算值="<<pexp.evaluate()<<endl<<endl;
cout<<"请再输入一个一位数的中缀表达式(q to quit!):"<<endl;
cin>>infix;
}
system("PAUSE");
return 0;
}
- 11 -
-
实践课程报告格式
单片机课程设计报告题院组组员组员组员组员目基于STC89C52RC的自行车测速仪系电气信息工程系专业通信工程长柴冰川学号20xx0…
-
大学生课程实践报告作业格式
毛泽东思想和中国特色社会主义理论体系概论课程实践报告报告名称当代大学生心理素质调查研究报告年级20xx级学院经济管理学院专业土地资…
-
课程与教学实践调研报告
课程与教学实践调研报告1课题的提出自上个世纪60年代以来国际化学课程改革风起云涌不少国家和地区在高中化学课程标准课程内容体系教学方…
-
国外课程实践总结报告
广西东方外语职业学院东南亚语言文化学院国外课程实践总结报告（09级）二级学院东南亚语言文化学院专业应用柬埔寨语班级09级柬埔寨语班…
-
课程与教学实践调研报告
课程与教学实践调研报告李栋新课程改革开始后由于基础教育培养目标课程体系的重建要求转变教师教育观念和学生学习方式学校文化建设呈现新的…
-
思修课社会实践调查报告格式及提纲
20xx-20xx学年第1学期《思想道德修养与法律基础》社会实践调查报告格式要求及参考题目一、写作格式1、封面：写清楚调查报告的题…
-
《马克思主义原理概论》课实践报告及格式求
上海杉达学院马克思主义基本原理概论社会实践报告实践论文题目学院姓名及学号专业职称指导教师年月日马克思主义基本原理概论课社会实践环节…
-
课程学习报告格式
课程学习报告课程名称监控组态软件班级学号姓名一学习目的1了解组态软件的使用环境及其基本功能2掌握组态软件的使用方法3掌握监控组态软…
-
课程实训报告格式
模拟电子技术课程实训报告课题名称基于单片机的系别机电系专业电气自动化班级09级学号35号学生姓名指导教师袁从贵完成日期20xx52…
-
最新毛概课实践报告及格式求
毛泽东思想和中国特色社会主义理论体系概论社会实践报告实践论文题目学院姓名及学号专业职称指导教师年月日毛泽东思想和中国特色社会主义理…
-
销售管理学 课程实践性报告
提纲：一、序言：企业管理不是学出来的，是实实在在做出来，管理是一门实践性的学科，参加社会实践活动，理论实践相互验证，才能学以致用。…