当前位置:首页 >> 工学 >>

表达式用二叉树表示


数据结构程序报告(3)

2011.3.29

2. 需求分析:
(1)功能:表达式可以用二叉树表示,对于简单的四则运算,请实现以下功能 【1】对于任意给出的前缀表达式(不带括号) 、中缀表达式(可以带括号)或后缀表达式 (不带括号) ,能够在计算机内部构造出一棵表达式二叉树,并且图示出来(图形的形式) 。 【2】对于构造好的内

部表达式二叉树,按照用户的要求输出相应的前缀表达式(不带括 号) 、中缀表达式(可以带括号,但不允许冗余括)或后缀表达式(不带括号) 。 提示:所谓中缀表达式中的冗余括号,就是去掉括号后不影响表达式的计算顺序。例 如:(c+b)+a”中的括号是冗余的,可以表示成不冗余的“c+b+a” “ 。 (2)输入输出要求:请输入字符串表达式: 树形二叉树(图形显示) 中缀表达式为: 前缀表达式为: 后缀表达式为:

3. 概要设计: (算法)
分成两部分完成: 【1】前缀、中缀、后缀表达式->二叉树表达式 前缀表达式->二叉树表达式: (a)碰到操作数则把其值赋给相应的新申请的二 叉树结点,地址压栈; (b)碰到操作符则把其值赋给相应的新申请的二叉树,并从 栈中弹出两个地址,分别作为其右指针和左指针,然后再把其地址压栈,最后一个 地址即为二叉树的根结点地址。 中缀表达式->二叉树表达式:把中缀表达式转换成后缀表达式,然后再建立二 叉树。

后缀表达式->二叉树表达式: (a)碰到操作数则把其值赋给相应的新申请的二 叉树结点,若栈为空则地址压栈,若非空则取栈顶元素,若栈顶元素的左孩子为空 则当前结点设为其左孩子,左孩子为满则设为其右孩子再压栈; (b)碰到操作数则 把其值赋给相应的新申请的二叉树结点,取栈顶元素,若栈顶元素的左孩子为空则 设为其左孩子,左孩子为满则设为其右孩子开始那个元素地址为根结点地址,开始 时用变量 root 保存。 【1】二叉树表达式->前缀、中缀、后缀表达式 二叉树表达式->前缀表达式:对二叉树表达式进行前序遍历。 二叉树表达式->中缀表达式:对二叉树表达式进行中序遍历,若结点操作符的 优先级高于其左或右子树,在打印相应的子树之前先打印开括号,在打印相应的子 树最后在打印一个闭括号。 二叉树表达式->后缀表达式:对二叉树表达式进行后序遍历。

建立表达式树就是建立树中的每一个结点,将每一个结点链接起来就是整棵树。而在 建立深度低的结点时要将其左右指针指向之前建立的深度比它高一级的结点(如’*’要指

向’2’和’3’,而’+’又要指向’*’)。这样我们可以用栈来存放每次建立的结点,按 照优先级(表达式为中缀型)或顺序扫描表达式(表达式为波兰式与逆波兰式)建立每一个结点。 建立结点的顺序即为表达式求值的顺序。 如果扫描到操作数则直接新建一个左右指针为空的 结点,并压入结点栈中(存放结点指针)。遇到运算符时首先新建一个结点,然后从栈中依次 弹出两个结点,并让新建立的结点的左右指针域指向它们。当所有结点建立完毕时,如果表 达式没有错误(这里假设输入表达式正确),这时栈中应该只剩下一个结点,它就是所建立的 表达式的根结点。

4. 详细设计: (具体方法)
首先创建一个节点类 TNode:包含操作符 oper、左孩子 left、右孩子 right,isOper ()判断是否为操作符,getOperOrder()返回运算符 op 所对应的优先级,freeTree() 程序结束销毁二叉树,postOrder()先序遍历,preOrder()后序遍历,inOrder()中 序遍历, ExpTree1 后缀表达式生成二叉树, () ExpTree3 前缀表达式生成二叉树, () ExpTree2 ()中后缀表达式生成二叉树,count()求值函数,paint()输出函数 附程序: #include <iostream>

#include <stack> #include <queue> #include <string> #include<math.h> using namespace std; class TNode//节点类 {public: charoper; TNode *left; TNode *right; int s; int t; TNode() { left=right=NULL;

oper=0; } TNode(char op) { left=right=NULL;

oper=op;}}; boolisOper(char op)//判断是否为运算符 { charoper[]={'(',')','+','-','*','/','^'}; for(int i=0;i<sizeof(oper);i++)

{if(op==oper[i]) { return true; }} return false;}

intgetOperOrder(char op)//返回运算符 op 所对应的优先级 {switch(op) {case '(': return 1; case '+': case '-': return 2; case '*': case '/': return 3; case '^': return 4; default: //定义在栈中的右括号和栈底字符的优先级最低 return 0; }}

void freeTree(TNode *&p)//释放树 {if(p->left!=NULL) freeTree(p->left); if(p->right!=NULL) freeTree(p->right); delete(p); cout<<"Memory free ";}

void postOrder(TNode *p) //先序遍历 {if(p) {postOrder(p->left); postOrder(p->right); cout<<p->oper; }}

void preOrder(TNode *p) //后序遍历 {if(p) {cout<<p->oper; preOrder(p->left); preOrder(p->right); }}

void inOrder(TNode *p)//中序遍历 {if(p) { if(p->left) { if(isOper(p->left->oper) &&getOperOrder(p->left->oper) <getOperOrder(p->oper)) {cout<<"("; inOrder(p->left); cout<<")"; }else{ inOrder(p->left); }} cout<<p->oper; if(p->right) { if(isOper(p->right->oper) &&getOperOrder(p->right->oper) <=getOperOrder(p->oper)) {cout<<"("; inOrder(p->right); cout<<")"; }else{ inOrder(p->right);

} } } }

void ExpTree1(TNode *&p,stringstr)//后缀表达式生成二叉树 {stack<TNode*>nodeStack; char temp; int i=0; temp=str[i++]; while(temp!='\0') { if(temp!='\0'&&!isOper(temp))//不是运算符,则进栈 { p=new TNode(temp);//以 temp 为结点值构造二叉树结点 nodeStack.push(p); temp=str[i++];} else { p=new TNode(temp);

if(nodeStack.size()) {p->right=nodeStack.top();//若非空则弹栈并设为结点的右孩子 nodeStack.pop(); } if(nodeStack.size()) {p->left=nodeStack.top();//若非空则弹栈并设为结点的左孩子 nodeStack.pop(); } nodeStack.push(p); temp=str[i++];

}}} void ExpTree3(TNode *&p, string str)//前缀表达式生成二叉树 {stack<TNode*>nodeStack; char temp; int i=str.size()-1; temp=str[i--]; while(temp!='\0') { if(temp!='\0'&&!isOper(temp)) { p=new TNode(temp);//以 temp 为内容来建立新的结点 nodeStack.push(p); temp=str[i--];} else { p=new TNode(temp); if(nodeStack.size())//若栈顶指针所指结点左孩子为空 { p->left=nodeStack.top(); //则当前结点设置成其左孩子 nodeStack.pop(); } if(nodeStack.size())//若栈顶指针所指结点右孩子为空 {p->right=nodeStack.top();//则当前结点设置成其右孩子 nodeStack.pop();//栈顶元素左右孩子指针设置完毕弹出 } nodeStack.push(p); temp=str[i--]; }}}

void ExpTree2(TNode *&p, string str)//中缀表达式转换成后缀表达式生成二叉树 {stack<char> a; char temp; stringPostfixexp=""; int i=0; temp=str[i++]; while(temp!='\0') { if(!isOper(temp)) {Postfixexp+=temp; temp=str[i++];} else if(temp=='(')//进栈 {a.push(temp); temp=str[i++];} else if(temp==')'){ while(a.top()!='(')//脱括号 { Postfixexp+=a.top(); a.pop();//在碰到开括号和栈为空前反复弹出栈中元素 } a.pop(); temp=str[i++]; }else if(temp=='+'||temp=='-'||temp=='*'||temp=='/')//出栈{ while(!a.empty()&&a.top()!='('&&getOperOrder(a.top())>=getOperOrder(tem

p))//若栈非空栈顶不是左括号且栈顶元素优先级不低于输入运算符时, //将栈顶元素弹出到后缀表达式中,并且 str 下标加 1 { Postfixexp+=a.top(); a.pop();} a.push(temp); temp=str[i++]; }} while(!a.empty()) {Postfixexp+=a.top(); a.pop(); } ExpTree1(p,Postfixexp);} void count(TNode *p,int&height,int n)//求值函数 { if(p->left==NULL&&p->right==NULL) {if(n>height) height=n;} if(p->left!=NULL) count(p->left,height,n+1); if(p->right!=NULL) count(p->right,height,n+1); } void paint(TNode *p)//输出函数 {int height=0;

int h=0; int i; usingstd::queue; queue<TNode*>aQueue; count(p,height,1); TNode *pointer=p; TNode *lastpointer; if(pointer) { pointer->s=1; pointer->t=1; aQueue.push(pointer);} while(!aQueue.empty()) { lastpointer=pointer; pointer=aQueue.front(); aQueue.pop(); if(pointer->s>h) {cout<<endl; h=pointer->s;} if(pointer->t==1) {for(i=0;i<pow(2,height-pointer->s)-1;i++) cout<<" ";} else if(lastpointer->s!=pointer->s){

for(i=0;i<(pointer->t-1)*(pow(2,height-pointer->s+1)-1)+(pointer->t-1)-1+pow(2, height-pointer->s);i++) cout<<" ";} else {for(i=0;i<(pointer->t-lastpointer->t)*(pow(2,height-pointer->s+1)-1)+(pointer->tlastpointer->t)-1;i++) cout<<" ";} cout<<pointer->oper; if(pointer->left!=NULL){ pointer->left->s=pointer->s+1; pointer->left->t=pointer->t*2-1; aQueue.push(pointer->left);} if(pointer->right!=NULL){ pointer->right->s=pointer->s+1; pointer->right->t=pointer->t*2; aQueue.push(pointer->right); } }} int main() {string expression; TNode *tree; cout<<endl<<"请输入字符串表达式:"; cin>>expression;

if(isOper(expression[0])) ExpTree3(tree,expression); else if(isOper(expression[1])) ExpTree2(tree,expression); else ExpTree1(tree,expression); paint(tree); cout<<endl; cout<<"中缀表达式为:"; inOrder(tree); cout<<endl; cout<<"前缀表达式为:"; preOrder(tree); cout<<endl; cout<<"后缀表达式为:"; postOrder(tree); cout<<endl; freeTree(tree); cout<<endl; system("pause"); return 0;} 5.测试数据:

(1)请输入字符串表达式:-+1*234 + 1 2 * 3 4

中缀表达式为:1+2*3-4 前缀表达式为:-+1*234 后缀表达式为:123*+4memory freememory free memory free memory freememory free 请按任意键继续……………………….. (2)请输入字符串表达式:1+2*3-4 + 1 2 * 3 4

中缀表达式为:1+2*3-4 前缀表达式为:-+1*234 后缀表达式为:123*+4memory freememory free memory free memory freememory free 请按任意键继续……………………….. (3)请输入字符串表达式:123*+4-

+ 1 2 * 3

4

中缀表达式为:1+2*3-4 前缀表达式为:-+1*234 后缀表达式为:123*+4memory freememory free memory free memory freememory free 请按任意键继续……………………….. 测试截图:

6.总结: 程序调试中的问题及解决方法: 前缀表达式建树, 通过入栈出栈操作求出前缀表达式的 逆序,针对得到的逆序表达式通过后缀表达式建立二叉树的方法,遇到操作数则入栈,遇到 操作符则从栈中弹出两个操作数构建一棵小的二叉树, 然后将小树的根节点入栈以便于下次 操作。经过循环,小树“长成”大树,表达式读完二叉树即建成。 心得体会:由于之前的上机较简单,经过这次作业我才深深感受到编程的滋味,真是苦 中有乐,完成之后觉得知识点掌握的更加透彻了,因为有好多问题是不上机根本想不到的,

只有经过了实践才会有提高,自己还是太缺乏锻炼,应该多动手编程,从整理思路、编写代 码、调试程序修改错误等各方面不断完善自己 7.使用说明: 请输入字符串表达式:可为前缀、中缀、后缀表达式(程序自动判断)


相关文章:
二叉树的应用-代数表达式实现实验报告
二叉树的应用-代数表达式实现实验报告_电脑基础知识_IT/计算机_专业资料。编写一个程序,用二叉树表示代数表达式,二叉树的每个结点包括一个运算符或操作数,代数表达式...
表达式二叉树上机报告
表达式二叉树上机报告班级:11070227 姓名:周潇 学号:11070227 完成日期:2013.4.10 一、需求分析: (1)功能:表达式可以用二叉树表示,对于简单的四则运算,请实现以下...
表达式二叉树代码
"); } printf("\n 二叉树凹入法表示为:\n"); ShowTree(E,5); if(flag==1) {printf("\n 带括弧的中缀表达式为:"); WriteExpr(E); } else printf...
任务书算术表达式与二叉树
写一个 程序,实现基于二叉树表示的算术表达式的操作。 【任务要求】 假设算术表达式 Expression 内可以含有变量 (a~z) 、 常量 (0~ 9)和二元运算符(+,-,*...
树和二叉树——数据结构实验报告
实习报告题目:编写一个实现基于二叉树表示的算术表达式 Expression 操作程序 班级: 姓名: 学号: 完成日期// 一、 需求分析算术表达式 Expression 内可以含有变量(a...
数据结构实验二叉树
其次,以二叉树表示算 术表达式的基础上,设计一个十进制的四则运算的计算器。 如算术表达式:a+b*(c-d)-e/f 三、实验要求如果利用完全二叉树的性质和二叉链表...
算术表达式(例题)-二叉树
算术表达式(例题)-二叉树_教学案例/设计_教学研究_教育专区。最早提出遍历问题的是对存储在计算机中的表达式求值。例如: b (c-d))-e/f。表达式用树形来表示,如...
二叉树实验
7.6 用二叉树表示代数表达式 编写一个程序,用二叉树表示代数表达式,树的每一个结点包括一个运算符,代数表 达式由输入得到(其中只包含=,-,* ,/和用一个...
算术表达式与二叉树1
算术表达式二叉树1_数学_自然科学_专业资料。今日推荐 157份文档 2015国家公务员考试备战攻略 2015国考行测模拟试题及历年真题 2015国考申论押密试卷及答案 2015国...
四则运算表达式求值(栈+二叉树,c++版)
b) 本程序要求利用二叉树后序遍历来实现表达式的转换, 同时可以使用实验 2 的结果 来求解后缀表达式的值。 c) 在字符界面上输入一个中缀表达式,回车表示结束。...
更多相关标签: