0

我有一个关于将字符串 s 解析为二叉树的问题。 

struct TreeNode {
string val;         // The data in this node.
TreeNode *left;   // Pointer to the left subtree.
TreeNode *right;  // Pointer to the right subtree.
};

string s="((OR (AND pass (NOT reject)) (AND (NOT pass) reject)))";

我做了一些笔画并消除了“（”和“）”并将所有单独的部分保留在向量后拆分中，后拆分有（底部）或并且通过不拒绝并且不通过拒绝（返回）

vector<string> aftersplit;
vector<TreeNode> parsetree;
while (!aftersplit.empty())//do the parsing 
{

     TreeNode *temp=new TreeNode;

    temp->val=aftersplit.back();
    temp->left=NULL;
    temp->right=NULL;        
    aftersplit.pop_back();
    if(temp->val=="AND"||temp->val=="OR"||temp->val=="=>"||temp->val=="<=>"){
        TreeNode *leftnode = new TreeNode; 

        leftnode=&parsetree.back();
        parsetree.pop_back();
        temp->left=leftnode;
        TreeNode *rightnode = new TreeNode; 

        rightnode=&parsetree.back();
        parsetree.pop_back();
        temp->right=rightnode;
        parsetree.push_back(temp); //can not put the temp into parsetree 
    }
    else if(temp->val=="NOT")
    {
        TreeNode *leftnode = new TreeNode; 

        leftnode=&parsetree.back();
        parsetree.pop_back();
        temp->left=leftnode;
        parsetree.push_back(temp);        
    }
    else {            
        parsetree.push_back(temp);
    }

}

我从右到左处理字符串 s

但是，当我在运算符为“OR”时运行“TreeNode leftnode”时；左节点被分配了一个地址，该地址被第一个“与”的左孩子“pass”使用，也就是说，“与”指向他的左孩子地址0x00007fff6d8da7e0，新的临时左节点正在分配地址0x00007fff6d8da7e0 在那之后树就像

    (AND)            
       / \        
      /   \       
   pass  (NOT)         
          /          
      reject

在那个leftnode被分配“pass”的地址之后，它会喜欢

                (AND)            
                 /    \        
                /      \       
              (AND)    (NOT)         
              /    \     /     
             /      \   /          
          (AND) (NOT) reject
         /    \        
        /      \       
     (AND)    (NOT)

等等，都指向自己，我知道指针可能有问题，但我无法弄清楚。请帮我

4

1 回答 1

1 
if(temp.val=="AND"||temp.val=="OR"||temp.val=="=>"||temp.val=="<=>"){
    TreeNode leftnode;  //appear a bug here
    leftnode=parsetree.back();
    parsetree.pop_back();
    temp.left=&leftnode;
    TreeNode rightnode;
    rightnode=parsetree.back();
    parsetree.pop_back();
    temp.right=&rightnode;
    parsetree.push_back(temp);  
}

你的变量leftnode和rightnode有一个有限的寿命。由于它们是在您的范围内声明的if，因此一旦您离开那里，它们就会被销毁。意味着他们的地址变得无效！因此，每次 temp.left 和 temp.right 的内容都会指向一些垃圾数据。

这实际上就是为什么您可以看到多次找到相同地址的原因：由于前一个对象已被销毁，它被用于存储您需要的新数据。但这并不是您想要的，因为您想保留您创建的所有对象。

最简单的方法是动态创建TreeNode您需要的 s （并相应地修改其余代码）：

TreeNode *leftnode = new TreeNode;
TreeNode *rightnode = new TreeNode;

这样，即使在退出if. 但是，您以后一定不要忘记delete他们。

于 2013-04-18T02:48:17.770 回答