試圖驗證表達式樹中的葉節點

-2

我做了一個布爾函數來驗證我的表達式樹中的葉節點。如果節點是任何運算符，則返回false。否則，它應該返回true。它會遞歸地調用它自己......這是我認爲的問題。你可以有一個布爾函數遞歸？這裏是我的功能試圖驗證表達式樹中的葉節點

bool validate(tnode* node) 
{ 
    if(node == NULL) 
    { 
    cout<<"Node is null";  
    return false; 
    } 
    if(node->left == NULL && node->right==NULL) 
    { 
    cout<<node->key<<endl<<endl; 
    if(node->key == '+' || '-' || '*' || '/') 
     return false; 
    else 
     return true; 
    }  
    else 
     validate(node->left); 
     validate(node->right);  
}

實際打印出我所有的葉節點的值完美，它們分別是：A B C d 2 C 3.但是，當我在我的主要功能運行它，它總是回來假。任何想法爲什麼？

來源

2013-04-25 user2313755

if(node->key == '+' || '-' || '*' || '/')

應該

if(node->key == '+' || node->key == '-' || node->key == '*' || node->key == '/')

同時：

else { 
    validate(node->left); 
    validate(node->right); 
} //should not miss the parenthesis

你或許應該做這樣的事情：

else{ 
     bool left = validate(node->left); 
     bool right = validate(node->right); 
     return (left && right); 
}

來源

2013-04-25 19:14:56 taocp

我不能只是讓它在這兩個驗證函數運行後返回true嗎？如果不是這樣，那麼在它完成之前就會崩潰，對吧？ – user2313755 2013-04-25 19:31:36

@ user2313755不，錯。 return語句只留下函數的當前實例，而不是整個遞歸。如果函數不是'void'，你總是必須返回一些東西。 – Detheroc 2013-04-25 19:43:35

您不在任何地方存儲結果。

validate(node->left); 
validate(node->right);

應該更像

_Bool res = validate(node->left);

然後做的結果的東西。

來源

2013-04-25 19:14:56

它總是返回false的原因是，這EXP ression：

(node->key == '+' || '-' || '*' || '/')

實際上意味着

(node->key == '+') || ('-' != 0) ...

這始終是真實的，因爲-字符沒有零值。

你也不需要作出規定成的if-else子句，我建議這樣的：

return !(node->key == '+' || node->key == '-' 
     || node->key == '*' || node->key == '/');

至於最後一部分，我認爲你需要做的是：

else 
    return validate(node->left) && validate(node->right);

來源

2013-04-25 19:23:13 Detheroc

試圖驗證表達式樹中的葉節點

回答

相關問題