change.cpp

逻辑表达式转化

	for( ; i < index_2 ; i++ )
	if( *(string2+i) )			//记录各个简单合取式的角码
	{
		for( node = *(string2+i) ; node != NULL ; node = node->left )
		{
			if( node->isOperand && node->right->negate1 )
				key += k;
			else
				if( node->negate1 )
					key += k;

			k *= 2;				//每进一位，二进制码乘2
		}
		*(data+i) = key;		//保存角码
		k = 1;					//重设二进制码
		key = 0;				//重设角码
	}
		
								//将角码保存到data_2[MAX]中，因为在下面会改变data[MAX]的值
	for( i = 0 ; i < index_2 ; i++ )
		*(data_2+i) = *(data+i);

								//用选择排序法将data_2[MAX]中的按角码从小到大反标识符存放在data_1[MAX]中
	for( i = 0 ; i < index_2 ; i++ )
	{
		if( *(data+i) >= 0 )
		{
			k = i;
			for( j = i+1 ; j < index_2 ; j++ )
				if( *(data+k) > *(data+j) && *(data+j) != -1 )
					k = j;		//存保当前角码蛭小的标识符

			*(data_1+(t++)) = k;
			*(data+k) = -1;		//为表示该角码已经检查过，设为-1
			i = -1;				//再一次从data[MAX]第一个元素开始，并且循环后i自加1
		}
	}
								//从第一个角码不为空的简单合取式开始建立新树
	for( j = 0 ; j <index_2 ; j++ )		
		if( *(string2+ *(data_1+j)) )
			break;
	node = copy( *(string2+ *(data_1+j ) ) );		//建立新结点

	for( i = j+1 ; i<index_2 ; i++ )
		if( *(data_2+ *(data_1+i) ) != *(data_2+ *(data_1+i-1) ) )
		{									//角码不同表示简单合取式不同，主析取表达式中没相同的简单合取式
			newnode = new Node( '\\' , false , true );
			newnode->left  = node;
			newnode->right = copy( *(string2+ *(data_1+i ) )  );
			node = newnode;
		}

	if( tree )		//删除原来的旧树
		delTree( tree );
	return node;	//返回当前二叉树
}
													///////////////////////////////////////////////

					//调用各种函数完成表达式的转换
void LogicTree::changeTree( link rhs )
{
	int k = 0, i;

	printTree();								
	for(  i = 0 ; i<index_1 ; i++ )		//先计算蕴含
		changeNode_2( *(string1+i) );
				
	negateTree( tree );			//将括号外的否定移到括号中
	do							//计算合取运算符
	{
		goon = 0;
		changeAllNode( tree , tree );
	}while( goon );				

	newBracket( tree );			//重设所有运算符的括号变量，惟方便输出
	arrangeTree( tree );		//为排序做准备

	if( tree->character == '\\' || isCharacter( tree->character ) )
		add( tree );			//加入简单合取式中没有的操作数

	record_string2( tree );
	record_string3( tree );
	paiXu( i );
	if( k )
		printTree();
	F5();
	tree = newTree();			//将新树的顶结点给tree
	if( !tree )
		cout<<"<=> 0"<<endl;
	else
		printTree();
}




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

void LogicTree::add( link rhs )
{
    int i = 0;	

	if( rhs )
	{
		if( rhs->left->character == '/' || isCharacter( rhs->left->character ) )
		{									
			for(; *(value+i) != '\0' ; i++ )
				*(value_1+i) = *(value+i);
		
			clean( rhs->left );				//检查该子树未存在哪些操作数
			add_1( rhs , rhs->left , 0 );	//补上未出现的操作数
		}
			else							//如果该结点为析取，则继续查找
				add( rhs->left  );

		if( rhs->right->character == '/' || isCharacter( rhs->right->character ) )
		{
			for( i = 0 ; *(value+i) != '\0' ; i++ )
				*(value_1+i) = *(value+i);	

			clean( rhs->right );			//检查该子树未存在哪些操作数
			add_1( rhs , rhs->right , 0 );	//补上未出现的操作数
		}
		else								//如果该结点为析取，则继续查找									
			add( rhs->right );
	}
}

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

void LogicTree::add_1( link rhs_p , link rhs_c , int po )
{
	int k = 0;

	while( *(value_1+po) == '*' && *(value_1+po) != '\0' )		//打到当前第一个未出现的操作数
		po++;

	if( *(value_1+po) != '\0' )				//趣在未出现的操作数
		{
			link node = new Node( '\\' , false , true );
			node->left = new Node( *(value_1+po) );
			node->right = new Node( *(value_1+po) , true );
			link newnode = new Node( '/' , false , true );
			newnode->left = rhs_c;
			newnode->right = node;     

			if( rhs_p->left == rhs_c )		//该结点为父结点的左子树
			{
				rhs_p->left = newnode;
				rhs_c = rhs_p->left;
				k = 1;
			}
			else							//该结点为父结点的右子树
			{
				rhs_p->right = newnode;
			    rhs_c = rhs_p->right;
				k = 2;
			}

			printTree();
			changeAllNode( rhs_c , rhs_p );		//计算已新加的析取
		
			if( k == 1 )					//改变的为父结点的左子树
			{
				add_1( rhs_p->left  , rhs_p->left->left  , po+1 );
				add_1( rhs_p->left  , rhs_p->left->right , po+1 );
			}
			else if( k == 2 )				//改变的为父结点的右子树
			{
				add_1( rhs_p->right , rhs_p->right->left , po+1 );
				add_1( rhs_p->right , rhs_p->right->right , po+1);
			}
		}
}
													///////////////////////////////////////////////


		//将以合取运算符为顶结点的树改变成最后一层为操作数且右结点只有操作数运算符结点
void LogicTree::arrange( link rhs )
{
	int i = 0;
	link node_1 = NULL;
	link node_p = rhs;
	link node_c = rhs;

	if( node_p->isOperand )
		while( node_c->left->isOperand )
			node_c = node_c->left;

	while( node_p->isOperand )
	{
		if( node_p->right->isOperand )
		{
			node_1 = node_p->right;
			node_p->right = node_c->left;
			node_c->left = node_1;
			node_c = node_1;
			while( node_c->left->isOperand )
				node_c = node_c->left;
		}
		node_p = node_p->left;
	}

}
													///////////////////////////////////////////////



void LogicTree::arrangeTree( link rhs )
{
	if( rhs )
	{
	if( rhs->character == '/' )			//如果结点为合取，就进行转化
		arrange( rhs );
	else
	{
		arrangeTree( rhs->left );
		arrangeTree( rhs->right );
	}
	}
}
													///////////////////////////////////////////////


		//构造二叉树
link LogicTree::buildTree( char * rhs )
{
    link node_1 = NULL;
	link node_2 = NULL;
	link node_3 = NULL;
	link node_4 = NULL;
	bool negate = false;

	while( *(rhs+num) != '\0' && *(rhs+num) != '\n' )
	{
		if( *(rhs+num) == '!' )
		{
			if( negate )
				negate = false;
			else
				negate = true;
		}
		else
		{
			if( isCharacter( *(rhs+num) ) )
			{
				node_1 = new Node( *(rhs+num), negate );
				negate = false;

				if( !node_2 )
					node_2 = node_1;
				else if( !node_2->right )
					node_2->right = node_1;
				else
					node_3->right = node_1;
			}
			
			else if( isOperator( *(rhs+num) ) )
			{
				node_3 = new Node( *(rhs+num), negate, true );
				negate = false;
				if( *(rhs+num) == '>' )
				    string1[index_1++] = node_3;
				
				if( node_2->bracket || !node_2->left )
				{
					node_3->left = node_2;
					node_2 = node_3;
				}
				else 
					if( priority( node_2->character ) < priority( node_3->character ) )
					{
						if( priority( node_2->right->character ) < priority( node_3->character )\
							&& !node_2->right->bracket )
						{
							node_3->left = node_2->right->right;
							node_2->right->right = node_3;
						}
						else
						{
						node_3->left = node_2->right;
						node_2->right = node_3;
						}
					}
					else
					{
						node_3->left = node_2;
						node_2 = node_3;
					}
			}
			else if( isLeftBracket( *(rhs+num) ) )
			{
				num++;
				node_4 = buildTree( rhs );
				if( negate )
					node_4->negate1 = negate;

				if( !node_2 )
					node_2 = node_4;
				else if( !node_2->right )
					node_2->right = node_4;
				else
				    node_3->right = node_4;
			}
			else
			{
				node_2->bracket++;
				return node_2;
			}
		}
		num++;
	}
	return node_2;
}
													///////////////////////////////////////////////




void LogicTree::changeAllNode( link rhs_c, link rhs_p )
{
	if( rhs_c->isOperand && ( rhs_c->left->isOperand || rhs_c->right->isOperand ) )
	{
		if( rhs_c->character == '/' )
			if( rhs_c->left->character == '\\' || rhs_c->right->character == '\\' )
			{
				goon++;
				if( rhs_c == tree )			//如果是顶结点，将新的树设为顶结点
					tree = changeNode_1( rhs_c );
				else
					if( rhs_p->left == rhs_c )
						rhs_p->left = changeNode_1( rhs_c );		//转换左子树
				else
					rhs_p->right = changeNode_1( rhs_c );			//转换右子树
				printTree();
			}
		changeAllNode( rhs_c->left  , rhs_c );
		changeAllNode( rhs_c->right , rhs_c );			
	}
}
													///////////////////////////////////////////////



void LogicTree::changeNode_2( link rhs )
{
	rhs->character = '\\';		//先将头结点设为蕴含运算符
								//将左结点否定一次
	if( rhs->left->negate1 )
		rhs->left->negate1 = false;
	else
		rhs->left->negate1 = true;
	printTree();
}

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


void LogicTree::negateTree( link rhs )
{
	if( isOperator( rhs->character ) )
	{
		if( rhs->negate1 )			//如果头结点否定
		{
			if( rhs->character == '\\' )		//若结点为析取，设成合取
				rhs->character = '/';
			else								//若结点为合取，设成析取
				rhs->character = '\\';
			rhs->negate1 = false;				//重新疫轩否定
			if( rhs->left->negate1 )			//重轩左右结点的否定级
				rhs->left->negate1 = false;
			else
				rhs->left->negate1 = true;
			if( rhs->right->negate1 )
				rhs->right->negate1 = false;
			else
				rhs->right->negate1 = true;
			printTree();
		}
		
		negateTree( rhs->left );
		negateTree( rhs->right );
	}
}
													///////////////////////////////////////////////



void LogicTree::newBracket( link rhs )
{
	if( rhs )
	{
		if( rhs->isOperand )
			rhs->bracket = 0;			//为方便打印，将所有的 bracket 设为0
		newBracket( rhs->left );
		newBracket( rhs->right );
	}
}



void LogicTree::record_string2( link rhs )
{
	if( rhs )
	{
		if( rhs->character == '/'  || !rhs->isOperand )
			string2[index_2++] = rhs;			//记录各个简单合取式的顶结点
		else
		{
			record_string2( rhs->left );
			record_string2( rhs->right );
		}
	}
}
													///////////////////////////////////////////////

					//记录有一个子结点为合取的运算符，方便删除
void LogicTree::record_string3( link rhs )
{
	if( rhs->character == '\\' )
	{
		int i = 0;
		if( rhs->left->character == '/' || !rhs->left->isOperand )
			for( i = 0 ; i < index_2 ; i++ )				//标识符与子结点的相符合
			{
				if( rhs->left == *(string2+i) )
				{
					*(string3+i) = rhs;
					break;
				}
			}
		else
			record_string3( rhs->left );

		if( rhs->right->character == '/' || !rhs->right->isOperand )
			for( i = 0 ; i < index_2 ; i++ )
			{
				if( rhs->right == *(string2+i) )
				{
					*(string3+i) = rhs;
					break;
				}
			}
		else
			record_string3( rhs->right );
	}
}