小玉我是龙叔呀 2019-02-09 09:07 采纳率: 0%
浏览 611

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条回答 默认 最新

  • shawnchu_1 2019-02-10 10:28
    关注
    这个是典型的指针指向元素被释放/修改的例子。
    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是另外一种方法,但是容易出现引用循环。
    
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题