C++ STL stack 的push方法会更改数据?

1、描述问题

昨晚写了个程序,功能是输入表达式,输出相应的二叉树的先序遍历结果。如

输入:a+b*(c-d)-e/f

输出:-+a*b-cd/ef

代码如下:

//main.cpp
#include "iostream"
#include "sstream"
#include "string"
#include "vector"
#include <algorithm>
#include "stack"
#include "BiNode.h"
using namespace std;
int prior[7][7] = 
{{0,0,0,0,1,0},
 {0,0,0,0,1,0},
 {1,1,0,0,1,0},
 {1,1,0,0,1,0},
 {1,1,1,1,1,0},
 {0,0,0,0,0,0}};

bool judgePriority(char a, char b);
void preOrder(BiNode<char>* T);
//不能在BiNode.h里面包含BiNode.cpp 
int main() {
    stack<char> op;
    stack<BiNode<char> > oprand;
    string expression;
    string str_op = "+-*/()";
    string::iterator i;
    cin >> expression;
    int error_flag = 0;

    for(i = expression.begin(); i < expression.end(); i++)
        if(str_op.find(*i, 0) != string::npos){
            if(!op.empty() && op.top() == '(' && *i == ')')
                op.pop();
            else if(op.empty() || judgePriority(*i, op.top()))
                op.push(*i);
            else{
                 BiNode<char>* right = (&(oprand.top()));
                 oprand.pop();
                 BiNode<char>* left = (&(oprand.top()));//new BiNode<char>(&(oprand.top()));
                 oprand.pop();
                 BiNode<char>* node = new BiNode<char>(op.top(), left, right);
                 op.pop();
//                 cout << node->getdata() << endl;
//                 cout << node->getlchild()->getdata() << endl;
//                 cout << node->getrchild()->getdata() << endl;

                 oprand.push(*node);
//                 cout << oprand.top().getdata() << endl;
//                 cout << oprand.top().getlchild()->getdata() << endl;
//                 cout << oprand.top().getrchild()->getdata() << endl;
                 i--;
            }
        }
        else if(*i >= 'a' && *i <= 'z'){
            BiNode<char>* node = new BiNode<char>(*i);
            oprand.push(*node);
        }
        else{
            cout << "Illegal input." << endl;
            return 1;
        }

//    oprand.pop();
//     oprand.pop();
//     if(oprand.top().getlchild() == NULL)
//         cout << "a is NULL." << endl;
//     else
//         cout <<  oprand.top().getlchild()->getdata() << endl;


    while(!op.empty()) {
         if(oprand.size() < 2){
             cout << "Illegal expression: Incorrect number of oprand or operator." << endl;
             error_flag = 1;
             break;
         }
//         cout <<  oprand.top().getdata() << endl;
         BiNode<char>* right = (&(oprand.top()));
         oprand.pop();
//         cout <<  oprand.top().getdata() << endl;
         BiNode<char>* left = (&(oprand.top()));
         oprand.pop();
         BiNode<char>* node = new BiNode<char>(op.top(), left, right);

         op.pop();
         oprand.push(*node);
//         cout <<  oprand.top().getdata();
//         cout <<  oprand.top().getlchild()->getdata() ;
//         cout <<  oprand.top().getrchild()->getdata() ;
    }


//    if(oprand.top().getlchild()->getlchild() == NULL)
//        cout << "a is NULL." << endl;

//    cout << (oprand.top().getlchild())->getdata() << endl;
    if(error_flag == 0)
        preOrder(&(oprand.top()));

    system("pause");
}
void preOrder(BiNode<char>* T) {
    if(T == NULL)
        return ;
    cout << T->getdata();
    preOrder(T->getlchild());
    preOrder(T->getrchild());
//    preOrder(T->getlchild());
}
bool judgePriority(char a, char b){
     string str_op = "+-*/()";
     size_t pos1 = str_op.find(a,0);
     size_t pos2 = str_op.find(b,0);    

     return prior[pos1][pos2];
}

using namespace std;
template<class T> class BiNode {
    public:
           BiNode(T elem){
                data = elem;
                lchild = NULL;
                rchild = NULL;
            }
           BiNode(BiNode* b){
                data = b->getdata();
                lchild = b->getlchild();
                rchild = b->getrchild();
           } 

           BiNode(T elem, BiNode* lchild, BiNode* rchild){
                data = elem;
                this->lchild = lchild;
                this->rchild = rchild;
            }
           BiNode* getlchild(){
                return lchild;
            }
           BiNode* getrchild(){
                return rchild;
            }
           T getdata(){
                return data;
           }
//           ~BiNode();

    private:
            BiNode* lchild;
            BiNode* rchild;
            T data;            
};

发现一个现象,就是如果将代码里面所有地方的

BiNode<char>* right = (&(oprand.top()));

BiNode<char>* left = (&(oprand.top()));

改成

BiNode<char>* right = new BiNode<char>(&(oprand.top()));

BiNode<char>* left = new BiNode<char>(&(oprand.top()));

就能输出正常。

可是如果不改,输出就会不正常。

经过逐步排错,我发现是下面这句出了问题:

oprand.push(*node);

将代码中oprand.push(*node);上下三行的cout语句解注,可以发现,在执行push语句之前,输出为-cd 执行push语句之后,输出为--d。六句cout语句执行的结果贴图如下。

图片说明

想请高手解答为什么push之后lchild的data被修改了?

(注:贴图的内容是在调试下输出的结果,如果直接执行程序的话会无限输出。希望也能帮忙解决为什么递归无法终止的问题)

1个回答

这个是典型的指针指向元素被释放/修改的例子。
stack<BiNode<char> > oprand可以理解为一个变长的数组BiNode oprand[N], 对其任何元素取的地址都不应在push/pop操作后使用,
因为stack/vector会在长度超过capacity以后reallocate, 之前的指针就失效了(指向的地址可能会被其他东西修改)。


                 BiNode<char>* right = (&(oprand.top())); // 假设当前oprand.size() = 10, then right = &(oprand[9])
                 oprand.pop( ); // 这时 right指向的item已经被释放, top指向8
                 BiNode<char>* left = (&(oprand.top()));// left =&(oprand[8])
                 oprand.pop();
                 BiNode<char>* node = new BiNode<char>(op.top(), left, right); // node->left=&(oprand[8]), node->right = &(oprand[9])
                 op.pop();
//                 cout << node->getdata() << endl;
//                 cout << node->getlchild()->getdata() << endl;
//                 cout << node->getrchild()->getdata() << endl;

                 oprand.push(*node); // 这行其实是用node指向的结构覆盖oprand[8],然后stack的size变9,覆盖之后lchild还是指向oprand[8](自己)
                                // 可以在这里加 cout << &(oprand.top()); cout<<oprand.top().getlchild(); 验证
//                 cout << oprand.top().getdata() << endl;
//                 cout << oprand.top().getlchild()->getdata() << endl;
//                 cout << oprand.top().getrchild()->getdata() << endl;

要避免这种情况很简单,用stack<BiNode<char>* > oprand,并且显式管理每一个node的分配释放即可,例如用另外一个vector存所有分配的指针,最后一起释放。
shared_ptr是另外一种方法,但是容易出现引用循环。
shawnchu_1
shawnchu_1 回复小玉我是龙叔呀: 是的,不考虑内存泄漏情况,stack里面存指针能够运行正确。oprand[8]的地址是不变的,但地址所在整个BiNode(原来的left)在push的时候被覆盖了。你可以在push以后马上打印*left的内容查看。
大约一年之前 回复
cnmbbbbbbbb
小玉我是龙叔呀 另外对您说的一点不太明白:并且显示管理每一个node的释放。 在stack里面存放指针确实可以避免出现上述的错误,如果不考虑内存泄漏的情况,就算我不释放我也可以保证结果正确把?
大约一年之前 回复
cnmbbbbbbbb
小玉我是龙叔呀 我可不可以这么理解:我这个栈s因为当前所处的内存位置是固定的,所以不管怎么push和pop,oprand[8]的地址就是不变的(只要不超过capacity)?
大约一年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问