毕业设计-数据结构【a】十进制整数四则运算计算器.doc

东北大学信息科学与工程学院
数据结构课程设计报告

题目 十进制整数四则运算计算器

课题组长 余灏然

课题组成员 魏嘉 张越
专业名称 计算机科学与技术

班级 计算机1307

指导教师 杨雷

2015 年 1月

课程设计任务书

题目：
十进制整数四则运算计算器
问题描述：
由输入的四则运算表达式字符串，动态生成算术表达式所对应的二叉树，通过表达式二叉树自动求值并输出。

设计要求：
设计十进制整数四则运算计算器。
（1）采用二叉树、栈等数据结构。
（2）给定表达式字符串，生成二叉链表的表达式二叉树。
（3）对表达式二叉树采用后序遍历求值并输出。
（4）可以考虑加入复数四则运算功能。
（5）其它完善性功能。

指导教师签字：

2014年12月28日

目录
1 课题概述 1
1.1 课题任务 1
1.2 课题原理 1
1.3 相关知识 4
2 需求分析 4
2.1 课题调研 5
2.2 用户需求分析 5
3 方案设计 5
3.1 总体功能设计 5
3.2 数据结构设计 5
3.3 函数原型设计 5
3.4 主算法设计 5
3.5 用户界面设计 5
4 方案实现 6
4.1 开发环境与工具 6
4.2 程序设计关键技术 6
4.3 个人设计实现（按组员分工）
4.3.1余灏然设计实现 6
4.3.2 魏嘉设计实现 9
4.3.3 张越设计实现 11

5 测试与调试 13
5.1 个人测试（按组员分工） 13
5.1.1 余灏然测试 13
5.1.2 魏嘉测试 16
5.1.3 张越测试 20

5.2 组装与系统测试 25
5.3 系统运行 25
6 课题总结 26
6.1 课题评价 26
6.2 团队协作 26
6.3 个人设计小结（按组员分工） 26
6.3.1 余灏然设计小结 26
6.3.2 魏嘉设计小结 27
6.3.3 张越设计小结 27
7 附录A 课题任务分工 28
A-1 课题程序设计分工 28
A-2 课题报告分工 29
附录C 用户操作手册（可选） 30
C.1 运行环境说明 30
C.2 操作说明 30

1 课题背景
1.1 课题任务
【问题描述】
由输入的四则运算表达式字符串，动态生成算术表达式所对应的二叉树，通过表达式二叉树自动求值并输出。
【设计要求】
设计十进制整数四则运算计算器。
（1）采用二叉树、栈等数据结构。
（2）给定表达式字符串，生成二叉链表的表达式二叉树。
（3）对表达式二叉树采用后序遍历求值并输出。
（4）可以考虑加入复数四则运算功能。
（5）其它完善性功能。
1.2 课题原理
用二叉链表处理表达式字符串，用栈处理括号在表达式计算时的优先级问题，并且使用MFC编程语言实现可视化。

1.2.1二叉链表
1.2.2栈处理符号表达式
1.2.3MFC编程语言实现可视化
用MFC语言中对按钮Button功能的添加，将外界输入的由数字0~9，符号“+”、“-”、“*”、“/”、“（”、“）”构成的表达式传入编辑框中的变量CString中。与此同时，可以使用退格键“←”执行退格功能和清屏键执行清屏功能。并且使用“=”按钮时，对输入的表达式进行计算。最终，由编辑框输出计算结果。
流程图如下

流程图1

流程图2

1.3相关知识
生成二叉链表，树的后序遍历，MFC编程语言实现可视化
2需求分析
2.1 课题调研
整数十进制四则运算计算器，用户输入算式程序程序运行并输出运算结果。
2.2 用户需求分析
（1） 用户可以通过MFC按钮输入多项式；
（2） 可输入带括号的运算；
（3） 该程序应该有对用户错误输入的辨别纠错功能；
（4） 程序应具有演示功能和调试功能。
（5） 程序应具有良好的人机接口。
（6） 程序应能友好的展现结果。
3方案设计
3.1 总体功能设计
十进制整数四则运算
3.2 数据结构设计
栈结构，用来储存多项式及生成树；
树结构，用来后序遍历以求多项式的值。
3.3 函数原型设计
函数原型
参数说明
功能描述
void turn(Stack &T,char d[max])
void change(Stack T,Stack &S)
栈T，字符数组d
[]
栈T，栈S
将输入的多项式压栈并转化为前缀表达式
int CreatTree(Tree &T,Stack &S)
Void PostOrder(Tree T,Stack &S)
树T，栈S
建立二叉链表并且后序遍历求值

3.4主算法设计
⑴将输入的表达式压栈，并将其转换为前缀表达式；
⑵由前缀表达式生成二叉链表；
⑶后序遍历二叉树求值。
3.5 用户界面设计
使用MFC编程语言设计界面如下：

4 方案实现
4.1 开发环境与工具
主要编程环境：Blend for Visual Studio 2013
编程工具：C++。

4.2 程序设计关键技术
⑴将输入的表达式压栈，并将其转换为前缀表达式；
⑵由前缀表达式生成二叉链表；
⑶后序遍历二叉树求值。

4.3 个人设计实现（按组员分工）
4.3.1 余灏然设计实现
数据结构定义和描述：
反转表达式及转换前缀表达式：
#include"head.h"
#include"fuhao.cpp"
#include"iostream"
using namespace std;

void turn(Stack &T,char d[max]);
void change(Stack T,Stack &S);

void turn(Stack &T,char d[max]) //字符串输入表达式且压栈
{
int h,r=0; //h用于重置数字，r用于计位置
data b;
while(1)
{
if(d[r]=='\0') break;
if( In(d[r]) )
{
b.k=2;
b.s=d[r++];
Push(T,b);
}
else
{
h=0;
while(d[r]!='\0')
{
if(d[r]=='+'||d[r]=='-'||d[r]=='*'||d[r]=='/'||d[r]=='('||d[r]==')') break;
h*=10;
switch(d[r])
{
case '1': h+=1;break;
case '2': h+=2;break;
case '3': h+=3;break;
case '4': h+=4;break;
case '5': h+=5;break;
case '6': h+=6;break;
case '7': h+=7;break;
case '8': h+=8;break;
case '9': h+=9;break;
case '0': h+=0;break;
default: cout<<"表达式有误!"; exit(0);
}
r++;
}
b.k=1;
b.i=h;
Push(T,b);
}
}
}

void change(Stack T,Stack &S) //转前置表达式
{
Stack P;
InitStack(P);
data a,b,c;
a.k=2 ; a.s='=';
Push(P,a);
while(1)
{
Pop(T,b);
if(b.k==2 && b.s=='=') break;
if(b.k==1) { Push(S,b);continue; }
if(b.k==2)
{
if( b.s==')' ) { Push(P,b);continue; }
if( b.s!='('&& b.s!=')')
{
while(1)
{
GetTop(P,c);
if( Compare(b.s,c.s)=='>'||Compare(b.s,c.s)=='=') {Push(P,b);break;}
else { Pop(P,c); Push(S,c);}
}
}
if( b.s=='(' )
{
while(1)
{
Pop(P,c);
if(c.k==2 && c.s==')') break;
Push(S,c);
}
}
}
}
while(1)
{
GetTop(P,c);
if(c.k==2 && c.s=='=') break;
Pop(P,c);
Push(S,c);
}
}

4.3.2 魏嘉设计实现
符号相关操作：
#include"iostream"
using namespace std;
char Compare(char a,char b);
int In(char c);
int Operate(int b,char x,int a);

/*判断运算的优先顺序*/
char Compare(char a,char b)
{
char c;
switch(a)
{
case'+':if(b=='*'||b=='/'||b=='(')
c='<';
else c='>';
break;
case'-':if(b=='*'||b=='/'||b=='(')
c='<';
else c='>';
break;
case'*':if(b=='(')
c='<';
else c='>';
break;
case'/':if(b=='(')
c='<';
else c='>';
break;
case'(':if(b==')')c='=';
else c='<';
break;
case')':c='>';
break;
case'=':if(b=='=')
c='=';
else c='<';
break;
}
return c;
}

int In(char c){
if(c=='+' || c=='-' || c=='*'|| c=='/'||c=='('||c==')'||c=='=')
return 1;
else return 0;
}

int Operate(int b,char x,int a)
{
int z;
switch(x){
case'+': z=a+b;break;
case'-': z=a-b;break;
case'*': z=a*b;break;
case'/': z=a/b;break;
}
return z;
}
#include"head.h"
#include"fuhao.cpp"
#include"iostream"
using namespace std;

void turn(Stack &T,char d[max]);
void change(Stack T,Stack &S);
typedef struct Node{
data p;
struct Node *lchild,*rchild;
}Node,*Tree;

后序遍历求值：
void PostOrder(Tree T,Stack &S) //利用递归，后序遍历并求值，T为二叉树，S为存储用的栈
{
data a,b,c,d;
if(T!=NULL)
{
PostOrder(T->lchild,S);
PostOrder(T->rchild,S);
c=T->p;
if(c.k==1) Push(S,c);
if(c.k==2)
{
Pop(S,b);Pop(S,a);
d.k=1;d.i=Operate(b.i,c.s,a.i);
Push(S,d);
}
}
}

4.3.3 张越设计实现
建立二叉链表：
#include"head.h"
#include"fuhao.cpp"
#include"iostream"
using namespace std;

void turn(Stack &T,char d[max]);
void change(Stack T,Stack &S);
typedef struct Node{
data p;
struct Node *lchild,*rchild;
}Node,*Tree;

int CreatTree(Tree &T,Stack &S) //建立二叉链表
{
data b,c;
Pop(S,b);
if(b.k==1) //当遇数字时，在后面补两个空位，用于建立二叉树
{ c.k=3; Push(S,c); Push(S,c);}
if(b.k==3) T=NULL;
else
{
if(!(T=(Node*)malloc(sizeof(Node)))) exit(-1);
T->p=b;
CreatTree(T->lchild,S);
CreatTree(T->rchild,S);
}
return(1);
}

栈的创建与操作：
#include"iostream"
using namespace std;

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define max 50

typedef struct Ndata{
int k; // 判断用 k=1: 数字 2：符号 3：返回,用于二叉树的建立
int i; //数字
char s; //符号
}data;

typedef struct NStack{
data *base;
data *top;
int stacksize;
}Stack;

int InitStack(Stack & S){
S.base=(data*)malloc(STACK_INIT_SIZE * sizeof(data) );
if(!S.base) exit(0);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return 1;
}

int GetTop(Stack S,data &e)
{
if(S.top==S.base) return 0;
e= *(S.top-1);
return 1;
}

int Push(Stack &S,data e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(data*)realloc(S.base,(S.stacksize + STACKINCREMENT)* sizeof(data));
if(!S.base) exit(0);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*(S.top++) = e;
return 1;
}

int Pop(Stack &S,data &e)
{
if(S.top==S.base) return 0;
e= *--S.top;
return 1;
}

void ClearStack(Stack &S) //把栈置空，只留栈底
{
data e;
while(1)
{
GetTop(S,e);
if(e.k==-1 ) break;
Pop(S,e);
}
}

5 测试与调试
5.1 个人测试（按组员分工）
5.1.1 余灏然测试
#include"head.h"
#include"fuhao.cpp"
#include"iostream"
using namespace std;

void turn(Stack &T,char d[max]);
void change(Stack T,Stack &S);

void main()
{
static char d[max];
Stack T,S,P; // T为反转栈，S用于输出先序表达式
InitStack(T);InitStack(S);InitStack(P);
data a,b,c;
b.k=2 ; b.s='='; a.k=1;
Push(T,b);Push(S,b);Push(P,b);
cout<<"请输入表达式:";
cin>>d;
turn(P,d);
cout<<"前缀表达式:";
while(1)
{
Pop(P,c);
if(c.k==2&&c.s=='=') break;
if(c.k==1) cout<<c.i;
if(c.k==2) cout<<c.s;
}
turn(T,d); //反转，将栈由栈顶输出到栈底的顺序即为反转顺序
change(T,S); //转化成前序表达式,T为转变前，S为转变后
cout<<endl<<"前缀表达式:";
while(1)
{
Pop(S,a);
if(a.k==2&&a.s=='=') break;
if(a.k==1) cout<<a.i;
if(a.k==2) cout<<a.s;
}
cout<<endl;

}
void turn(Stack &T,char d[max]) //字符串输入表达式且压栈
{
int h,r=0; //h用于重置数字，r用于计位置
data b;
while(1)
{
if(d[r]=='\0') break;
if( In(d[r]) )
{
b.k=2;
b.s=d[r++];
Push(T,b);
}
else
{
h=0;
while(d[r]!='\0')
{
if(d[r]=='+'||d[r]=='-'||d[r]=='*'||d[r]=='/'||d[r]=='('||d[r]==')') break;
h*=10;
switch(d[r])
{
case '1': h+=1;break;
case '2': h+=2;break;
case '3': h+=3;break;
case '4': h+=4;break;
case '5': h+=5;break;
case '6': h+=6;break;
case '7': h+=7;break;
case '8': h+=8;break;
case '9': h+=9;break;
case '0': h+=0;break;
default: cout<<"表达式有误!"; exit(0);
}
r++;
}
b.k=1;
b.i=h;
Push(T,b);
}
}
}

void change(Stack T,Stack &S) //转前置表达式
{
Stack P;
InitStack(P);
data a,b,c;
a.k=2 ; a.s='=';
Push(P,a);
while(1)
{
Pop(T,b);
if(b.k==2 && b.s=='=') break;
if(b.k==1) { Push(S,b);continue; }
if(b.k==2)
{
if( b.s==')' ) { Push(P,b);continue; }
if( b.s!='('&& b.s!=')')
{
while(1)
{
GetTop(P,c);
if( Compare(b.s,c.s)=='>'||Compare(b.s,c.s)=='=') {Push(P,b);break;}
else { Pop(P,c); Push(S,c);}
}
}
if( b.s=='(' )
{
while(1)
{
Pop(P,c);
if(c.k==2 && c.s==')') break;
Push(S,c);
}
}
}
}
while(1)
{
GetTop(P,c);
if(c.k==2 && c.s=='=') break;
Pop(P,c);
Push(S,c);
}
}
测试结果：

5.1.2 魏嘉测试
符号相关操作：
#include"iostream"
using namespace std;
char Compare(char a,char b);
int In(char c);
int Operate(int b,char x,int a);

void main()
{
int i,j,k;
char a,b,s;
while(1)
{
cout<<"请选择操作1.符号优先级判断 2.判断是否是符号 3.两个数的四则运算 ： ";
cin>>i;
if(i==1)
{
cout<<"请输入两个符号：";
cin>>a>>b;
s=Compare(a,b);
cout<<"优先级："<<s<<endl<<endl;
}
if(i==2)
{
cout<<"请输入一个字符";
cin>>s;
if(In(s)) cout<<"是运算符"<<endl;
else cout<<"非运算符"<<endl;
}
if(i==3)
{
cout<<"请输入2个数字：";
cin>>j>>k;
cout<<"请选择加减乘除：";
cin>>s;
j=Operate(k,s,j);
cout<<"结果为"<<j<<endl;
}
}
}

/*判断运算的优先顺序*/
char Compare(char a,char b)
{
char c;
switch(a)
{
case'+':if(b=='*'||b=='/'||b=='(')
c='<';
else c='>';
break;
case'-':if(b=='*'||b=='/'||b=='(')
c='<';
else c='>';
break;
case'*':if(b=='(')
c='<';
else c='>';
break;
case'/':if(b=='(')
c='<';
else c='>';
break;
case'(':if(b==')')c='=';
else c='<';
break;
case')':c='>';
break;
case'=':if(b=='=')
c='=';
else c='<';
break;
}
return c;
}

int In(char c){
if(c=='+' || c=='-' || c=='*'|| c=='/'||c=='('||c==')'||c=='=')
return 1;
else return 0;
}

测试结果：

int Operate(int b,char x,int a)
{
int z;
switch(x){
case'+': z=a+b;break;
case'-': z=a-b;break;
case'*': z=a*b;break;
case'/': z=a/b;break;
}
return z;
}
#include"head.h"
#include"fuhao.cpp"
#include"iostream"
using namespace std;

void turn(Stack &T,char d[max]);
void change(Stack T,Stack &S);
typedef struct Node{
data p;
struct Node *lchild,*rchild;
}Node,*Tree;

void main()
{
void PostOrder(Tree T,Stack &S);
void main2(Tree &T);
Stack P;
Tree T;
InitStack(P);
data b;
b.k=2 ;
b.s='=';
Push(P,b);
main2(T);
PostOrder(T,P);
GetTop(P,b);
cout<<"表达式值为"<<b.i<<endl;
}
后序遍历求值：
void PostOrder(Tree T,Stack &S) //利用递归，后序遍历并求值，T为二叉树，S为存储用的栈
{
data a,b,c,d;
if(T!=NULL)
{
PostOrder(T->lchild,S);
PostOrder(T->rchild,S);
c=T->p;
if(c.k==1) Push(S,c);
if(c.k==2)
{
Pop(S,b);Pop(S,a);
d.k=1;d.i=Operate(b.i,c.s,a.i);
Push(S,d);
}
}
}

测试结果：

5.1.3 张越测试
#include"head.h"
#include"fuhao.cpp"
#include"iostream"
using namespace std;

void turn(Stack &T,char d[max]);
void change(Stack T,Stack &S);
typedef struct Node{
data p;
struct Node *lchild,*rchild;
}Node,*Tree;

void main()
{
Stack main1();
int CreatTree(Tree &T,Stack &S);
Stack S;
Tree T;
InitStack(S);
data b,c;
int i;
b.k=2 ; b.s='=';
Push(S,b);
S=main1();
CreatTree(T,S);
cout<<"表达式树建立成功！"<<endl;
cout<<"根节点值为：";
while(1)
{
c=T->p;
if(c.k==1) cout<<c.i<<endl;
if(c.k==2) cout<<c.s<<endl;
cout<<"访问左孩子1，访问右孩子2：";
cin>>i;
if(i==1) T=T->lchild;
if(i==2) T=T->rchild;
}

}

int CreatTree(Tree &T,Stack &S) //建立二叉链表
{
data b,c;
Pop(S,b);
if(b.k==1) //当遇数字时，在后面补两个空位，用于建立二叉树
{ c.k=3; Push(S,c); Push(S,c);}
if(b.k==3) T=NULL;
else
{
if(!(T=(Node*)malloc(sizeof(Node)))) exit(-1);
T->p=b;
CreatTree(T->lchild,S);
CreatTree(T->rchild,S);
}
return(1);
}
测试结果：

栈的创建与操作：
#include"iostream"
using namespace std;

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define max 50

typedef struct Ndata{
int k; // 判断用 k=1: 数字 2：符号 3：返回,用于二叉树的建立
int i; //数字
char s; //符号
}data;

typedef struct NStack{
data *base;
data *top;
int stacksize;
}Stack;

int InitStack(Stack & S){
S.base=(data*)malloc(STACK_INIT_SIZE * sizeof(data) );
if(!S.base) exit(0);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return 1;
}

int GetTop(Stack S,data &e)
{
if(S.top==S.base) return 0;
e= *(S.top-1);
return 1;
}

int Push(Stack &S,data e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(data*)realloc(S.base,(S.stacksize + STACKINCREMENT)* sizeof(data));
if(!S.base) exit(0);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*(S.top++) = e;
return 1;
}

int Pop(Stack &S,data &e)
{
if(S.top==S.base) return 0;
e= *--S.top;
return 1;
}

void ClearStack(Stack &S) //把栈置空，只留栈底
{
data e;
while(1)
{
GetTop(S,e);
if(e.k==-1 ) break;
Pop(S,e);
}
}

void main()
{
int i;
Stack T;
InitStack(T);
cout<<"创建栈成功!"<<endl;
data a,b;
a.k=-1;a.i=-1;
Push(T,a);
while(1)
{
cout<<"对栈进行操作：1.存入数据 2.获取栈顶元素 3.取出并删除栈顶元素 4.置空栈，只留栈底 5.结束:";
cin>>i;
if(i==1)
{
cout<<"请输入2个数字:";
cin>>b.k>>b.i;
Push(T,b);
cout<<"已成功存入栈里!"<<endl;
}
if(i==2)
{
GetTop(T,b);
cout<<b.k<<" "<<b.i<<endl;
}
if(i==3)
{
Pop(T,b);
cout<<b.k<<" "<<b.i<<endl;
}
if(i==4)
{
ClearStack(T);
cout<<"置空成功！"<<endl;
}
getchar();getchar();
if(i==5) break;
}
}
测试结果：

5.2 组装与系统测试

5.3 系统运行

6 课题总结
6.1 课题评价
按照课题的要求，我们组同学进行了分工，实现了其所规定的设计要求，并且有所拓展，运用课本上的知识及学习了一些本来未曾接触的知识，运用陌生的类模板实现了掌握较为熟练的功能。

6.2 团队协作
由于需要学习新的知识--MFC编程语言，在完成项目过程中，我们进行了明确的分工，以确保高效，每个人对新知识的学习，之后汇总，按照所学分配任务，高效地完成了任务。
6.