change.cpp

逻辑表达式转化

#include "logic.h"



void Node::delNode( link rhs )
{
	if( rhs->left )
		delNode( rhs->left );
	if( rhs->right )
		delNode( rhs->right );
	delete rhs;
	rhs = NULL;
}

													///////////////////////////////////////////////

		//构造函数初始化成员变量
LogicTree::LogicTree():
		  tree( NULL ),
		  num( 0 ),
		  index_1( 0 ),
		  index_2( 0 ),
		  num1( 0 ),
		  goon( 0 )
{
    int i ;
	for(  i = 0 ; i<54 ; i++ )
		*(value+i) = *(value_1+i) = '\0';
	for(  i = 0 ; i<MAX ; i++ )
		*(string1+i) = *(string2+i) = *(string3+i) = NULL;
}

													///////////////////////////////////////////////

		//重载运算符
Node & Node::operator =( const Node & rhs )
{
    if( this == &rhs )				//如果赋给自已，则返回自身
		return *this;
    data      = rhs.data;
	bracket   = rhs.bracket;
	negate1   = rhs.negate1;
	isOperand = rhs.isOperand;
	character = rhs.character;
	return *this;
}

													///////////////////////////////////////////////
		


link LogicTree::copy( link _tree )
{
	if( _tree )						//如果参数不为空，则复制该结点
	{
		link theTree = new Node;
	    *theTree = *_tree;
		theTree->left = copy( _tree->left );
		theTree->right = copy( _tree->right );
		return theTree;	
	}
	else							//如果是空，则结束递归函数
		return NULL;
}

													///////////////////////////////////////////////


int LogicTree::isRight( char * rhs )
{
	int i = 0;
	int j = 0;
	int k = 0;

	if( *rhs == '\0' || *rhs == '\n' )
		return 0;
	for(; *(rhs+i) != '\0' && *(rhs+i) != '\n'; i++)
	{
		if( !isOperator( *(rhs+i) ) && !isCharacter( *(rhs+i) ) && !isLeftBracket( *(rhs+i) )\
			&& !isRightBracket( *(rhs+i) ) && *(rhs+i) != '!' )			//如果字符串中不合法的字符，返回0
			return 0;
		if( i )
		{
			if( isLeftBracket( *(rhs+i) ) )					//如果是左括号
			{
				j++;
				if( isRightBracket( *(rhs+i-1) ) || isCharacter( *(rhs+i-1) ) ) 
					return 0;								//前一个为操作数或右括号，返回0
			}
			else if( isRightBracket( *(rhs+i) ) )			//如果是右括号
			{
				j--;
				if( isLeftBracket( *(rhs+i-1) ) || isOperator( *(rhs+i-1) ) || *(rhs+i-1) == '!' )
					return 0;								//前一个为左括号、操作数或 ! ,返回0
			}
			else if( isCharacter( *(rhs+i) ) )				//如果是操作数
			{
				if( isCharacter( *(rhs+i-1) ) || isRightBracket( *(rhs+i-1) ) ) 
					return 0;								//如果前一个是操作或右括号，返回0
				for( k = 0 ; *(value+k) != '\0' && *(value+k) != *(rhs+i) ; k++ );
				if( *(value+k) == '\0' )					//如果该操作数不在数组是
				{
					num1 = k+1;
					*(value+k) = *(rhs+i);					//记录该操作数
				}
			}
			else if( *(rhs+i) == '!' )						//如果是 ! 
			{
				if( isRightBracket( *(rhs+i-1) ) || *(rhs+i+1) == '\0' )
					return 0;								//如果前一个是右括号或后一个为结束符，返回0
			}
			else					//为运算符
			{
				if( isLeftBracket( *(rhs+i-1) ) || isOperator( *(rhs+i-1) ) || \
					*(rhs+i-1) == '!' || *(rhs+i+1) == '\0' || *(rhs+i+1) == '\0' )
					return 0;
			}
		}
		else						//i = 0
		{
			if( isLeftBracket( *rhs ) )
				j++;
			else if( isRightBracket( *rhs ) || isOperator( *rhs ) )
				return 0;
			else if( isCharacter( *(rhs+i) ) )		//记录弟一个操作数
				*(value+(num1++)) = *rhs;
			else if( *(rhs+1) == '\0' )
				return 0;
		}
	}
    if( j )			//如果括号不对称
		return 0;
	return 1;
}

													///////////////////////////////////////////////


void LogicTree::delTree( link _tree )
{
	if( _tree )				//如果结点不为空则删除左右结点
	{
		delTree( _tree->left );
		delTree( _tree->right );	
	
	delete _tree;			//再删除头结点
	_tree = NULL;
	}
}

													///////////////////////////////////////////////

				//如果是操作数，则返回1，否则返回0
int LogicTree::isCharacter( char rhs )const
{
	if( ( rhs >= 97 && rhs <= 122 ) || ( rhs >= 65 && rhs <= 90 ) )
		return 1;
	return 0;
}

													///////////////////////////////////////////////


int LogicTree::isOperator( char rhs )const
{
	switch( rhs )
	{
	case '\\':
    case '/':
	case '>':return 1;			//如果是运算符，则返加1
	default:return 0;			//如果不是运算符，返回0
	}
}

													///////////////////////////////////////////////


void LogicTree::clean( link rhs )
{
	if( rhs )
	{
		if( isCharacter( rhs->character ) )
			for( int i = 0 ; *(value+i) != '\0' ; i++ )
				if( rhs->character == *(value+i) )
				{
					*(value_1+i) = '*';		//如果已存在该字符，则把该位设为 * 
					return;					//跳出本次函数
				}
	
		clean( rhs->left );					//刷新左结点
		clean( rhs->right );				//刷新右结点
	}
}

													///////////////////////////////////////////////

			//判断各个运算符的优先级
int LogicTree::priority( char rhs )const
{
	switch( rhs )
	{
	case '>':return 1;
	case '\\':return 2;
	case '/':return 3;	
	default:return 4;
	}
}

													///////////////////////////////////////////////

			
void LogicTree::print( link rhs )
{
	int yes_l = 0;			//判断是否打印左括号
	int yes_r = 0;			//判断是否打印右括号

	if( rhs )				//rhs不为空
	{
		if( isOperator( rhs->character ) )		//如果该结点为运算符，打印左子树
		{
			if( isOperator( rhs->left->character ) )
				if( rhs->character != rhs->left->character || rhs->left->bracket || rhs->left->negate1 )
					yes_l = 1;			//运算符外层有括号
		
			if( rhs->left->negate1 )
				cout<<"!";
			if( yes_l )					//有括号就打印括号
				cout<<"(";

			print( rhs->left );			//打印以该结点为头结点的子树
			
			if ( yes_l )				//如果打印了左括号就再打印右括号
				cout<<")";
		}

		if( rhs->character == '\\' )
			cout<<"\\/";
		else if( rhs->character == '/' )
			cout<<"/\\";
		else if( rhs->character == '>' )
			cout<<"->";
		else
			cout<<rhs->character;

		if( isOperator( rhs->character ) )		//打印右子树
		{
			if( isOperator( rhs->right->character ) )
				if( rhs->character != rhs->right->character || rhs->right->bracket || rhs->right->negate1 )
					yes_r = 1;
			
			if( rhs->right->negate1 )
				cout<<"!";
			if( yes_r )
				cout<<"(";	
			print( rhs->right );
			if( yes_r )
				cout<<")";
		}
	}
}

													///////////////////////////////////////////////


void LogicTree::printTree()
{
	int i = 0;
	cout<<"<=> ";
	if( tree->negate1 )			//如果顶结点有否定
	{
		cout<<"!";
		if( isOperator( tree->character ) )		//如果顶结点为运算符，在外层打印括号，否定直接打印
			i = 1;
		if( i )
			cout<<"(";
		print( tree );
		if( i )
			cout<<")";
	}
	else
		print( tree );			//如果顶结点没有否定，则直接打印
		cout<<endl;
}

													///////////////////////////////////////////////

			//头结点为合取，子结点中至少有一个为析取，进行计算
link LogicTree::changeNode_1( link rhs )
{
	link newnode = new Node('\\', false ,true );		//建立一个析取结点
	link newnode_1 = copy( rhs );					//产生一个子树的复本
	newnode->left = rhs;							//将原结点设为新结点的左结点
	newnode->right = newnode_1;						//将复本结点设为新结点的右结点
    link temp_1;									//记录临时子树
	link temp_2;

	if( rhs->left->character == '\\' )
	{
		temp_1 = rhs->left;
		temp_2 = newnode_1->left;
		rhs->left = copy( temp_1->left );
		newnode_1->left = copy( temp_2->right );
	}                                                              
	else
	{
		temp_1 = rhs->right;
		temp_2 = newnode_1->right;
		rhs->right = copy( temp_1->left );
		newnode_1->right = copy( temp_2->right );
	}
	delTree( temp_1 );
	delTree( temp_2 );

	return newnode;
}


void LogicTree::F5 ()
{
	int i = 0;
	int k = 0;				//设置是否跳出整个循环
	link node_1 = NULL;		//记录头结点
	link node_2 = NULL;		//记录头结点或它的前一结点
	link node_3 = NULL;		//记录头结点的后一结点

	for( ; i<index_2 ; i++ )
	{
		k = 0;
		node_2 = NULL;
		node_1 = *(string2+i);			//初始化node_1为简音合取式的头结点
		for( ; node_1 && node_1->isOperand ; node_2 = node_1,node_1 = node_1->left )
		{
			node_3 = node_1->left ;			//初始化与头结点相比较的结点
			while( node_1->left->isOperand )		
			{
				if( node_1->right->character > node_3->right->character )		//因为在前面已经为它排序
					break;
															//两个运算符相同
				if( node_1->right->negate1 == node_3->right->negate1 )			
				{														//若否定相同，则删去与头结点相比较的结点
					node_1->left = node_3->left;
					delete node_3->right;
					delete node_3;
				}
				else					//若否定不同，该简单合取范式恒为假，删去该简单合取范式
				{
					if( *(string2+i) == tree )
						tree = NULL;
					else
					{
						if( string3[i]->left == *(string2+i) )
							string3[i]->left = NULL;
						else
							string3[i]->right = NULL;
					}
					delTree( *(string2+i) );
					*(string2+i) = NULL;
					k = 1;
					break;			//跳出循环
				}		
				node_3 = node_1->left;
			}
			if( k )
				break;						//头结点的左结点为操作数
			if( node_1->left->character == node_1->right->character )	
				if( node_1->left->negate1 == node_1->right->negate1 )		//否定相同，删去头结点的右结点
				{				
					node_3 = node_1;
					if( node_2 )
					{														//当该简单合取式头结点的左结点为操作数
						node_2->left = node_1->left;
						node_1 = node_2->left;
					}
					else								//当该简单合取式头结点的左结点不为操作数
					{
						if( string3[i]->left == *(string2+i) )
							string3[i]->left = node_1->left;
						else
							string3[i]->right = node_1->left;

						*(string2+i) = node_1->left;
						node_1 = *(string2+i);
					}
					delete node_3->right;
					delete node_3;
				}
				else									//否定相同，删去该简单合取式
				{
					if( tree == *(string2+i) )			//若整个表达式只有一个简单合取式，要将tree设为NULL
						tree = NULL;
					else
					{
						if( string3[i]->left == *(string2+i) )
							string3[i]->left = NULL;
						else
							string3[i]->right = NULL;
					}
					delTree( *(string2+i) );
					*(string2+i) = NULL;
					break;			//跳出循环
				}
		}
	}
}


													///////////////////////////////////////////////

		//为方便输出，用选择排序阖对每个简单合取式排序。
void LogicTree::paiXu( int &k)
{
	int i = 0;
	link node_1 = NULL;		//记录对比结点的父结点
	link node_2 = NULL;		//记录当前最小结点的父结点
	link node_3 = NULL;		//记录要进行比较的结点的父结点
   
	for(; *(string2+i) != '\0' ; i++ )
	{
		for(node_1 = *(string2+i); node_1->isOperand ; node_1 = node_1->left )
		{
			node_2 = node_1;
			for( node_3 = node_1->left ; node_3->isOperand ; node_3 = node_3->left )
			{
				if( node_2->right->character < node_3->right->character && ++k )
					node_2 = node_3;				//当前最小结点大于进行比较的结点，重设当前最小结点
				if( !node_3->left->isOperand )		//若进行比较的结点为操作数，则与它进行比较
					if( node_2->right->character < node_3->left->character && ++k )
						node_2 = node_3;
			}		
			
			if( node_1 != node_2 )		//对比不是最小结点
			{
										//node_2的右结点为最小结点
				if( node_2->left->isOperand || ( !node_2->left->isOperand &&\
					node_2->left->character < node_2->right->character ) )
				{
					node_3 = node_1->right;
					node_1->right = node_2->right;
					node_2->right = node_3;
				} 
				else					//node_2的左结点为最小结点
				{
					node_3 = node_1->right;
					node_1->right = node_2->left;
					node_2->left = node_3;
				}
			}
			else if( node_2->left->character > node_2->right->character )
			{											//对比结点的左结点为操作数，且右结点大于左结点
				node_3 = node_2->left;
				node_2->left = node_2->right;
				node_2->right = node_3;
			}
		}
	}
}
													///////////////////////////////////////////////

		//建立新的二叉树来正职放排序好的简单合取式
link LogicTree::newTree()
{
	int data[MAX]   = {0};		//记录标志符相对应简单合取式的角码
	int data_1[MAX] = {0};
	int data_2[MAX] = {0};
	int key = 0;		//暂时保存角码
	int i = 0;
	int j = 0;
	int k = 1;			//记录当前的二进制码
	int t = 0;
	link node    = NULL;
	link newnode = NULL;