十进制四则运算计算器的设计与实现

本科生课程设计任务书

2010 — 2011 学年 夏季学期

信息与电气工程学院 学院 计算机科学与技术 专业

课程设计名称： 数据结构

设计题目： 十进制四则运算计算器的设计与实现

完成期限：自 2011 年 6 月 27 日至 2011 年 7 月 1 日 共 1 周

（1）问题描述

在以二叉树表示算术表达式的基础上，设计一个十进制的四则运算计算器。

（3）概要设计

系统用到的抽象数据类型定义：

ADT SNode_s{

数据对象 V：具有相同类型及后进先出特性的数据元素集合

数据关系 R：相邻数据元素具有前驱和后继的关系

基本操作：

InitStack_s(&S)

初始条件：无

操作结果：构造一个空栈 S

Push_s(&S)

初始条件：栈 S 已经存在

操作结果：用 e 返回 S 的栈顶元素

}ADT

ADT SNode_f{

数据对象 D：具有相同类型及后进先出特性的数据元素集合

数据关系 R：相邻数据元素具有前驱和后继的关系

基本操作：

InitStack_f(&S)

初始条件：无

操作结果：构造一个空栈 S

Push_f(&S)

初始条件：栈 S 已经存在

Pop_f(&S，&e)：

操作结果：删除 S 的栈顶元素，并用 e 返回其值

ADT BiTNode{

数据对象 T：具有相同类型及后进先出特性的数据元素集合

CreateBiTree(BT)

2.不是空树且没有输入’#’.则判断左子树不为空

（1）判断左子树的左子树是否为空，不为空则将左子树的数给左子树

的左子树

(2)并设置标志位 BT->flag[i]=2， BT->flag[i]=1。一直延续。

1. 用中序遍历读出表达式的值，根据标志位将符号位和数据压栈

2. 根据标志位判断是符号则读出，再到符号栈中压栈，左右孩子不空

决

定用中序遍历，将数据和括号存在叶子结点，+-*/的符号存在中心节点。

数，将括号里面的结果压栈，否则一直调用函数根据优先级高低先计算*/，

计算+-。

体会：理解思绪很难，过程就处理了几天，一直在考虑遍历的方法。写程序时

考虑了好多比较优先级的方法。这个程序有点难，写程序也写了好久。但是收

获好多。做啥事都得不断的琢磨，多下功夫。

（1）算法设计及其重要语句注释：

//判断符号的优先级

switch(ch){

case '+':

case '-':return 1;break;

case '/':return 2;break;

case '(':

case ')':return 3;break;

default:

}

}

void Putin(char &ch,float fl,LinkStack_f &Sf, LinkStack_s &Ss){

//把多项式中的乘除先计算好，然后放到符号栈和数字栈中

int p;

char pre;

float mid;

for(;ch=='#';){

p=Prio(ch); //得到当即输入符号的优先级

GetTop_f(Sf,pre); //获得符号栈的顶元素

if(p>Prio(pre)){ //比较两者优先级，当输入乘除时，先计算

}

else {

}

cin>>ch;

}

}

float Putout(float totle,LinkStack_f &Sf,LinkStack_s &Ss){

//把栈中的数字和符号计算出来

float mid;

char pre;

Pop_s(Ss,mid);

Pop_f(Sf,pre);

switch(pre){

}

}

return totle;

}

switch(ch){

case '+':

case '-':return 1;break;

case '/':return 2;break;

case '(':

case ')':return 3;break;

default:

}

p=Prio(ch); //得到当即输入符号的优先级

GetTop_f(Sf,pre); //获得符号栈的顶元素