四则混合运算表达式处理
计算机技术基础-独处的时候
实验题目：四则混合运算表达式处理
一．实验要求：
（1）
以逆波兰表示输入的算术表达式（假设每个操作数都以
单字符字母表示，即操作数的标识符为一个字母）；
（2） 初始化表达式树；
（3） 生成表达式树；
（4） 输出表达式树的各种遍历的结果；
（5）
打印表达式树；
（6） 删除表达式树；
（7）
设计相应的“菜单”，通过键盘输入选择，完成实验要
求的测试。
二、 概要设计
1.
数据结构的定义
表达式树的定义如下：
class Tree
{
private:
Stack * data;
存放数据
Stack * ope;
存放运算符
Node * head;
二叉树的根节点
public:
Tree();
构造函数，初始化一棵二叉树
~Tree();
析构函数
int Tree_Creat(string);
用逆波兰表达式生成表达式树
void Tree_delete();
将表达式树删除
bool if_creat();
判断是否已经生成了表达式树
int Depth();
计算表达式树的深度
int Tree_Depth(Node* p);
int Num();
计算表达式树的结点个数
int Tree_Num(Node *p);
int * At();
生成一个数组（用途在后文详细解释）
void at_all(Node* p,int*
a,int i);
void Display();
表达式树的打印
void ex_inorder();
中序遍历
void ex_preorder();
前序遍历
void ex_postorder();
后序遍历
void inorder(Node *p);
void preorder(Node *p);
void postorder(Node *p);
};
说明:
树的生成过程如同书本Page37中“表达式的计算”过程类似，只
是元素从操作
符和操作数变成了结点类型，但是拿来比较的还是结点的数据域。
在具体处理之前，先设置两个栈：
1．运算符栈ope：用于表达式处理过程中存放运算符结点。
2．操作数栈
data
：用于表达式处理过程中存放操作数结点。
然后从左到右读出表达式的各个符号，每读出一个符号按一下原则进行处理：
1.若读出的是操作数，则将该操作数压入操作数栈data，并依此读下一个
符号。
2.若读出的是操作符，则作进一步判断。
① 若读出的运算符优先级大于运算符栈栈顶运算
符的优先级，则将读出的
运算符压入运算符栈，并依此读下一个符号。
② 若读出运算符的优
先级不大于运算符栈栈顶的运算符优先级，则从操作
数栈连续推出两个运算符，并从运算符栈推出一个运
算符，然后将运算符视为
树根，操作数为子节点连起来，并将运算结果是做操作数压入操作数栈。在这<
br>钟情况下，当前读出的运算符下次将重新考虑（即不再读下一个符号）。
3.如此到最后，操作数栈栈顶结点即为表达式树的根节点，表达式树生成。
2．主要功能模块的功能
以逆波兰表示输入的算术表达式
初始化表达式树；
生成表达式树；
输出表达式树的各种遍历的结果；
打印表达式树；
删除表达式树；
3．主程序的流程及各程序模块之间的层次关系
主程序中，先初始化一棵树tree，进入while循环。
给出菜单：
******************************
|
1.生成一颗表达式树； |
| 2.输出各种遍历的结果； |
|
3.打印表达式树； |
| 4.删除表达式树；
|
| #.退出 |
*************
*****************
Choose==1时，调用树的生成函数
Tree_C
reat(string)；
Choose==2时，调用树的三种遍历函数：
ex_preorder(); 前序遍历
ex_inorder(); 中序遍历
ex_postorder();
后序遍历
Choose==3时，调用树的打印函数
Display()，给出树的树状打印形式；
Choose==4时，调用树的删除函数
Tree_delete();；
Choose==#时，跳出循环，程序终止
；
三．详细设计（主模块流程图）
1.树的生成Tree_Creat(string)：
从左到右读出表达式的各个符号，每读出一个符号按一下原则进行处理：
1.若读出的是操作数，则将该操作数压入操作数栈data，并依此读下一个
符号。
2.若读出的是操作符，则作进一步判断。
③ 若读出的运算符优先级大于运算符栈栈顶运算
符的优先级，则将读出的
运算符压入运算符栈，并依此读下一个符号。
④ 若读出运算符的优
先级不大于运算符栈栈顶的运算符优先级，则从操作
数栈连续推出两个运算符，并从运算符栈推出一个运
算符，然后将运算符视为树
根，操作数为子节点连起来，并将运算结果是做操作数压入操作数栈。在这钟
情
况下，当前读出的运算符下次将重新考虑（即不再读下一个符号）。
3.如此到最后，操作数栈栈顶结点即为表达式树的根节点，表达式树生成。
2.树的遍历（以先序遍历为例）
void Tree:: preorder(Node
*p)
{
if (p!=NULL)
{
cout <<
p->value; 输出其数据
preorder(p->lchild); 对其左结点进行先序遍历
preorder(p->rchild); 对其右结点进行先序遍历
}
}
3.树的打印Display()
由于是层次打印，所以采用层次遍历。遍
历从二叉树的根结点开始，首先将根结
点指针入队列，然后从对头取出一个元素，每取一个元素，执行下
面两个操
作：
（1）访问该元素所指结点，将数据域元素放到预置的数组里面；
（2）若该元素所指结点的左、
右孩子结点非空，则将该元素所指结点的左孩
子指针和右孩子指针顺序入队。
此过程不断进行
，当队列为空时，二叉树的层次遍历结束，操作数和操作符都依
次在数组里面，然后依照先后顺序，按每
一层的结点个数输出就可以打印二叉树。
4．主程序main()
主程序中，先初始化一棵树tree，进入while循环。
给出菜单：
******************************
|
1.生成一颗表达式树； |
| 2.输出各种遍历的结果； |
|
3.打印表达式树； |
| 4.删除表达式树；
|
| #.退出 |
*************
*****************
Choose==1时，从键盘以逆波兰表示输入的算术表达式，
输入有误则会报错，终
止程序运行；
Choose==2时，依次输出先序，中序，后序遍历结果；
Choose==3时，
给出树的树状打印形式；
Choose==4时，删除本棵树；
Choose==#时，跳出循环，程序终止
；
四．分析
1．调试中遇到的问题及对问题的解决方法
程序的编写还算顺利，到最后树的打印比较麻烦。
虽然层次可以用队列的方法分
出。但是由于生成的二叉树大多不是完全二叉树。同一层结点不是两两紧密
相连，
之间的间隔不好确定。
为了解决这一问题，我定义了一个数组，按满二叉树的结点层次编号，依次存放
1或0（该位
置结点存在即为1，不存在即为0）。因此在打印的过程中，根据这
个数组和层次遍历的结果，可以较为
合适的将二叉树用树状的形式打印出来。
2．算法的时间复杂度和空间复杂度。
时间复杂度：由于无论是生成，打印，遍历。算法的核心都是二叉树的遍历，所
以其时间复杂度是O（n
）；
空间复杂度：由于程序在遍历时使用了递归，所以空间复杂度为O(n)。
五、 使用说明及测试结果
1.使用说明：点击打开应用程序。会出现菜单，如下图：
输入选择1，然后接着输入一个逆波兰表示的表达式，回车即生
成一棵树
例如:输入abcd-*+ef-
接着输入2,则输出树的三种遍历结果。输入3，则输出输的树状
打印图。如下图：
然后选择4则删除树，选择1则重新生成一颗新树。
最后选择#，则退出程序，效果如下图：
若输入表达式有错的时候，会报错，如下图所示：
由于使用函数assert（），所以也可能出现对话框如下：
六、 源程序
****************************
********************************************
*
主函数 *
********
**************************************************
**************
#include
int
main(){
char choose;
Tree tree;
while (1)
{
cout<<
cout<<生成一颗表达式树；
|
cout<<输出各种遍历的结果； |
cout<<打印表达式树； |
cout<<删除表达式树；
|
cout<<退出 |
cout<<
cout<
cin>>choose;
if (choose=='#')
{
cout<<退出程序！
break;
}
else if
(choose=='1')
{
string str;
while (1)
{
cout<<输入逆波兰表达式：
cin>>str;
if (IsExp(str)) break;
else
{
cout<<！
cout<<
continue;
}
}
_Creat(str);
continue;
}
else if
(choose=='2')
{
if (_creat()==false)
{
cout<<请先生成一颗表达式树！
continue;
}
else
{
cout<<前序遍历：
_preorder();
cout<<中序遍历：
_inorder();
cout<<后序遍历：
_postorder();
}
continue;
}
else if (choose=='3')
{
if (_creat()==false)
{
cout<<请先生成一颗表达式树！
continue;
}
y();
continue;
}
else if
(choose=='4')
{
_delete();
continue;
}
else
{
cout<<输入错误，请重新选择！
continue;
}
}
return 0;
}
#include
#include
#include
#include
#include
using namespace std;
const
int maxsize=100;
int isletter(char x){
判断字符x是否为字母
if (x<='z'&&x>='a') return 1;
if (x=='+'||x=='-'||x=='*'||x=='') return -1;
else return 0;
}
bool
IsExp(string a){
判断字符串a是否可能表达式
int i=0;
char s=a[i];
while (s!='0')
{
if (isletter(s)==0)
{
return false;
}
i++;
s=a[i];
}
return true;
}
int Priority(char a,char b){
判断运算符a，b的优先级
if (a=='-'||a=='+') return
1;
else if (a=='*'||a=='')
{
if
(b=='*'||b=='')
{
return 1;
}
else return 0;
}
}
*******
**************************************************
***************
*
定义结点的数据类型 *
*********
**************************************************
*************
struct Node
{
char value;
Node *lchild;
Node *rchild;
};
********************
**************************************************
**
* 定义一个堆栈类
*
********************************************
****************************
class Stack
{
private:
int size;
堆栈大小
int top; 栈顶指针
Node *T; 指向堆栈的指针
public:
Stack(int s);
构造函数，初始化一个大小为s的堆栈
~Stack();
析构函数
bool Stack_empty();
判断堆栈是否为空
bool Stack_full();
判断堆栈是否已满
void Push(Node *n);
将结点n压栈
Node *Pop();
将栈顶元素弹出
friend class Tree;
将类tree视为stack的友元类
};
Stack::Stack(int
s){
size=s;
top=-1;
T=new
Node[size];
}
Stack::~Stack(){
size=0;
top=-1;
if (T) delete []T;
}
bool Stack::Stack_empty(){
if
(top==-1) return true;
else return false;
}
bool Stack::Stack_full(){
if (top==size-1) return true;
else
return false;
}
void Stack::Push(Node
*n){
assert (!Stack_full());
若堆栈已满则报错
top++;
T[top].value=n->value;
T[top].lchild=n->lchild;
T[top].rchild=n->rchild;
}
Node
*Stack::Pop(){
assert(!Stack_empty());
若堆栈为空则报错
Node *a=new Node();
a->lchild=T[top].lchild;
a->rchild=T[top].rchild;
a->value=T[top].value;
top--;
return a;
}
******************************
******************************************
*
定义一个队列类 *
*******
**************************************************
***************
class queue{
private:
Node *T; 指向队列的指针
int rear, front; 队头，队尾指针
int size; 队列大小
public:
queue(int s);
构造函数，初始化一个大小为s的队列
~queue();
析构函数
bool queue_empty();
判断队列是否为空
bool queue_full();
判断队列是否已满
void enqueue(Node *n);
将结点n从队尾入队
Node *dequeue();
将队头结点出队
friend class Tree;
将类tree视为queue的友元类
};
queue::queue(int s){
size=s;
T=new Node[size];
front=size-1;
rear=front;
}
queue::~queue(){
size=0;
front=size-1;
rear=front;
if (T) delete []T;
}
bool
queue::queue_empty(){
return front == rear;
}
bool queue::queue_full()
{
return (rear+1)%size==front;
}
void
queue::enqueue(Node *n)
{
assert(!queue_full());
rear = (rear + 1) %
size;
T[rear].value=n->value;
T[rear].lchild=n->lchild;
T[rear].rchild=n->rchild;
}
Node* queue::dequeue()
{
Node* a=new
Node;
assert (!queue_empty());
front=(front + 1)% size;
a->lchild=T[front].lchild;
a->rchild=T[front].rchild;
a->value=T[front].value;
return a;
}
***********************
*************************************************
* 定义一个二叉树类
*
********************************************
****************************
class Tree
{
private:
Stack * data;
Stack * ope;
Node *
head;
public:
Tree();
~Tree();
int
Tree_Creat(string);
void
Tree_delete();
bool
if_creat();
int Depth();
int Tree_Depth(Node* p);
int
Num();
int
Tree_Num(Node *p);
int * At();
void at_all(Node* p,int* a,int i);
void Display();
void
ex_inorder();
void
ex_preorder();
void
ex_postorder();
void
inorder(Node *p);
void
preorder(Node *p);
void
postorder(Node *p);
};
Tree::Tree(){
data=NULL;
ope=NULL;
head=NULL;
}
Tree::~Tree(){
if(data) delete data;
if(ope) delete ope;
if(head) delete head;
存放数据
存放运算符
二叉树的根节点
构造函数，初始化一棵二叉树
析构函数
用逆波兰表达式生成表达式树
将表达式树删除
判断是否已经生成了表达式树
计算表达式树的深度
计算表达式树的结点个数
生成类似于邻接数组
表达式树的打印
中序遍历
前序遍历
后序遍历
}
bool
Tree::if_creat(){
if (head)
{
return true;
}
return false;
}
int Tree::Tree_Creat(string s){
int
num=();
Stack stack_data(num);
Stack
stack_ope(num);
int i;
for
(i=0;i
if
(isletter(s[i])==0) return 0;
Node * no=new
Node;
no->value=s[i];
no->lchild=NULL;
no->rchild=NULL;
if
(isletter(s[i])==1)
{
stack_(no);
}
if (isletter(s[i])==-1)
{
if (stack_==-1)
{
Node*
a1=stack_();
Node* a2=stack_();
no->lchild=a2;
no->rchild=a1;
stack_(no);
continue;
}
if (stack_>=0)
{
if
(Priority(s[i],stack_ope.T->value)==0)
{
stack_(no);
continue;
}
}
Node* a1=stack_();
Node* a2=stack_();
no->lchild=a2;
no->rchild=a1;
stack_(no);
}
}
head=stack_();
return 1;
}
void Tree::Tree_delete(){
if(data)
delete data;
if(ope) delete ope;
if(head) delete head;
data=NULL;
ope=NULL;
head=NULL;
}
int
Tree::Depth(){
Node * p=head;
int
de=Tree_Depth(p);
return de;
}
int Tree::Tree_Depth(Node* p)
{
int
depthval;
int depthLeft=0,depthRight=0;
if ( !p) depthval = 0;
else
{
depthLeft=Tree_Depth( p->lchild );
depthRight=Tree_Depth( p->rchild );
depth
val=1+(depthLeft>depthRight?depthLeft:depthRight);
}
return depthval;
}
int
Tree::Num(){
Node * p=head;
int de=Tree_Num(p);
return de;
}
int Tree::Tree_Num(Node *p){
int num;
int right_num=0;
int left_num=0;
if ( p->lchild==0&&p->rchild==0) num = 1;
else
{
right_num=Tree_Num( p->lchild );
left_num=Tree_Num( p->rchild );
num=1+right_num+left_num;
}
return
num;
}
int* Tree::At(){
int
d=Depth();
int dall= pow(2,d)-1;
int
*a=new int[dall];
a[0]=1;
Node
*p=head;
at_all(p,a,0);
int j;
for (j=0;j
if (a[j]==1)
{
continue;
}
a[j]=0;
}
return a;
}
void
Tree::at_all(Node* p,int* a,int i){
if(p->lchild==NULL&&p->lchild==NULL)
{
return;
}
if (p->lchild!=NULL)
{
a[i*2+1]=1;
at_all(p->lchild,a,2*i+1);
}
if
(p->rchild!=NULL)
{
a[i*2+2]=1;
at_all(p->rchild,a,2*i+2);
}
}
void Tree::Display(){
int de=Depth();
int num=Num();
int
*a=At();
Node* p=head;
char *re=new
char[num];
int count=0;
queue qu(num);
e(p);
while (!=)
{
Node
*q=e();
re[count]=q->value;
count++;
if (q->lchild)
{
e(q->lchild);
}
if (q->rchild)
{
e(q->rchild);
}
}
cout<
double m_dis=52;
double f_dis=39;
count=0;
int k=1;
cout<
for (i=1;i
m_dis=m_dis2.0;
f_dis=39-(pow(2,i-1)-0.5)*m_dis;
cout<
for (j=0;j
if(a[k]==0)
{
zero_num++;
}
else
{
cout<
cout<
}
}
cout<
}
void
Tree::ex_preorder(){
Node *n2=head;
preorder(n2);
cout<
void Tree::ex_inorder(){
Node *n2=head;
inorder(n2);
cout<
void Tree::ex_postorder(){
Node *n2=head;
postorder(n2);
cout<
void Tree:: preorder(Node *p)
{
if (p!=NULL)
{
cout <<
p->value;
preorder(p->lchild);
preorder(p->rchild);
}
}
void Tree::inorder(Node *p)
{
if
(p!=NULL)
{
inorder(p->lchild);
cout << p->value;
inorder(p->rchild);
}
}
void Tree:: postorder(Node*p)
{
if (p!=NULL)
{
postorder(p->lchild);
postorder(p->rchild);
cout <
}
}