基于二叉树的算术表达式计算与实现  

Evaluation of arithmetic expression based on binary tree

作　　者：陈海珠[1] 郑卉[1] 

机构地区：[1]重庆电子工程职业学院软件工程系,401331

出　　处：《中国科技信息》2012年第13期190-190,193,共2页China Science and Technology Information

基　　金：高职高专计算机类专业2012年度规划课题(JZW590112116)资助

摘　　要：算术表达式、栈的操作、二叉树的遍历这几个概念是数据结构教学中的基本内容。算术表达式求值是程序设计语言编译中的一个最基本问题,也是栈应用的一个典型例子。在数据结构中没有解决表达式与二叉树之间的相互转换关系。本文旨在研究表达式向二叉树的转换,即扫描输入的算术表达式,生成表达式的二叉树,再以先序遍历此二叉树求取表达式的值。为由一种算术表达式得出后缀、前缀两种表达式提供了一种新思路;同时以更简便的方式实现了算术表达式、二叉树这两者之间的转换。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.

关 键 词：算术表达式 表达式树 二叉树的遍历 树 数据结构 

分 类 号：TP311.11[自动化与计算机技术—计算机软件与理论]