二叉树表达式求值.doc

一、程序设计的基本思想，原理和算法描述：表达式建树原理：对表达式先找到运算级最低的运算操作符，并将其作为该表达式的根结点，该运算符左右两段表达式分别作为其左右子树。1.若该运算操作符位于表达式首，则其一定是“-”，此时左子树为空；2.若该运算操作符是一对括弧（括弧嵌套情况）则化简（把括弧去掉），对表达式构造二叉树；表达式不合法情况：1.表达式首为：“+”、“*”、“/”、“.”、“）”；2.表达式尾为：“+”、“-”、“*”、“/”、“.”、“（”；表达式合法情况：1.表达式非首位置： ??????????????? a.“（”之前只能为：“+”、“-”、“*”、“/”、“（”；???? b.“）”之前只能为：“）”、数字“0-9”;???? c.“+”、“*”、“/”之前只能为：“）”、数字“0-9”；???? d.“-”之前只能为：“（”、“）”、数字“0-9”；???? e.“.”之前只能为： 数字“0-9”；表达式求值：将操作数全部转化为double数据类型进行求解。测试数据：??? 1. -((2.5+2.5)/(3-1)*4+(10-8)*6)/(4-2)+(-2*(4+1)/(3-1)*2+1)+1??? 2. -((((3-1)/2+2.5-(3-4+6))/2 -3*2/1)+1.5)*2-3*3/2/(5-3)??? 3. 1000000000*2000000000/4??? 4. 200.3.3*32.1??? 5. 99999/11??? 6. (45-33)*2-3+4/2*5-3??? 7. -(45-33)*2-3+4/2*5-3 二、源程序及注释：//ExpnBiTree.cpp#includestdio.h#includestring.h#includestdlib.h#define STATUS int#define OK 1#define ERROR 0#define EXP_LEN 100 //定义表达式的最大长度#define DATA_LEN 20 //定义每个操作数的最大长度typedef struct BinaryTree{??? int dflag;?????? //标志域，值为1，data[]存放操作运算符;值为0，data[]存放操作数??? char data[DATA_LEN+1]; //数据域，存放：操作运算符 或 操作数??? struct BinaryTree *lchild,*rchild; //分别指向结点的左、右子树}BiTNode,*BiTree;??? //定义二叉树结点 及 二叉树类型指针STATUS CreateBiTree(BiTree bt,char *p,int l);//创建二叉树，并用bt返回树的根地址，p为表达式的首地址，l为表达式的长度STATUS Calculate(BiTree bt,double rst);//计算表达式的值，bt为据表达式创建的二叉树，用rst返回表达式的值STATUS PreOrderTraverse(BiTree bt); //先序遍历二叉树bt，输出先序遍历序列STATUS InOrderTraverse(BiTree bt);?? //中序遍历二叉树bt，输出中序遍历序列STATUS PostOrderTraverse(BiTree bt); //后序遍历二叉树bt，输出后序遍历序列STATUS DestroyBiTree(BiTree bt);??? //销毁二叉树void main(){??? int n,l,i;?? //n标志量，值为0，退出程序；l存储表达式的长度；i一般变量??? char expn[EXP_LEN+1];??????????? //存放表达式??? double rst;????????????????????? //存放表达式计算结果??? BiTree bt=NULL;????????????????? //声明一个二叉树??? do??? {??????? i=0;??????? printf(请输入合法的表达式:\n);??????? gets(expn);??????? for(i=0,l=0;expn[i]!=\0;i++) //去掉表达式中的空格，并计算表达式的长度??????????? if(expn[i]!= )expn[l++]=expn[i];??????? expn[l]=\0;??????? printf(正在构建二叉树……\n);??????? if(CreateBiTree(bt,expn,l))printf(二叉树构