第1页 / 共50页
第2页 / 共50页
第3页 / 共50页
第4页 / 共50页
第5页 / 共50页
第6页 / 共50页
第7页 / 共50页
第8页 / 共50页
四川大学计算机学院数据结构作业.docx
二、基本要求
三、工具/准备工作
四、分析与实现
五、测试与结论
六、课程设计总结
二、基本要求
三、工具/准备工作
四、分析与实现
五、测试与结论
六、课程设计总结
二、基本要求
三、工具/准备工作
四、分析与实现
五、测试与结论
六、课程设计总结
《 数据结构与算法 》课程设计
指导老师：游洪跃
班级：2010 级计算机学院计算机科学与技术专业 9 班
姓名：袁东昊
学号：1043041071
1
1. 算术表达式求值
一、 问题描述
从键盘上输入中缀算数表达式，包括括号，计算粗话表达式的值。
二、基本要求
1) 程序对所输出的表达式做出简单的判断，如表达式有错，能给出适当的提示
2) 能处理单目运算符：+和—
三、工具/准备工作
在开始做课程设计项目前，应回顾或复习相关内容。
需要一台计算机，其内安装有 Microsoft Visual Studio 2010 的集成开发环境软件
四、分析与实现
对中缀表达式，一般运算规则如下：
1) 先乘方，再乘除，最后加减
2) 同级运算从左算到右
3) 先算括号内，再算括号外
根据实践经验，可以对运算符设置统一的优先级，从而方便比较。如下表：
运算符
优先级
单目运算符：+，—（可以看成 0+/—个数）
双目运算符：+，—（在+或—的前一个字符（当前一个不是运算符时，规定用‘0’表示））为‘=’，
‘（’，则为单目运算符。
+-
3
（）
=
1
2
*/%
4
^
5
具体实现算法时，可设置两个工作栈，一个为操作符栈 optr(operator),另一个为操作数栈
opnd(operand),算法基本工作思路如下：
1) 将 optr 栈和 opnd 栈清空，在 optr 栈中加入一个‘=’
2) 从输入流获取一字符 ch，循环执行（3）~（5）直到求出表达式的值为止。
3) 取出 optr 的栈顶 optrTop，当 optrTop=‘=’且 ch=‘=’时，整个表达式求值完毕，这时 opnd
栈顶元素为表达式的值。
4) 若 ch 不是操作符，则将字符放回输入流（cin.putback），读操作数 operand；将 operand 加入
opnd 栈，读入下一个字符 ch。
5) 若 ch 是操作符，按如下方式进行处理
i. 如果 ch 为单目运算符，则在 ch 前面加上操作数 0，也就是将 0 入 opnd 栈。
ii. 如果 optrTop 与 ch 不匹配，例如 optrTop=’）’且 ch=‘（’,显示错误信息。
iii. 如果 optrTop=‘（’且 ch=‘）’，则从 optr 栈退出栈顶的‘（’，去括号，然后从输入流中读入字
符并送入 ch
2
iv. 如果 ch=‘（’或 optrTop 比 ch 的优先级低，则 ch 入 optr 栈，从 optr 栈退出 theta，形成运算
指令（left）theta(right),结果入 opnd 栈。
源代码：
//文件 node.h
#ifndef _NODE_H_
#define _NODE_H_
template
struct Node
{
ElemType data;
Node *next;
Node();
Node(ElemType item,Node *link=NULL);
};
template
Node::Node()
{
next = NULL;
}
template
Node::Node(ElemType item, Node *link)
{
data = item;
next = link;
}
#endif _NODE_H_
//文件 lk_stack.h
#ifndef _LINK_STACK_H_
#define _LINK_STACK_H_
#include "utility.h"
#include "node.h"
template
class LinkStack
{
protected:
Node *top;
void Init();
public:
LinkStack();
int Length() const;
bool Empty() const;
void Clear();
void Traverse(void (* visit)(const ElemType &)) const;
StatusCode Push(const ElemType &e);
StatusCode Pop(ElemType &e);
3
StatusCode Top(ElemType &e) const;
LinkStack(const LinkStack ©);
LinkStack&operator=(const LinkStack ©);
};
template
void LinkStack::Init()
{
top=NULL;
}
template
LinkStack::LinkStack()
{
Init();
}
template
int LinkStack::Length() const
{
int count = 0;
for ( Node *tmpPtr = top; tmpPtr != NULL; tmpPtr = tmpPtr->next)
{
count++;
}
return count;
}
template
bool LinkStack::Empty() const
{
return top==NULL;
}
template
void LinkStack::Clear()
{
ElemType tmpElem;
while(!Empty())
{
Pop(tmpElem);
}
}
template
void LinkStack::Traverse(void (* visit)(const ElemType &)) const
4
{
Node *tmpPtr;
LinkStack tmpS;
for(tmpPtr=top;tmpPtr!=NULL;tmpPtr->next)
{
tmpS.Push(tmpPtr->data);
}
for(tmpPtr=tmpS.top;tmpPtr!=NULL;tmpPtr->next)
{
(* visit)(tmpPtr->data);
}
}
template
StatusCode LinkStack::Push(const ElemType &e)
{
Node *new_top=new Node(e,top);
if(new_top==NULL)
{
return OVER_FLOW;
}
else
{
}
}
top=new_top;
return SUCCESS;
template
StatusCode LinkStack::Top(ElemType & e) const
{
if(Empty())
{
return UNDER_FLOW;
}
else
{
}
}
e=top->data;
return SUCCESS;
template
StatusCode LinkStack::Pop(ElemType &e)
{
if(Empty())
{
5
return UNDER_FLOW;
Node *old_top=top;
e=old_top->data;
top=old_top->next;
delete old_top;
return SUCCESS;
}
else
{
}
}
template
LinkStack::LinkStack(const LinkStack ©)
{
if(copy.Empty())
{
Init();
}
else
{
top=new Node(copy.top->data);
Node *buttomPtr=top;
for(Node *tmp=copy.top->next;tmpPtr!=NuLL;tmpPtr!=NULL;tmpPtr=tmpPtr->next)
{
buttomPtr->next=new Node(tmpPtr->data)
buttomPtr=buttomptr->next;
}
}
}
template
LinkStack&LinkStack::operator=(const LinkStack ©)
{
if(©!=this)
{
if(copy.Empty())
{
Init();
}
else
{
Clear();
top=new Node(copy.top->data);
Node *buttomPtr=top;
for(Node *tmpPtr=copy.top->next;tmpPtr!=Null;tmpPtr=tmpPtr->next)
{
6
buttomPtr->next=new Node(tmpPtr->data);
buttomPtr=buttomPtr->next;
}
}
}
return *this;
}
#endif _LINK_STACK_H_
//文件路径名: calculator.h
// 文件路径名: calculator\calculator.h
#ifndef __CALCULATOR_H__
#define __CALCULATOR_H__
#include "lk_stack.h"
// 链栈类
// 计算器类
template
class Calculator
{
private:
LinkStack opnd;
LinkStack optr;
int OperPrior(char op);
void Get2Operands(ElemType &left, ElemType &right);
ElemType Operate(ElemType left, char op, ElemType right);
// 操作符优先级
// 操作数栈
// 操作符栈
bool IsOperator(char ch);
// 判断 ch 是否为操作符
public:
Calculator(){};
virtual ~Calculator(){};
void Run();
};
// 无参数的构造函数
// 析构函数
// 运算表达式
template
int Calculator::OperPrior(char op)
{
int prior;
if (op == '=') prior = 1;
else if (op == '(' || op == ')') prior = 2;
else if (op == '+' || op == '-') prior = 3;
else if (op == '*' || op == '/'|| op == '%') prior = 4;
// 优先级
// =优先级为 1
// (优先级为 2
// +-优先级为 3
// */%优先级为 4
else if (op == '^')
return prior;
prior = 5;
}
7
template
void Calculator::Get2Operands(ElemType &left, ElemType &right)
{
if (opnd.Pop(right) == UNDER_FLOW) throw Error("表达式有错!");
if (opnd.Pop(left)
== UNDER_FLOW) throw Error("表达式有错!");
};
template
ElemType Calculator::Operate(ElemType left, char op, ElemType right)
{
ElemType result;
if (op == '+') result = left + right;
else if (op == '-') result = left - right;
else if (op == '*') result = left * right;
else if (op == '/' && right == 0) throw Error("除数为零!");
else if (op == '/' && right != 0) result = left / right;
// 减法运算
// 乘法运算
// 加法运算
(long)right == 0) throw Error("除数为零!");
else if (op == '%' &&
else if (op == '%' && (long)right != 0) result = (long)left % (long)right;
else if (op == '^') result = pow(left, right);
return result;
// 返回 result
// 乘方运算
}
template
bool Calculator::IsOperator(char ch)
{
if (ch == '=' || ch == '(' || ch == '^' || ch == '*' ||
ch == '/' || ch =='%' || ch == '+' || ch== '-' || ch == ')') return true;
else return false;
};
template
void Calculator::Run()
{
// 清空 optr 栈与 opnd 栈
// 在 optr 栈中加入一个'='
optr.Clear(); opnd.Clear();
optr.Push('=');
char ch;
char priorChar; // 当前输入的前一个字符如不为操作符，则令其值为'0'
char optrTop;
double operand;
char op;
priorChar = '=';
ch = GetChar();
if (optr.Top(optrTop) == UNDER_FLOW) throw Error("表达式有错!");
// 操作符
// 前一字符
// 读入一个字符
// 临时字符
// 临 optr 栈的栈顶字符
// 操作数
// 取出 optr 栈的栈顶
while (optrTop != '=' || ch != '=')
{
// 当前表达式还未运算结束, 继续运算
// 抛出异常
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
