数据结构专业课程设计方案报告.doc

课 程 设 计 报 告

课程设计名称： 数据构造
系 ： 计算机科学系
学生姓名： 李锡会
班 级： 13計算機科學與技術1班
学 号： 18
成 绩：
指引教师： 肖錦輝老師
开学时间： - 年 第 2 学期
一．设计题目
算术表达式求值
二．重要内容
（所选课题需求分析，实现功能等）
1、程序能对所输入表达式作简朴判断，如表达式有错。
2、能解决单目运算符：+、-。
三．课题设计基本思想，原理和算法描述
（涉及课题所用数据构造，界面设计、输入/输出设计，功能模块设计，符号阐明等）
对于中缀表达式，普通运算规则如下：
1、先乘方，再乘除，最后加减。
2、同级运算从左算到右。
3、先括号内，再括号外。
操作符号：+ - * / ^ % ().
依照实际经验，可以对运算符设立统一优先级，从而以便比较。
上面讨论+、-为双目运算符，如单目运算符，编程实现时，可在前面加上0而转化为双目运算符。
思路如下：
1、将optr栈和opnd栈清空，在optr栈中加入一种‘=’。
2、从输入流获取一字符ch，循环执行环节3至环节5直到求出表达式值为止。
3、取出optr栈顶optrTop，当optrTop=‘=’且ch=‘=’时，整个表达式求值完毕，这时opnd栈栈顶元素为表达式值。
4、若ch不是操作符，则将字符放回输入流（cin.putback）,读操作符operand；将operand加入opnd栈，读入下一种字符ch。
5、若ch是操作符，按如下方式进行解决：
a．若ch为单目运算符，则在ch前面加上操作符0，也就是将0入pond。
b．若optrTop与ch不匹配，例如optrTop=‘）’且ch=‘（’，显示错误信息。
c．若optrTop=‘（’且ch=‘）’，则从optr栈退出栈顶‘（’，去括号，然后从输入流中读入字符并送入ch；
d．若ch=‘(‘或optrTop比ch优化级低，则ch入optr，从输入流中取下一种字符ch；
e．若optrTop不不大于或等于ch优先级，则从opnd栈退出left和right，从optr栈退出theta，形成运算符指令（left）theta（right），成果入opnd栈。
四．源程序及注释

需要用到头文献有：
lk_stack.h node.h utility.h cal.h
// cal.h

#ifndef __CALCULATOR_H__
#define __CALCULATOR_H__
#include "lk_stack.h" // 链栈类

template<class ElemType>
class Calculator
{
private:
LinkStack<ElemType> opnd;
LinkStack<char> optr;
//char GetChar();
int OperPrior(char op);
void Get2Operands (ElemType &left,ElemType &right);
ElemType Operate(ElemType left,char op,ElemType right);
bool IsOperator(char ch);
public:
Calculator(){};
virtual ~Calculator(){};
void Run();
};
template<class ElemType>
int Calculator<ElemType>::OperPrior(char ch)
{
if(ch == '=') return 1;
if(ch == '^') return 5;
if(ch == '('||ch == ')') return 2;
if(ch == '+'|| ch == '-') return 3;
if(ch == '*'||ch == '/'||ch == '%') return 4;
return 0;
}
template<class ElemType>
bool Calculator<ElemType>::IsOperator(char ch)
{
if (ch == '=' || ch == '(' || ch == '*' ||
ch == '/' || ch == '+' || ch == '-' || ch == ')'|| ch == '%'||ch == '^') return true;
else return false;
};
template<class ElemType>
ElemType Calculator<ElemType>::Operate(ElemType left，char theta，ElemType right)
// 操作成果：执行运算left op right
{
ElemType result;
if (theta == '+') result = left + right；// 加法运算
else if (theta == '-') result = left - right；// 减法运算
else if (theta == '*') result = left * right；// 乘法运算
//else if (theta == '/' && right == 0) throw "除数为零!"；// 抛出异常
else if (theta == '/' ) result = left / right；// 除法运算
else if (theta == '^') result = pow(left ，right);
else if (theta == '%') result = (int)left%(int)right;
return result；// 返回result
}
template<class ElemType>
void Calculator<ElemType>::Get2Operands( ElemType &left，ElemType &right)
// 操作成果：从栈opnd中退出两个操作数
{
opnd.Pop(right)；
opnd.Pop(left)；
}
template<class ElemType>
void Calculator<ElemType>::Run()
{
optr.Clear();
opnd.Clear();
optr.Push('=');
char ch;
char priorChar;
char optrTop;
ElemType operand;
char op;
priorChar='=';
ch=GetChar();
optr.Top(optrTop);
while(optrTop!='='||ch!='=')
{
if(isdigit(ch)||ch=='.')
{
cin.putback(ch);
cin>>operand;
opnd.Push(operand);
priorChar='0';
ch=GetChar();
}
else if(!IsOperator(ch))
{
cout<<"表达式错误！"<<endl;
return;
}
else
{
if ((priorChar=='='||priorChar=='(')&&(ch=='+'||ch=='-'))
{
opnd.Push(0);
priorChar='0';
}
if(optrTop=='('&&ch==')')
{
optr.Pop(optrTop);
ch=GetChar();
priorChar=')';
}
else if(ch=='('||OperPrior(optrTop)<OperPrior(ch))
{
optr.Push(ch);
priorChar=ch;
ch=GetChar();
}
else
{
optr.Pop(op);
ElemType left,right;
Get2Operands(left,right);
opnd.Push(Operate(left,op,right));
}
}
optr.Top(optrTop);
}
opnd.Top(operand) ;
cout<<operand<<endl;
};

#endif

//main.cpp

#include"utility.h"
#include "cal.h" // 计算器类
int main(void)
{
try // 用try封装也许浮现异常代码
{
do
{
cout << "输入一种表达式:" << endl;
Calculator<double> cal;
cal.Run()；// 表达式求值

cout << "与否继续";
} while (UserSaysYes());
}
catch (Error err) // 捕获并解决异常
{
err.Show()；// 显示异常信息
}

system("PAUSE")；// 调用库函数system()
return 0；// 返回值，返回操作系统
}

五、运营示例及成果分析
（截图分析）

六、调试和运营程序过程中产生问题及采用办法
Throw语句出错，用cout和return代替。
七、总结和展望
（400字以上）
感谢教师给咱们这次课程设计机会，在本次项目中，虽然我面临着许多困难，但是，通过不断地努力与调试后，终于完毕了该次项目。但是，该项目局限性，加上运营环境问题，也许会浮现不稳定，但总体来说，可以顺利实现项目规定。固然，在完毕该次项目过程中，我意识到自己在基本知识上各种局限性，同步，我也为了完毕项目而不断努力地复习并验证知识点。我但愿在后来日子里，可以接受更大挑战，由于那不但可以给自己锻炼，还可以在那个过程中，学到更多项目经验。说夸张一点，那是算是宝贵财富吧。固然，需要在拥有一定知识基本，才干接受一定难度项目，因此，必要先从基本知识开始，固然需要对基本知识加以巩固，然后不断地上机操作，并加以锻炼。说实话，对初次完毕项目，难度比较大，由于要考虑各种不拟定因素，因此，在真正实践起来，相称困难，有时候也许对一种小小问题，抱着诸多无奈，固然，成果刻苦地努力，还是可以顺利完毕任务。
八、参照资料
（格式为：[序号]作者.书名.出版社，出版年份 如：
[1] 李建学等著.数据构造课程设计案例精编.清华大学出版社，
[2] 唐宁九等主编.数据构造与算法（C++版）实验和课程设计教程. 清华大学出版社，）
注：以上所有正文内容（所给八个标题除外）均采用小四字体书写，且每段首行缩进，段落间距1.3倍行距。