简单计算器的实现
一、实验内容:
a.重写程序清单4-1的递归下降计算器,使其根据3.3.2节的申明返回一个语法树。
b.写出一个作为参数的函数,他得到由a部分的代码生成的语法树,并由语法树来返
回计算的值。
二、基本思路:
按题目的要求,用户输入一个表达式,在a问返回该表达式的语法树,b问利用a问返回的语法树,通过语法树的移动,最终返回所输入的表达式的结果。分析这个问题,首先应该确立此语法树的结构。根据 3.3.2节的分析可知,可以用二叉树来存储这棵语法树。此二叉树的每个结点都有一个数值及一个左孩子和一个右孩子。当结点是内部结点时,它存储的数值为运算符,并且它的左右孩子都不为空;
当它为叶子结点时,它存储的是一个整数值,并且它的左右孩子都为空。当读入一个表达式时,先根据表达式的文法把它转化为一个语法树,并返回此语法树的根结点,然后利用这个返回的结点指针,利用语法树的移动,最终计算出这个语法树所存储的表达式的值。因为只有叶子结点存储数据,而内部结点存储的是运算符,所以首先要识别每个结点是叶子结点还是内部结点,才能对其进行正确的处理。由前面两种结点的构成可以得知,叶子结点的左右孩子都为空,而内部结点的左右孩子都不为空,这就可以做为区分这两种结点的重要标志。从底层叶子结点开始向上演变,用运算的结果取代内部结点的值,并把此内部结点转变为叶子结点,最终在根结点出返回表达式的值。
三、程序实现:
a.创建一个二叉树的类,包含它的一些信息:节点存的值、左子树指针以及右子树指
针。
b.实验环境是VC++;
c.只是在书中4-1的程序中加一个创建树的语句就可以实现。
d.运行的结果是一棵中序遍历的语法树,#表示此节点的深度(根节点的深度为0)。
e.举例:如先输入算式:12*96+13*(56+36);
四、
◆源文件tree.h的程序代码:
//"tree.h"
//the declaration fo class tree with two children
#ifndef tree_h
#define tree_h
class Tree
{
public:
enum Nodekind {add,sub,mul,leaf}; //节点类型+-*及叶子private:
int val;
Nodekind kind;
Tree* leftchild ;
Tree* rightchild;
public:
Tree(Nodekind k,Tree* l,Tree* r);
Tree();
void SetLeft(Tree* l); //设置左子树void SetRight(Tree* r); //设置右子树
Tree* Left(); //返回左子树指针
Tree* right(); //返回左子树指针int LeftVal( ); //返回右子树的值
int RightVal(); //返回左子树的值
void setvalue(int v); //设置节点的值
void setKind(Nodekind n); //设置节点类型
int value(); //返回结点值
int ofkind(); //返回结点类型
};
#endif
◆源文件tree.cpp的程序代码:
//"tree.cpp"
//the difination of class Tree
#include
#include"tree.h"
Tree::Tree(Nodekind k,Tree* l,Tree* r)
{
kind=k;
leftchild=l;
rightchild=r;
if(kind==add)
val=leftchild->value()+rightchild->value();
else if(kind==sub)
val=leftchild->value()-rightchild->value();
else if(kind==mul)
val=leftchild->value()*rightchild->value();
else if(kind==leaf) ;
else
{
cout<<"Warning:NO such expression include!!\n";
val=0;
}
}
Tree::Tree()
{
val=0;
kind=add;
leftchild=NULL;
rightchild=NULL;
}
void Tree::SetLeft(Tree* l) //设置左指针
{
leftchild=l;
}
void Tree::SetRight(Tree* r) //设置右指针
{
rightchild=r;
}
Tree* Tree::Left() //返回树的左指针
{
return leftchild;
}
Tree* Tree::right() //返回树的右指针
{
return rightchild;
}
int Tree::LeftVal( ) //返回左孩子树的值,即:返回左节点的存的值{
return leftchild->value();
}
int Tree::RightVal() //返回右孩子树的值,即:返回右节点的存的值{
return rightchild->value();
}
void Tree::setvalue(int v) //设置树节点的值
{
val=v;
}
void Tree::setKind(Nodekind n) //设置节点的类型:add,sub,mul,leaf {
kind=n;
}
int Tree::value()
{
return val;
}
int Tree::ofkind() //返回节点的类型
{
return (int)kind;
}
◆源文件calculate.cpp的程序代码:
//"calculate.cpp"
//---design a calculator
#include
#include
#include
#include"tree.h"
char token;
Tree* exp(void);
Tree* term(void);
Tree* factor(void);
void printTree(Tree *);
void error(void)
{
fprintf(stderr,"error\n");
exit(1);
}
void match(char expectedToken)
{
if(token==expectedToken)
token=getchar();
else
error();
}
main()
{
printf("输入你要计算的表达式:\n");
token=getchar();
Tree* result;
result=exp();
printTree(result); //建立语法树
if(token='\n')
printf("Result=%d\n",result->value()); //输出表达式结果
else
error(); //错误处理
return 0;
}
Tree * exp(void)
{
Tree* suboot;
Tree* newsuboot;
suboot=term();
while((token=='+')||(token=='-'))
switch (token)
{
case'+':
match('+');
newsuboot=(Tree*)new Tree(Tree::add,suboot,term()); //实现语法树建立
suboot=newsuboot;
break;
case'-':
match('-');
newsuboot=(Tree*)new Tree(Tree::sub,suboot,term());
suboot=newsuboot;
break;
}
return suboot; //返回一棵语法树的根节点指针
}
Tree* term(void)
{
Tree* suboot;
Tree* newsuboot;
suboot=factor();
while(token=='*')
{
match('*');
newsuboot=(Tree*)new Tree(Tree::mul,suboot,term()); //实现语法树建立
suboot=newsuboot;
}
return suboot; //返回一棵语法树的根节点指针
}
Tree* factor(void)
{
Tree* suboot;
int temp;
if(token=='(')
{
match('(');
suboot=exp();
match(')');
}
else if(token>='0'&&token<='9')
{
ungetc(token,stdin);
scanf("%d",&temp);
suboot=(Tree*)new Tree(Tree::leaf,NULL,NULL); //为叶子结点故其孩子结点为空
suboot->setvalue(temp);
token=getchar();
}
return suboot;
}
void printTree(Tree* root) //用前序遍历输出该树的节点
{
Tree* subroot=root;
if(subroot==NULL)
return;
else
{
if(subroot->Left()==NULL&&subroot->right()==NULL)
printf(" leaf:%d\n ",subroot->value());
else
if(subroot->ofkind()==0)
printf("operator+ ");
else if(subroot->ofkind()==1)
printf("operator- ");
else if(subroot->ofkind()==2)
printf("operator* ");
else
printf("leaf");
printTree(subroot->Left());
printTree(subroot->right());
}
}
五、实验运行结果:
用JSP编写的一个简易计算器实现代码如下: <%@ page contentType="text/html;charset=gb2312"%>
//接收运算符号 String oper=request.getParameter("op"); Double dnum1=0.0; Double dnum2=0.0; Double result=0.0; //java中String -> int if(num1!=null&&num2!=null&&oper!=null) { dnum1=Double.parseDouble(num1); dnum2=Double.parseDouble(num2); //计算 if(oper.equals("+")) { //加 result=dnum1+dnum2; } else if(oper.equals("-")) { //减 result=dnum1-dnum2; } else if(oper.equals("×")) { //乘 result=dnum1*dnum2; } else { //除 result=dnum1/dnum2; } } %>