проверка дерева выражений

Question

У меня почти есть функция проверки работоспособности, но я только что написал последнюю часть, где он проверяет внутренние узлы, чтобы убедиться, что они операторы. Без этой части функция проверяет мелкие узлы листа. Хотя, когда я включаю внутреннюю часть, она печатает первый узел «-» и возвращает 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; 
    } 

Без этого, функция отлично работает! Любые идеи, что вызывает это?

Answer 1

Выражение оператора if разбивает вашу программу, поскольку это заставляет функцию преждевременно прекращать проверку узлов. Если установлен узел left или right, он проверяет наличие оператора и, если он находит его, он возвращает true. Если найдено совпадение, это предотвращает дальнейшую проверку, если left, right или оба указывают на большее количество узлов. Если вы замените логический оператор или логическим оператором и, код может по-прежнему сбой, так как проверка выражения для операторов полностью whack. Для того, чтобы этот блок кода для работы ему необходимо будет заменить на что-то вроде этого:

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, это является C++ Afterall.