王潇00348226表达式.cpp

表达式二叉树

// 我真诚地保证：
    
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。

// 在此，我感谢 XXX, …, XXX对我的启发和帮助。下面的报告中，我还会具体地提到
// 他们在各个方法对我的帮助。
 
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。

// 我从未没抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。

    // 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
    
//*****************************************
//***         二叉树   4. 2             ***
//***                                   ***
//***            00348226  王潇(第二组) ***
//***          创建日期：  04-10-2      ***
//***          最后修改：  04-10-4      ***
//*****************************************

//程序功能：实现输入的前后缀表达式均可构造树并打印，并再转化为任意形式的表达式
//          可循环实现操作
//主要算法：即以三种周游方法为主，附以各种实现题目要求的操作


#include <iostream.h>
#include <string.h>
#include <stack>
#include <algorithm>
#include <conio.h>
using namespace std;     //应用stl函数库中的栈模板
    



//类名：BinaryTreeNode
//功用：二叉树的结点类
//类参数： 一个数据域字符变量，左右指针
//类函数： 两个不同参数的构造函数与三个函数外部接口
class BinaryTreeNode
{
public:
	char element;        //数据域为一个字符变量，存储表达式的一个字符   
	BinaryTreeNode * left;
	BinaryTreeNode * right;
	BinaryTreeNode()     //不带参数的构造函数
	{
		element = '\0';
		left = NULL;
		right = NULL;
	}

	BinaryTreeNode( char ch ) //将字符变量初始化为输入的参数
	{
		element = ch;
		left = NULL;
		right = NULL;
	}
	char value()   //返回数据域
	{
		return element;  
	}
	BinaryTreeNode * leftchild() const //返回左指针
	{
		return left;
	}
	BinaryTreeNode * rightchild() const //返回右指针
	{
		return right;
	}
};

const int MaxNode = 100; //定义常量为100
BinaryTreeNode tempNode[MaxNode];  //定义类数组为全局变量，用于存储输入的表达式，一个字符占用一个类

typedef stack<BinaryTreeNode *>  astack; //定义栈，栈元素为结点指针

//以下两函数功能为根据输入的表达式为前缀或后缀分别构造表达式树
//函数参数为输入的表达式，返回参数为表达式树的根结点
BinaryTreeNode * CreatePreOrder( char * s );
BinaryTreeNode * CreatePostOrder( char * s );

//按树的形状打印表达式树，root为树的根结点，level表示结点所在层次,初次调用时level=0
void Print(BinaryTreeNode * root, int level);

//以下三个函数功用为根据已有的表达式树，分别输出前缀，中缀，后缀表达式
//参数为树的跟结点
void OutputPreOrder( BinaryTreeNode * root );
void OutputInOrder( BinaryTreeNode * root );
void OutputPostOrder( BinaryTreeNode * root );


void main()
{//主函数入口点
	BinaryTreeNode * root = NULL;
	char array[MaxNode];  //储存输入的表达式
	char ch = 'y';
	int type = 0;         //储存输入表达式与输出表达式的类型
	int i = 0;   //定义并初始化各参量

	do
	{
		type = 0;
		ch = 'y';
		root = NULL;  
		for( int i = 0; i <= MaxNode - 1; i++ )
			array[i] = '\0';             //执行每次操作前，先初始化各参量

		cout<<"请输入待输入的表达式类型(1为前缀，2为后缀)"<<endl;
		do{
			 cin>>type;                 
			 if( type != 1 && type != 2 )
				 cout<<"错误，请重新输入"<<endl;
		}while(type != 1 && type != 2);           //输入类型，错误时循环输入

		cout<<endl<<"请输入相应的表达式(仅由字母与+-*/组成)"<<endl;
        Start:          
			cin>>array;                           //输入表达式，错误时循环输入
			for( i = 0; i <= (int) strlen( array ) - 1; i++ )
				if( !((array[i] >= 'a' && array[i] <='z') || (array[i] >= 'A' && array[i] <='Z')
					|| array[i] == '+' ||array[i] == '-'||array[i] == '*'||array[i] == '/') )
				{
					cout<<"错误，请重新输入"<<endl;
					goto Start;
				}     


		if( type == 1 )
		//若为前缀，调用相应函数
			root = CreatePreOrder( array );
		else
        //若为前缀，调用相应函数
			root = CreatePostOrder( array );

		cout<<endl<<endl;
        cout<<"下图为表达式的树形结构"<<endl;
		Print( root, 0 );  //打印

		cout<<endl<<endl;
		cout<<"请输入要得出的表达式类型(1为前缀，2为中缀，3为后缀)"<<endl;
        do{                                  //输入类型，错误时循环输入
			 cin>>type;
			 if( type != 1 && type != 2 && type != 3 )
				 cout<<"错误，请重新输入"<<endl;
		}while(type != 1 && type != 2 && type != 3 );

		if( type == 1 )
        //若为前缀，调用相应函数
			OutputPreOrder( root );
		else if( type == 2)
		//若为中缀，调用相应函数
			OutputInOrder( root );
		else
		//若为后缀，调用相应函数
			OutputPostOrder( root );

		cout<<endl<<endl;

		cout<<"想继续输入表达式吗(y/n)";
		cout<<endl;
		ch = getche();
		cout<<endl<<endl<<endl;
		if( !( ch == 'y' || ch == 'Y' ) )
			cout<<"感谢使用，程序退出"<<endl;
	}while( ch == 'y' || ch == 'Y' );   //输入为y时，可以循环进行操作
}


//输入表达式为前缀，调用该函数构造树
//函数参数为输入的表达式，返回参数为表达式树的根结点
//算法：1. 将输入的字符串逐一输入类数组中
//      2. 从左向右，为字母时接入出栈的操作符结点后，
//         为操作符时接入出栈的操作符接点后并在入栈
//      3. 返回根结点指针
BinaryTreeNode * CreatePreOrder( char * s )
{
	astack Prestack;
 
	
	int i = 0, j = 0;
	int len = (int)strlen( s );

	for( j = 0; j <= len - 1; j++)
		tempNode[j] = BinaryTreeNode( s[j] );  //将输入的字符串逐一输入类数组中

	BinaryTreeNode * root = & tempNode[0] ;
	BinaryTreeNode * pointer = root;
	Prestack.push( &tempNode[0] );
	i = 1;

	while( i <= len - 1 )
	{
		
		if( (tempNode[i].value() >= 'a' && tempNode[i].value() <= 'z' )|| (tempNode[i].value() >= 'A' && tempNode[i].value() <= 'Z' )
			|| tempNode[i].value() == '+' || tempNode[i].value() == '-' || tempNode[i].value() == '*' || tempNode[i].value() == '/' )
		{//输入字符符合条件时
			pointer = Prestack.top(); //出栈
			Prestack.pop();
			if( pointer->left == NULL )
			{//出栈结点的左指针为空时，接入
				pointer->left = &tempNode[i];
   				Prestack.push( pointer ); //入栈
			}
		   	else 
			{//出栈结点的右指针为空时，接入
				pointer->right = &tempNode[i];
			}
			if( tempNode[i].value() == '+'||tempNode[i].value() == '-'||tempNode[i].value() == '*'||tempNode[i].value() == '/' )
				Prestack.push( &tempNode[i] ); //当前结点为操作符时，再入栈
		}
		i++;  //向右移位
	}
	return root;  //返回根结点
}


//与上一函数基本相同
BinaryTreeNode * CreatePostOrder( char * s )
{
	astack Poststack;
 
	
	int i = 0, j = 0;
	int len = (int)strlen( s );

	for( j = 0; j <= len - 1; j++)
		tempNode[j] = BinaryTreeNode( s[j] );    //将输入的字符串逐一输入类数组中

	BinaryTreeNode * root = & tempNode[len - 1] ;
	BinaryTreeNode * pointer = root;
	Poststack.push( &tempNode[len - 1] );
	i = len - 2;

	while( i >=0 )
	{
		
		if( (tempNode[i].value() >= 'a' && tempNode[i].value() <= 'z' )|| (tempNode[i].value() >= 'A' && tempNode[i].value() <= 'Z' )
			|| tempNode[i].value() == '+' || tempNode[i].value() == '-' || tempNode[i].value() == '*' || tempNode[i].value() == '/' )
		{//输入字符符合条件时
			pointer = Poststack.top();
			Poststack.pop();
			if( pointer->rightchild() == NULL )
			{//出栈结点的右指针为空时，接入
				pointer->right = &tempNode[i];
   				Poststack.push( pointer );
			}
		   	else 
			{//出栈结点的左指针为空时，接入
				pointer->left = &tempNode[i];
			}
			if( tempNode[i].value() == '+'||tempNode[i].value() == '-'||tempNode[i].value() == '*'||tempNode[i].value() == '/' )
				Poststack.push( &tempNode[i] );  //当前结点为操作符时，再入栈
		}
		i--;  //向左移位
	}
	return root;//返回根结点
}

//按树的形状打印表达式树，root为树的根结点，level表示结点所在层次,初次调用时level=0
//主要用中序递归的方法
void Print(BinaryTreeNode * root, int level)
{
	if(root->leftchild()) 
		Print(root->leftchild(),level+1);  //左子树不为空，递归打印左子树
	for(int j=1;j<=level;j++) 
		cout<<"   "; //打印j个空格以表示出层次
	cout<<root->value()<<endl;    //打印当前结点
	
    if(root->rightchild()) 
		Print(root->rightchild(),level+1);//右子树不为空，递归打印右子树
}


//输出前缀表达式，参数为树的跟结点
//采用前序递归的方法
void OutputPreOrder( BinaryTreeNode * root )
{
	if( root != NULL )
	{
		cout<<root->value();
		OutputPreOrder( root->leftchild() );
		OutputPreOrder( root->rightchild() );
		
	}
}

//输出后缀表达式，参数为树的跟结点
//采用后序递归的方法
void OutputPostOrder( BinaryTreeNode * root )
{
	if( root != NULL )
	{	
		OutputPostOrder( root->leftchild() );
		OutputPostOrder( root->rightchild() );
		cout<<root->value();
	}
}

//输出中缀表达式，参数为树的跟结点
//采用中序递归的方法
void OutputInOrder( BinaryTreeNode * root )
{
	if( ( root->value() >= 'a' && root->value() <= 'z' ) || ( root->value() >= 'A' && root->value() <= 'Z' ) )
		cout<<root->value();    //当前结点为字母时，直接打印
	else
	{//当前结点为操作符时
		if( (root->leftchild()->value() == '+' || root->leftchild()->value() == '-' )
			&& ( root->value() == '*' || root->value() == '/' ) )
		{//左结点的优先级较小
			cout<<'(';
			OutputInOrder( root->leftchild() );
			cout<<')'; //打印括号，括号中打印左子树
		}
        else
		//优先级与顺序一致，直接打印左子树
			OutputInOrder( root->leftchild() );

		cout<<root->value();

	    if( (root->rightchild()->value() == '+' || root->rightchild()->value() == '-' )
			&& ( root->value() == '*' || root->value() == '/' ) )
		{//右结点的优先级较小
			cout<<'(';
			OutputInOrder( root->rightchild() );
			cout<<')';//打印括号，括号中打印左子树
		}
		else
        //优先级与顺序一致，直接打印右子树
			OutputInOrder( root->rightchild() );
	}
}