cnmbbbbbbbb
小玉我是龙叔呀
2019-02-09 09:07

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

  • c++
  • 开发语言

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条回答