基于二叉树的算术表达式计算与实现
科技教育创新
Education
DOI：10.3969/j.issn.1001-8972.2012.13.135
中国科技信息2012年第13期 CHINA SCIENCE AND TECHNOLOGY INFORMATION Jul.2012
基金项目：高职高专计算机类专业2012年度规划课题(JZW590112116)资助
基于二叉树的算术表达式计算与实现
Evaluation of arithmetic expression based on binary tree
陈海珠 郑卉
重庆电子工程职业学院软件工程系 401331
摘 要
算术表达式、栈的操作、二叉树的遍历这几个概念是数据结构教学中的基本内容。算术表达式求值是程序设计语言编译中的一个最基本问题，也是栈应用的一个典型例子。在数据结构中没有解决表达式与二叉树之间的相互转换关系。本文旨在研究表达式向二叉树的转换，即扫描输入的算术表达式，生成表达式的二叉树，再以先序遍历此二叉树求取表达式的值。为由一种算术表达式得出后缀、前缀两种表达式提供了一种新思路；同时以更简便的方式实现了算术表达式、二叉树这两者之间的转换。关键词
算术表达式；表达式树；二叉树的遍历；树；数据结构Abstract
Arithmetic expression, stack and binary tree are fundamental concepts in studying data structure. Evaluating arithmetic expression is one of basic problems in compiling of programming languages and one of typical application instances of the stack. In the course of data structure, there are seldom solutions for converting arithmetic expression to binary tree. This paper discusses this problem: scan the input arithmetic expression, convert it to a binary tree, and evaluate the expression by inorder traveling the tree. This paper provides a new method for obtaining the prefix and suffix expressions from an infix expression and converts arithmetic expression to binary tree in an efficient way.Keywords
arithmetic expression; expression tree; traversal of binary tree; tree; data structure
结构，原因在于只要以不同顺序遍历此树就能够生成表达式的不同表示。
表达式树具有以下特点：1）操作数都是叶子结点；2）运算符都是内部结点。
从图1可看出，操作符和操作数都变成了树中的结点。对操作数是多位数的情况，为方便处理，在结点的定义上，内部结点以optr保存操作符，而叶子结点以data保存操作数，各结点均以lchild和rchild分别指向结点的左右子树。表达式树的构建步骤如下：
1 概述
数学表达式求值是程序设计语言编译中的一个最基本问题。表达式的求值是栈应用的一个典型例子。表达式前缀、中缀、后缀三种形式，相应的也就有前缀、中缀（普通计算器）、后缀三种计算器。数据结构教材使用二叉树表示一个算术表达式，前序、中序、后序遍历该二叉树分别得到前缀、中缀、后缀表达式，再把这些表达式用堆栈来实现不同的计算器。
如何由算术表达式得到其二叉树表示，在数据结构的教材上鲜有提及，而在所发表的论文中对此问题的解决办法通常是采用堆栈作为辅助的存储结构来实现算术表达式向二叉树的转换。本文不使用堆栈，采用递归编程的方式来实现表达式向二叉树的转换，然后通过先序遍历该二叉树来求出表达式的值。采用这样的方式来构建二叉树更简便而有效，由于不需要转换成某种表达式也不需要使用堆栈，本文的方法可以直接地求出表达式的值。
为方便讨论，我们将由表达式转换成的二叉树称为表达式树。
2 表达式树的构建
首先我们来观察二叉树如何来描述一个表达式。如图1所示，表达式树的结点存储操作数和二元操作符（+、-、*、/）。由此可看出，二叉树是存储算术表达式的最佳数据
图1 表达式树
1）读入表达式的一部分产生相应的二叉树后，在读入运算符时，运算符与根接点的运算符比较优先级的高低：a)高：读入的运算符作为根接点的右子树，原来的右子树作为读入运算符的左子树；b)不高于：读入的运算符作为树根，原来的二叉树作为它的左子树。
2)遇到括号，先使括号内的表达式产生一棵二叉树，在把它的根接点连到前面已产生的二叉树的右子树上。
使用函数createTree( )来创建表达式树，参照上述步骤，设计了函数getPriority( )来获取操作符之间的优先级：对'+'和'-'返回1；对'*'和'/''*'返回2；其他情况返回0。在创建表达树的过程中，操作符和操作数都变成了树中的结点，当然对他们的处理方式是不一样的，所以在程序设计上设置函数getNode( ) 来处理表达式树的结点。特别是当遇到优先级最高的”( )”操作时，getNode( )还需要去调用函数createTree( )来将”( )”内的子算术表达式构建为一棵子树。
BTNode *getNode(char *str, int &pos){ BTNode *createTree(char *str, int &pos);
BTNode *p = new BTNode; char ch = str[0]; if(isdigit(ch)) { int i = 0; char data[MAX_LEN]; while(isdigit(ch=str[i])) data[i++] = ch;
p->data = atoi(data); pos += i; } else if(ch =='+' || ch =='-' || ch =='*' || ch =='/')
{ p->optr = ch; p o s += 1; }
else if(ch =='(') { pos += 1; p =
createTree(str+1, pos); }
else if(ch ==')') { pos += 1; return NULL; }
else if(ch=='\0') return NULL; return p;}
BTNode *createTree(char *str, int &pos)
{ int pos1 = 0; B T N o d e *l c h i l d = getNode(str+pos1, pos1);
BTNode *root = getNode(str+pos1, pos1);
B T N o d e *r c h i l d = getNode(str+pos1, pos1);
root->lchild = lchild; root->rchild = rchild;
BTNode *node; while((node=getNode(str+pos1,pos1)))
{ if(getPriority(root->optr) > getPriority(node->optr))
{ n o d e ->lchild=root; n o d e ->rchild=getNode(str+pos1, pos1); root = node; } else { n o d e ->lchild=root->rchild; r o o t ->rchild=node; n o d e ->rchild=getNode(str+pos1, pos1); } } pos+=pos1; return root;}
3 表达式的计算
输入表达式对应的字符串，对改字符串从左到右逐个读取每一个字符，做相应的处理后按照前述步骤构建与表达式对应的表达树，表达式树建立后，以先序遍历的方式求出整个表达式的值。
int result(BTNode *b) /*采用先序遍历表达式树方式来计算表达式的值*/
{ int n1, n2; switch(b->optr) { case'+': n1=result(b->lchild);//计算左子表达式
n2=result(b->rchild);//计算右子表达式
b->data=n1+n2;break; (对'-'、'*'、'/'的处理与'+'的类似，此处省略之)
default: return b->data; } return b->data; }
以及创新内容进行阶段性答辩来考核，查看学生主动建构知识的能力。允许学生根据教学基本要求和个人意愿选择实验项目。为支持和鼓励学生参加各种开放实验项目，学校采取适当的激励措施，根据成果或者获得奖励的层次给予学分。
总之，开放实验教学内容的制定应该遵循“面向全体、因材施教、形式多样、讲究实效”的原则，根据不同层次的学生和要求制定开放内容，确实有效的培养学生的实践和创新能力。
3.2加强开放式实验教学的教师队伍为了及时解决学生在实验中遇到的问题，指导学生完成开放实验项目，教师必须努力提高自身的理论素养，积极探索新的实验内容和实验方法，掌握更多相关实验技能和专业技术知识，具有更加丰富的教学理论和实际经验，才能做好教学内容和教学体系的改革，更好的满足开放式实验教学的要求，给予学生在实验过程中正确的引导。教师队伍的整体素质决定一个学校的办学层次和水平。在采取多种形式引进高素质人才的同时，鼓励教师通过各种方式来提高自身的素质。我院注重对教师尤其是青年教师的培养，实行青年教师导师制，对每位新进教师安排一位导师，在教学、科研等各方面进行指导。我院经常聘请著名相关领域的专家学者不定期进行座谈会，指导教师实际应用能力和科研能力。在校企合作人才培养过程中，采取合作研发、企业实践等措施，鼓励教师积极参与，将自身的专业知识融入实际应用中，切实感受实践教学与理论教学的差距，确定自身素养提高的具体计划；及时了解相关领域发展动态、对人才能力和素质的需求，确保在实验教学中正确引导学生实践能力。
在开放式实验教学过程中，教师和实验技术人员必须把相关课程知识融合在一起，在教学过程中及时关注学生的接受能力和创新能力，开发和设计出更多设计性和创新性实验项目。要不断更新教学内容，改革教学和考试方法，融能力培养于教学之中，加强与学生的交流，真正做到既传授知识又培养动手能力。鼓励实验室开放，鼓励教师和实验技术人员积极参与更多的开放式实验教学和科研型实验项目，把开放式实验教学作为工作量计算和实验技术人员奖酬分配上一个较为重要的比重。
4 结语
我院已逐步着手开放实验网络信息化管理平台的建设，通过计算机实验教学中心，结合我校现有的条件如一卡通系统，门禁系统，监控系统，教务管理系统等，对我校部分计算机基础课程进行试点开放式实验管理。我院现有开放的基础实验有《大学英语》课程、《大学信息技术基础》和计算机程序设计语言类课程试点进行开放式实验教学管理；综合实验也逐步开展，小有成效，如我院学生获得“国信蓝点杯”全国软件专业人才设计与开发大赛二等奖等；同时，我院新建的几个专业创新实验室已开放给学生使用，在江苏省大学生电子设计大赛等获得了较好的名次。
开放实验教学建设是一个长期过程，我院在不断深入研究科研创新型实验教学过程中，还应与全校实验中心建立合作关系，开展开放式实验教学的研究，扩大研究领域，不断完善，培养出更多创新型人才。参考文献
[1] 宋象军,汪春华,刘太林,等.营造实验室开放环境,引导学生自主实验[J].实验技术与管