验证表达式树
问题描述:
我几乎有了我的验证功能,但我只写了最后一部分,它检查内部节点以确保它们是操作者。如果没有这个部分,函数会很好地检查叶节点。但是,当我包含内部部分时,它会打印出第一个节点“ - ”并返回false。验证表达式树
bool validate(tnode* node)
{
cout<<"validating leaf nodes...."<<endl;
if(node == NULL)
{
cout<<"Node is null";
return false;
}
if(node->left != NULL || node->right != NULL)
{
cout<<node->key<<endl<<endl;
if(node->key != '+' || node->key != '-' || node->key != '/' || node->key != '*')
return false;
}
if(node->left == NULL && node->right==NULL)
{
cout<<"Found leave node "<<node->key<<endl<<endl;
if(node->key == '+' || node->key == '-' || node->key == '*' || node->key == '/')
return false;
}
else
return validate(node->left) && validate(node->right);
}
问题代码此功能..
if(node->left != NULL || node->right != NULL)
{
cout<<node->key<<endl<<endl;
if(node->key != '+' || node->key != '-' || node->key != '/' || node->key != '*')
return false;
}
没有它,功能完美的作品!任何想法是什么造成的?
答
语句if
的表达式会破坏您的程序,因为它会导致函数过早停止验证节点。如果设置了left
或right
节点,它将检查运营商,如果它找到一个,则返回true
。如果发现匹配,则会阻止进一步的验证发生,如果left
,right
或两者均指向更多节点。如果用逻辑或运算符替换逻辑运算符和,则代码仍可能失败,因为运算符的表达式检查完全是重击。为了让代码块的工作,将需要改变的东西是这样的:
if(node->left == NULL && node->right == NULL)
{
cout<<node->key<<endl<<endl;
if(node->key == '+' || node->key == '-'
|| node->key == '/' || node->key == '*')
return true;
// nothing else to check since both left and right are null
return false;
}
您也过于复杂解决方案和重复的代码。由于当前节点有效,因此只需检查它为运营商存储的密钥。在这种情况下,如果左和右节点不为空,只需调用validate
,并且只检查当前节点密钥。下面的代码未经测试,但看起来正确。
bool validate(tnode* node)
{
cout << "validating leaf nodes...." << endl;
// Invalid node.
if(node == NULL)
{
cout << "Node is null";
return false;
}
// We have a left node, go validate it.
if(node->left != NULL)
{
return validate(node->left);
}
// We have a right node, go validate it.
if(node->right != NULL)
{
return validate(node->right);
}
// Now let's check the key.
cout << "Found leaf node " << node->key << endl << endl;
if(node->key == '+' || node->key == '-'
|| node->key == '/' || node->key == '*')
{
// BOOYAH!
cout << "Operator: " << node->key << endl << endl;
return true;
}
// This isn't the key type we're looking for.
return false;
}
我还建议使validate
的tnode
一个const合格成员函数,这是 C++毕竟。
如果'node'等于NULL会发生什么? – 2013-04-26 01:51:22
您是否想要将您的ORs更改为AND,例如||至 && ? – 2013-04-26 01:52:52