我的验证函数几乎已经可以工作了,但我刚刚编写了最后一部分,它检查内部节点以确保它们是运算符(operator)。如果没有这部分,该函数可以很好地检查叶节点。不过,当我包含内部部分时,它会打印出第一个节点“-”并返回 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
或两者都指向更多节点,则会阻止进一步验证。如果将逻辑 or 运算符替换为逻辑 and 运算符,则代码仍可能失败,因为运算符的表达式检查完全是粗暴。为了使该代码块正常工作,需要将其更改为如下所示:
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;
}
您的解决方案也过于复杂并且代码重复。由于当前节点有效,您只需检查它为运算符(operator)存储的 key 。在这种情况下,如果左节点和右节点不为空,您可以简单地调用 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++。
关于c++ - 验证表达式树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16226619/