// 我真誠地保證：
    
// 我自己獨(dú)立地完成了整個程序從分析、設(shè)計(jì)到編碼的所有工作。
// 如果在上述過程中，我遇到了什么困難而求教于人，那么，我將在程序?qū)嵙?xí)報(bào)告中
// 詳細(xì)地列舉我所遇到的問題，以及別人給我的提示。

// 在此，我感謝 XXX, …, XXX對我的啟發(fā)和幫助。下面的報(bào)告中，我還會具體地提到
// 他們在各個方法對我的幫助。
 
// 我的程序里中凡是引用到其他程序或文檔之處，
// 例如教材、課堂筆記、網(wǎng)上的源代碼以及其他參考書上的代碼段,
// 我都已經(jīng)在程序的注釋里很清楚地注明了引用的出處。

// 我從未沒抄襲過別人的程序，也沒有盜用別人的程序，
// 不管是修改式的抄襲還是原封不動的抄襲。

    // 我編寫這個程序，從來沒有想過要去破壞或妨礙其他計(jì)算機(jī)系統(tǒng)的正常運(yùn)轉(zhuǎn)。
    
//*****************************************
//***         二叉樹   4. 2             ***
//***                                   ***
//***            00348226  王瀟(第二組) ***
//***          創(chuàng)建日期：  04-10-2      ***
//***          最后修改：  04-10-4      ***
//*****************************************

//程序功能：實(shí)現(xiàn)輸入的前后綴表達(dá)式均可構(gòu)造樹并打印，并再轉(zhuǎn)化為任意形式的表達(dá)式
//          可循環(huán)實(shí)現(xiàn)操作
//主要算法：即以三種周游方法為主，附以各種實(shí)現(xiàn)題目要求的操作


#include <iostream.h>
#include <string.h>
#include <stack>
#include <algorithm>
#include <conio.h>
using namespace std;     //應(yīng)用stl函數(shù)庫中的棧模板
    



//類名：BinaryTreeNode
//功用：二叉樹的結(jié)點(diǎn)類
//類參數(shù)： 一個數(shù)據(jù)域字符變量，左右指針
//類函數(shù)： 兩個不同參數(shù)的構(gòu)造函數(shù)與三個函數(shù)外部接口
class BinaryTreeNode
{
public:
	char element;        //數(shù)據(jù)域?yàn)橐粋€字符變量，存儲表達(dá)式的一個字符   
	BinaryTreeNode * left;
	BinaryTreeNode * right;
	BinaryTreeNode()     //不帶參數(shù)的構(gòu)造函數(shù)
	{
		element = '\0';
		left = NULL;
		right = NULL;
	}

	BinaryTreeNode( char ch ) //將字符變量初始化為輸入的參數(shù)
	{
		element = ch;
		left = NULL;
		right = NULL;
	}
	char value()   //返回?cái)?shù)據(jù)域
	{
		return element;  
	}
	BinaryTreeNode * leftchild() const //返回左指針
	{
		return left;
	}
	BinaryTreeNode * rightchild() const //返回右指針
	{
		return right;
	}
};

const int MaxNode = 100; //定義常量為100
BinaryTreeNode tempNode[MaxNode];  //定義類數(shù)組為全局變量，用于存儲輸入的表達(dá)式，一個字符占用一個類

typedef stack<BinaryTreeNode *>  astack; //定義棧，棧元素為結(jié)點(diǎn)指針

//以下兩函數(shù)功能為根據(jù)輸入的表達(dá)式為前綴或后綴分別構(gòu)造表達(dá)式樹
//函數(shù)參數(shù)為輸入的表達(dá)式，返回參數(shù)為表達(dá)式樹的根結(jié)點(diǎn)
BinaryTreeNode * CreatePreOrder( char * s );
BinaryTreeNode * CreatePostOrder( char * s );

//按樹的形狀打印表達(dá)式樹，root為樹的根結(jié)點(diǎn)，level表示結(jié)點(diǎn)所在層次,初次調(diào)用時(shí)level=0
void Print(BinaryTreeNode * root, int level);

//以下三個函數(shù)功用為根據(jù)已有的表達(dá)式樹，分別輸出前綴，中綴，后綴表達(dá)式
//參數(shù)為樹的跟結(jié)點(diǎn)
void OutputPreOrder( BinaryTreeNode * root );
void OutputInOrder( BinaryTreeNode * root );
void OutputPostOrder( BinaryTreeNode * root );


void main()
{//主函數(shù)入口點(diǎn)
	BinaryTreeNode * root = NULL;
	char array[MaxNode];  //儲存輸入的表達(dá)式
	char ch = 'y';
	int type = 0;         //儲存輸入表達(dá)式與輸出表達(dá)式的類型
	int i = 0;   //定義并初始化各參量

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

		cout<<"請輸入待輸入的表達(dá)式類型(1為前綴，2為后綴)"<<endl;
		do{
			 cin>>type;                 
			 if( type != 1 && type != 2 )
				 cout<<"錯誤，請重新輸入"<<endl;
		}while(type != 1 && type != 2);           //輸入類型，錯誤時(shí)循環(huán)輸入

		cout<<endl<<"請輸入相應(yīng)的表達(dá)式(僅由字母與+-*/組成)"<<endl;
        Start:          
			cin>>array;                           //輸入表達(dá)式，錯誤時(shí)循環(huán)輸入
			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 )
		//若為前綴，調(diào)用相應(yīng)函數(shù)
			root = CreatePreOrder( array );
		else
        //若為前綴，調(diào)用相應(yīng)函數(shù)
			root = CreatePostOrder( array );

		cout<<endl<<endl;
        cout<<"下圖為表達(dá)式的樹形結(jié)構(gòu)"<<endl;
		Print( root, 0 );  //打印

		cout<<endl<<endl;
		cout<<"請輸入要得出的表達(dá)式類型(1為前綴，2為中綴，3為后綴)"<<endl;
        do{                                  //輸入類型，錯誤時(shí)循環(huán)輸入
			 cin>>type;
			 if( type != 1 && type != 2 && type != 3 )
				 cout<<"錯誤，請重新輸入"<<endl;
		}while(type != 1 && type != 2 && type != 3 );

		if( type == 1 )
        //若為前綴，調(diào)用相應(yīng)函數(shù)
			OutputPreOrder( root );
		else if( type == 2)
		//若為中綴，調(diào)用相應(yīng)函數(shù)
			OutputInOrder( root );
		else
		//若為后綴，調(diào)用相應(yīng)函數(shù)
			OutputPostOrder( root );

		cout<<endl<<endl;

		cout<<"想繼續(xù)輸入表達(dá)式嗎(y/n)";
		cout<<endl;
		ch = getche();
		cout<<endl<<endl<<endl;
		if( !( ch == 'y' || ch == 'Y' ) )
			cout<<"感謝使用，程序退出"<<endl;
	}while( ch == 'y' || ch == 'Y' );   //輸入為y時(shí)，可以循環(huán)進(jìn)行操作
}


//輸入表達(dá)式為前綴，調(diào)用該函數(shù)構(gòu)造樹
//函數(shù)參數(shù)為輸入的表達(dá)式，返回參數(shù)為表達(dá)式樹的根結(jié)點(diǎn)
//算法：1. 將輸入的字符串逐一輸入類數(shù)組中
//      2. 從左向右，為字母時(shí)接入出棧的操作符結(jié)點(diǎn)后，
//         為操作符時(shí)接入出棧的操作符接點(diǎn)后并在入棧
//      3. 返回根結(jié)點(diǎn)指針
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] );  //將輸入的字符串逐一輸入類數(shù)組中

	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() == '/' )
		{//輸入字符符合條件時(shí)
			pointer = Prestack.top(); //出棧
			Prestack.pop();
			if( pointer->left == NULL )
			{//出棧結(jié)點(diǎn)的左指針為空時(shí)，接入
				pointer->left = &tempNode[i];
   				Prestack.push( pointer ); //入棧
			}
		   	else 
			{//出棧結(jié)點(diǎn)的右指針為空時(shí)，接入
				pointer->right = &tempNode[i];
			}
			if( tempNode[i].value() == '+'||tempNode[i].value() == '-'||tempNode[i].value() == '*'||tempNode[i].value() == '/' )
				Prestack.push( &tempNode[i] ); //當(dāng)前結(jié)點(diǎn)為操作符時(shí)，再入棧
		}
		i++;  //向右移位
	}
	return root;  //返回根結(jié)點(diǎn)
}


//與上一函數(shù)基本相同
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] );    //將輸入的字符串逐一輸入類數(shù)組中

	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() == '/' )
		{//輸入字符符合條件時(shí)
			pointer = Poststack.top();
			Poststack.pop();
			if( pointer->rightchild() == NULL )
			{//出棧結(jié)點(diǎn)的右指針為空時(shí)，接入
				pointer->right = &tempNode[i];
   				Poststack.push( pointer );
			}
		   	else 
			{//出棧結(jié)點(diǎn)的左指針為空時(shí)，接入
				pointer->left = &tempNode[i];
			}
			if( tempNode[i].value() == '+'||tempNode[i].value() == '-'||tempNode[i].value() == '*'||tempNode[i].value() == '/' )
				Poststack.push( &tempNode[i] );  //當(dāng)前結(jié)點(diǎn)為操作符時(shí)，再入棧
		}
		i--;  //向左移位
	}
	return root;//返回根結(jié)點(diǎn)
}

//按樹的形狀打印表達(dá)式樹，root為樹的根結(jié)點(diǎn)，level表示結(jié)點(diǎn)所在層次,初次調(diào)用時(shí)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;    //打印當(dāng)前結(jié)點(diǎn)
	
    if(root->rightchild()) 
		Print(root->rightchild(),level+1);//右子樹不為空，遞歸打印右子樹
}


//輸出前綴表達(dá)式，參數(shù)為樹的跟結(jié)點(diǎn)
//采用前序遞歸的方法
void OutputPreOrder( BinaryTreeNode * root )
{
	if( root != NULL )
	{
		cout<<root->value();
		OutputPreOrder( root->leftchild() );
		OutputPreOrder( root->rightchild() );
		
	}
}

//輸出后綴表達(dá)式，參數(shù)為樹的跟結(jié)點(diǎn)
//采用后序遞歸的方法
void OutputPostOrder( BinaryTreeNode * root )
{
	if( root != NULL )
	{	
		OutputPostOrder( root->leftchild() );
		OutputPostOrder( root->rightchild() );
		cout<<root->value();
	}
}

//輸出中綴表達(dá)式，參數(shù)為樹的跟結(jié)點(diǎn)
//采用中序遞歸的方法
void OutputInOrder( BinaryTreeNode * root )
{
	if( ( root->value() >= 'a' && root->value() <= 'z' ) || ( root->value() >= 'A' && root->value() <= 'Z' ) )
		cout<<root->value();    //當(dāng)前結(jié)點(diǎn)為字母時(shí)，直接打印
	else
	{//當(dāng)前結(jié)點(diǎn)為操作符時(shí)
		if( (root->leftchild()->value() == '+' || root->leftchild()->value() == '-' )
			&& ( root->value() == '*' || root->value() == '/' ) )
		{//左結(jié)點(diǎn)的優(yōu)先級較小
			cout<<'(';
			OutputInOrder( root->leftchild() );
			cout<<')'; //打印括號，括號中打印左子樹
		}
        else
		//優(yōu)先級與順序一致，直接打印左子樹
			OutputInOrder( root->leftchild() );

		cout<<root->value();

	    if( (root->rightchild()->value() == '+' || root->rightchild()->value() == '-' )
			&& ( root->value() == '*' || root->value() == '/' ) )
		{//右結(jié)點(diǎn)的優(yōu)先級較小
			cout<<'(';
			OutputInOrder( root->rightchild() );
			cout<<')';//打印括號，括號中打印左子樹
		}
		else
        //優(yōu)先級與順序一致，直接打印右子樹
			OutputInOrder( root->rightchild() );
	}
}