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被修改了?
(注:贴图的内容是在调试下输出的结果,如果直接执行程序的话会无限输出。希望也能帮忙解决为什么递归无法终止的问题)