实验三实验报告
1120131317 周任然
1、简易计算器
（1）问题描述
由键盘输入一算术表达式， 以中缀形式输入， 试编写程序将中缀表达式转换成一棵二叉 表达式树，通过对该的后序遍历求出计算表达式的值。
（2）基本要求
要求对输入的表达式能判断出是否合法。不合法要有错误提示信息。
将中缀表达式转换成二叉表达式树。
后序遍历求出表达式的值
（3）数据结构与算法分析 一棵表达式树，它的树叶是操作数，如常量或变量名字，而其他的结点为操作符。
建立表达式树。二叉树的存储可以用顺序存储也可用链式存储。 当要创建二叉树时，
先从表达式尾部向前搜索， 找到第一个优先级最低的运算符， 建立以这个运算符为数据元素 的根结点。
注意到表达式中此运算符的左边部分对应的二叉绔为根结点的左子树， 右边部分
对应的是二叉绔为根结点的右子树， 根据地这一点， 可用递归调用自己来完成对左右子树的 构造。
求表达式的值。求值时同样可以采用递归的思想，对表达式进行后序遍历。先递归 调用自己计算左子树所代表的表达式的值，再递归调用自己计算右子树代表的表达式的值， 最后读取根结点中的运算符， 以刚才得到的左右子树的结果作为操作数加以计算， 得到最终 结果。
（ 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 本程序包含四个模块：主程序模块； 二叉树单元模块(实现二叉树的抽象数据类型，包 括结点和指针的定义)；顺序栈单元模块(实现顺序栈的抽象数据类型，包含结点和指针的 定义)；字符串单元模块 (实现字符串的抽象数据类型 )。四个模块之间调用关系为主程序模
块二叉树模块，二叉树模块调用顺序栈模块。
详细设计
struct TNode *lchild *rchild
struct TNode *lchild *rchild
顺序栈类型。
#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);
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; };
// 动态顺序串
// 求串长
// 求逆序串
// 求顺序栈长度
// 取栈顶元素
// 二叉树结点
// 运算符
// 操作数
}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) {
bool IsOperator(char opr) {
// 判断输入串中的字符是不是合法操作符
// 将一个中缀串转换为后缀串，// 输出串// 对输入串逆序扫描
// 将一个中缀串转换为后缀串，
// 输出串
// 对输入串逆序扫描
Output.ch[i]=Str.ch[i];
Output.length++; }
// 假如是操作数，把它添加到输出串中。
if( Str.ch[i]==')' )
// 假如是右括号，将它压栈。
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) {
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 expressi on is "<<N<<e ndl;
cout<< "To do ano ther calculatio n? [Y/N]";
cin> >e; if(e== ' 'flag=1;
else flag=0; }while(flag)
}//main
测试结果
-I a c
* C\U 5ers\le novoXDes kto 閃款据結唏黑程 ?i+\W?\X01\calc .ene
［匸d回丨富1
十谜制四则运算计算器
试验的2曹津
JM HI. ■Ml JR1 IM. J
请输入要计算的表达式：
12-<-4>*?20+3/5>*8/5>*<-4>
结果是： -515.3^
\ J
iff- IM iM.
请输入要计算的表达式：
-<22.7-420?.3>Z<<2.4+1.6>*12>+4.4-2.9
结臬是: SB .7
请输入要计算的表达式：
1 0-<?3>h<<21*3/5>*d/3>*<-2> 酱果是： -弟5-6
附录（带注释的源程序）
〃****************************CStack h***************************** #in clude<iostream> using n amespace std;
#defi ne Stack_Size 100
//字符类型顺序栈//
//字符类型顺序栈
//初始化顺序栈
{
char elem[Stack_Size]; int top;
}CStack
void In itCStack(&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******************************//
//*
**************************
*TStack.h
*****************************
*//
#include<iostream>#include"Tree.h" using namespace std;#define Stack_Size 100typedef struct{TNode elem[Stack_Size]; int top;}TStack//
#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--];}// 出栈//****************************
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);
// 求的输入的串长
// 求的输入的串长
// 对输入串逆序扫描
// 假如是操作数， 把它添加到输出
// 假如是右括号，将它压栈。
// 如果是运算符
|| GetTop(S)==')' ||
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 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++;
}
}
// 假如是左括号， 栈中运算符逐个//
// 假如是左括号， 栈中运算符逐个
// 直到遇到右括号。右括
出栈并输出
{
号出栈并丢弃。
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); 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;
}
}
// 由中缀表达式生成表达式
// 用以存放生成的二叉树结
// 求得 S 的前缀表达式
// 计算
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) );
}#include<iostream>
}
#include<iostream>
#include"String.h" #include"Tree.h" using namespace std;
bool JudegExp(String Exp) 是否符合运算规则。
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[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]==' A'||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<<"
cout<<"
cout<<"
cout<<"
// 输出简单界面即信息
※※※※※※※※※※※※
※ 十进制计算器 ※※※※※※※※※※※※ 试验 092 曹津
"<<endl;
※ "<<endl;
"<<endl;
"<<endl;
void main()
{
int n ;
char e;
int flag;
String Str;
// 供用户输入的表达式字符串
Face();
// 输出界面及相关信息
do {
}
cout<< ” Please input an expression: ” <<endl;
cin>>Str;
JudgeExp(Str); T=CreatBiTree(Str); n=Value(T);
// 判断输入的表达式是否合法。
// 生成表达式二叉树
// 计算表达式的值
cout<< ” The value of this expression is ” <<N<<endl;
cout<< ” To do another calculation? *Y/N+ ” ;
cin>>e;
if(== 'y') flag=1; else flag=0; }while(flag)
相关热词搜索： 实验 报告