实验三实验报告.doc

实验三实验报告
1120131317 周任然
1、简易计算器
（1）问题描述
由键盘输入一算术表达式，以中缀形式输入，试编写程序将中缀表达式转换成一棵二叉表达式树，通过对该的后序遍历求出计算表达式的值。
（2）基本要求
a．要求对输入的表达式能判断出是否合法。不合法要有错误提示信息。
b．将中缀表达式转换成二叉表达式树。
c．后序遍历求出表达式的值
（3）数据结构与算法分析
一棵表达式树，它的树叶是操作数，如常量或变量名字，而其他的结点为操作符。
a．建立表达式树。二叉树的存储可以用顺序存储也可用链式存储。当要创建二叉树时，先从表达式尾部向前搜索，找到第一个优先级最低的运算符，建立以这个运算符为数据元素的根结点。注意到表达式中此运算符的左边部分对应的二叉绔为根结点的左子树，右边部分对应的是二叉绔为根结点的右子树，根据地这一点，可用递归调用自己来完成对左右子树的构造。
b．求表达式的值。求值时同样可以采用递归的思想，对表达式进行后序遍历。先递归调用自己计算左子树所代表的表达式的值，再递归调用自己计算右子树代表的表达式的值，最后读取根结点中的运算符，以刚才得到的左右子树的结果作为操作数加以计算，得到最终结果。
（4）需求分析
程序运行后显示提示信息，输入任意四则运算表达式，倘若所输入的表达式不合法程序将报错。
输入四则运算表达式完毕，程序将输出运算结果。
测试用的表达式须是由+、-、*、/运算符，括号“(”、“)”与相应的运算数组成。运算数可以是无符号浮点型或整型，范围在0～65535。
（5）概要设计
二叉树的抽象数据类型定义
ADT BinaryTree{
数据对象：表达式运算数 { num | 0< num < 65535 }
表达式运算符 { opr | + , - , * , / }
数据关系：由一个根结点和两棵互不相交的左右子树构成，且树中结点具有层次关系。根结点必须为运算符，叶子结点必须为运算数。
基本操作：
InitBiTree(&T , &S)
初始条件：存在一四则运算前缀表达式S。
操作结果：根据前缀表达式S构造相应的二叉树T。
DestroyBiTree(&T)
初始条件：二叉树T已经存在。
操作结果：销毁T。
Value(&T)
初始条件：二叉树T已经存在。
操作结果：计算出T所表示的四则运算表达式的值并返回。
}ADT BineryTree
顺序栈的抽象数据类型定义
ADT Stack{
数据对象：具有相同类型及后进先出特性的数据元素集合。
数据关系：相邻数据元素具有前去和后继关系。
基本操作：
InitStack(&S)
初始条件：无
操作结果：构造一个空栈S。
DestroyStack(&S)
初始条件：栈S已经存在。
操作结果：销毁S。
StackLength(&S)
初始条件：栈S已经存在。
操作结果：返回S中元素个数。
GetTop(S , &e)
初始条件：栈S已经存在且非空。
操作结果：用e返回S的栈顶元素。
Push(&S , e)
初始条件：栈S已经存在。
操作结果：插入元素e为S的新栈顶元素。
Pop(&S , e)
初始条件：栈S已经存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。
}ADT Stack
字符串的抽象数据类型定义
ADT String{
数据对象：具有字符类型的数据元素集合。
数据关系：相邻数据元素具有前驱和后继关系。
基本操作：
StrLength(S)
初始条件：串S已经存在。
操作结果：返回S的元素个数。
StrNeg(S , F)
初始条件：串S已经存在且非空。
操作结果：求S的逆序并将结果保存在串F中。
}ADT String
本程序包含四个模块：主程序模块；二叉树单元模块（实现二叉树的抽象数据类型，包括结点和指针的定义）；顺序栈单元模块（实现顺序栈的抽象数据类型，包含结点和指针的定义）；字符串单元模块(实现字符串的抽象数据类型)。四个模块之间调用关系为主程序模块二叉树模块，二叉树模块调用顺序栈模块。
详细设计
顺序栈类型。
#define Stack_Size 100
typedef struct {
char elem[Stack_Size];
int top;
}SqStack
基本操作实现的伪代码算法如下：
void InitStack (SqStack &S) { //初始化顺序栈
S.elem=new ElemType[Stack_Size];
if(!S.elem) Error("Overflow!");
S.top=-1; }

viod Push (SqStack &S,char c) { //顺序栈压栈
if(S.top==(Stack_Size-1)) Error("Stack Overflow!");
S.elem[++S.top]=c; }

ElemType Pop (SqStack &S) { //顺序栈出栈
if(S.top==-1) Error("Stack Empty!");
return S.elem[S.top--]; }

int StackLength(SqStack &S) { //求顺序栈长度
return (S.top+1); }

GetTop(SqStack &S ,char e) { //取栈顶元素
e=S.elem[top]; }

字符串类型
typedef struct{ //动态顺序串
char *ch;
int length;
}String
基本操作实现的伪代码算法如下：
int StrLength(&S) { //求串长
return S.length; }

void StrNeg(&S , &F) { //求逆序串
if(!S.length) error(“String Empty!”);
for(i=0 ; i<length ; i++)
F.ch[i] = S.ch[length-1-i]; }
二叉树类型。
typedef struct TNode{ //二叉树结点
union data{ char optr; //运算符
int opnd; }; //操作数
struct TNode *lchild , *rchild
}TNode
typedef TNode *BiTree //二叉树指针
基本操作实现的伪代码算法如下：
int Precedence (char opr) { //判断运算符级别函数；其中* /的级别为2，+ -的级别为1；
int level;
switch(opr) {
case'+': case'-': return (1); break;
case'*': case'/': return(2); break;
case'(': case')':
case'#':
default:
return(0); break; }
}
bool IsOperator(char opr) { //判断输入串中的字符是不是合法操作符
if(op=='+'||op=='-'||op=='*'||op=='/')
return true;
else
return false; }
string Convert(string &Str) { //将一个中缀串转换为后缀串，
string Output; //输出串
SqStack S;
for(int i=S.length-1 ; i>=0 ; i--) { //对输入串逆序扫描
if(Str.ch[i]>=48&&Str.ch[i]<=57) {
Output.ch[i]=Str.ch[i]; //假如是操作数，把它添加到输出串中。
Output.length++; }
if( Str.ch[i]==')' ) //假如是右括号，将它压栈。
Push( S , Str.ch[i] );
while( IsOperator( s[i] ) ) { //如果是运算符
if( top==0 || GetTop(S)==')' || Precedence(Str.ch[i] ) >=Precedence( GetTop(S) ) ) {
Push( S , Str.ch[i] );
break; }
else { Pop(S , e);
Output.ch[i]=e;
Output.length++; } }
if( Str.ch[i]=='(' ) { //假如是左括号，栈中运算符逐个出栈并输出，直到遇到右括号。右括号出栈并丢弃。
while( GetTop(S)!=')' ) {
Output.ch[i]=Pop(S);
Output.length++;
}
}
}
while(S.top!=-1) { //假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。
Output.ch=Output.ch--;
Output.ch=Pop(S); }
return output;
}
void CreatBiTree(&T , &S) { //由中缀表达式生成表达式二叉树
String F;
SqStack Sq; //用以存放生成的二叉树结点
InitStack(Sq);
F=Convert(S); //求得S的前缀表达式
for(i=F.length-1 ; i>=0 ; i--) {
If( !IsOperator(F.ch[i]) ) {
T=new TNode;
T->data=F.ch[i];
T->lchild=NULL;
T->rchild=NULL;
Push(Sq , T) }
else {
T=new TNode;
T->data=F.ch[i];
T->lchild=Pop( Sq );
T->rchild=Pop( Sq );
Push(Sq , T); }
} }
int Calc(int a, char opr, int b) { //计算
switch (opr) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
}
int Value(TNode *T) {
if (T->lchild == NULL &&T->rchild == NULL)
return T->data;
else
return Calc( Value(T->lchild) , T->data , Value(T->rchild) );
};
主函数伪码算法。
void main() {
Face(); //输出界面及相关信息
do {
cout<<”Please input an expression:”<<endl;
cin>>Str;
JudgeExp(S); //判断输入的表达式是否合法。
T=CreatBiTree(S);
N=Value(T);
cout<<”The value of this expression is”<<N<<endl;
cout<<”To do another calculation? [Y/N]” ;
cin>>e;
if(e==’y’) flag=1;
else flag=0; }while(flag)
}//main

测试结果

附录（带注释的源程序）
//****************************CStack.h******************************//
#include<iostream>
using namespace std;

#define Stack_Size 100

typedef struct
{ //字符类型顺序栈
char elem[Stack_Size];
int top;
}CStack

void InitCStack(&S)
{ //初始化顺序栈
S.elem=new char[Stack_Size];
if(!S.elem) Error("Overflow!");
S.top=-1;
}

void Push_C(CStack &S , char e)
{ //压栈
if( S.top==(Stack_Size-1) ) Error("Stack Overflow!");
S.elem[++S.top]=e;
}

char Pop_C(CStack &S)
{ //出栈
if(S.top==-1) Error("Stack Empty!");
return S.elem[top--];
}

char GetTop(&S)
{ //取栈顶元素
if(S.top==-1) Error("Stack Empty!");
return S.elem[top];
}

int CStackLength(&S)
{ //求栈中元素个数
return top+1;
}

//****************************TStack.h******************************//
#include<iostream>
#include"Tree.h"
using namespace std;

#define Stack_Size 100

typedef struct
{ //二叉树结点类型顺序栈
TNode elem[Stack_Size];
int top;
}TStack

void InitTStack(&S)
{ //初始化顺序栈
S.elem=new char[Stack_Size];
if(!S.elem) Error("Overflow!");
S.top=-1;
}

void Push_T(TStack &S , TNode T)
{ //压栈
if( S.top==(Stack_Size-1) ) Error("Stack Overflow!");
S.elem[++S.top]=T;
}

TNode Pop_T(TStack &S)
{ //出栈
if(S.top==-1) Error("Stack Empty!");
return S.elem[top--];
}

//****************************String.h******************************//
#include<iostream>
using namespace std;

typedef struct //动态顺序串
{
char *ch;
int len;
}String

Srting StrNeg(&Str) //求逆序串
{
String F;
for(i=0 ; i<length ; i++)
F.ch[i] = Str.ch[Str.len-1-i];
return F
}

int StrLen(&Str) //求串长
{
int i;
for(i=0 ; Str.ch[i]!='\0' ; ) i++;
return i;
}

//****************************Tree.h******************************//
#include<iostream>
#include"String.h"
#include"CStack.h"
#include"TStack.h"
using namespace std;

typedef struct
{ //二叉树结点
union data
{ //数据域
char opr; //运算符
int opn; //运算数
}
struct TNode *lchid , *rchild; //指针域
}TNode

typedef TNode *BiTree; //二叉树头结点

int Precedence(char opr)
{ //判断运算符级别函数；其中* /的级别为2，+ -的级别为1；
switch(opr)
{
case'+': case'-': return 1; break;
case'*': case'/': return 2; break;
case'(': case')':
case'#':
default:
return 0; break;
}
}

bool IsOperator(char opr)
{ //判断输入串中的字符是不是合法操作符
if(op=='+'||op=='-'||op=='*'||op=='/')
return true;
else
return false;
}

String Convert(String &Str) //将一个中缀串转换为后缀串
{
int i;
String Output; //输出串
Output.len=0;
CStack S;
InitCStack(S);
Str.len=StrLen(Str); //求的输入的串长
for(i=Str.len-1 ; i>=0 ; i--) //对输入串逆序扫描
{
if(Str.ch[i]>=48 && Str.ch[i]<=57) //假如是操作数，把它添加到输出串中。
{
Output.ch[Str.len-1-i]=Str.ch[i];
Output.len++;
}
if( Str.ch[i]==')' ) //假如是右括号，将它压栈。
Push_C( S , Str.ch[i] );
while( IsOperator( Str.ch[i] ) ) //如果是运算符
{
if( S.top==0 || GetTop(S)==')' || Precedence(Str.ch[i] ) >=Precedence( GetTop(S) ) )
{
Push_C( S , Str.ch[i] );
break;
}
else
{
Output.ch[Str.len-1-i]=Pop_C(S);
Output.len++;
}
}
if( Str.ch[i]=='(' ) //假如是左括号，栈中运算符逐个出栈并输出
{ //直到遇到右括号。右括号出栈并丢弃。
while( GetTop(S)!=')' )
{
Output.ch[Str.len-1-i]=Pop_C(S);
Output.len++;
}
}
}
while(S.top!=-1) //假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。
{
Output.ch[++Output.len-1]=Pop_C(S);
}

return StrNeg(Output); //输出Output的逆序即为所求前缀表达式
}

void CreatBiTree(&T , &Str) //由中缀表达式生成表达式二叉树
{
String F;
TStack S; //用以存放生成的二叉树结点
InitTStack(S);
F=Convert(Str); //求得S的前缀表达式
for(i=F.len-1 ; i>=0 ; i--)
{
if( !IsOperator(F.ch[i]) )
{
T=new TNode;
T->data=F.ch[i];
T->lchild=NULL;
T->rchild=NULL;
Push_T(S , T)
}
else
{
T=new TNode;
T->data=F.ch[i];
T->lchild=Pop_T( S );
T->rchild=Pop_T( S );
Push_T(S , T);
}
}
}

int Calc(int a, char opr, int b) //计算
{
switch (opr)
{
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
}

int Value(TNode *T) //求表达式二叉树的值
{
if (T->lchild == NULL &&T->rchild == NULL)
return T->data;
else
return Calc( Value(T->lchild) , T->data , Value(T->rchild) );
}

//****************************JudgeExp.h******************************//
#include<iostream>
#include"String.h"
#include"Tree.h"
using namespace std;

bool JudegExp(String Exp) //此函数验证式子是否正确，即是否符合运算规则。
{
char check;
int error=0;
int lb=0;
int rb=0;
if(StrLen(Exp)==1 && Exp.ch[0]!='-')
return false;
else if( (IsOperator(Exp.ch[0])&& Exp.ch[0]!='-' || IsOperator( Exp.ch[StrLen(Exp)-1] ) ) && Exp.ch[0]!='(' && Exp.ch[StrLen(Exp)-1]!=')' ) //此处若不加，在遇到某些式子时，会出现非法操作。
return false;
for(int m=0 ; m<StrLen(Exp) ; m++)
{
check=Exp.ch[m];
if(m==0 && check=='-' && (IsDigit(Exp.ch[1])!=0 || Exp.ch[1]=='(' ) ) check=Exp.ch[++m];
if( IsOperand(check) ); //如果是数字，跳过，不管。
else if(IsOperator(check))
{
if( check==')' )
{
rb++;
if( IsOperator(Exp.ch[m+1])&&(Exp.ch[m+1]=='+'||Exp.ch[m+1]=='-'||Exp.ch[m+1]=='*'||Exp.ch[m+1]=='/'||Exp.ch[m+1]=='^'||Exp.ch[m+1]==')' ) )
{
m++;
if( Exp.ch[m]==')' )
rb++;
}
else if( IsOperator(Exp.ch[m+1]) )
error++;
}
else if( check=='(' )
{
lb++;
if( Exp.ch[m+1]=='(' )
{
m++;
lb++;
}
else if(IsOperator(Exp.ch[m+1]) && Exp.ch[m+1]!='-')
error++;
}
else
{
if( IsOperator(Exp.ch[m+1]) && Exp.ch[m+1]=='(' )
{
m++;
lb++;
}
else if( IsOperator(Exp.ch[m+1]) )
error++;
}
}
else error++;
}
if(error==0 && lb==rb)
return(true);
else
return(false);
}

//****************************main.cpp******************************//
#include<iostream>
#include"CStack.h"
#include"TStack.h"
#include"String.h"
#include"Tree.h"
#include"JudgeExp.h"
using namespace std;

void Face() //输出简单界面即信息
{
cout<<" ※※※※※※※※※※※※ "<<endl;
cout<<" ※ 十进制计算器 ※ "<<endl;
cout<<" ※※※※※※※※※※※※ "<<endl;
cout<<" 试验092 曹津 "<<endl;
}

void main()
{
int n ;
c