多叉树的括号表示法(字符串)然后层序输出。自己检查了好久也没有看出问题来,能运行出来结果,但是提交测试时出错。
输入:(a(b,c,d,e))输出样例:abcde
//下面是我写的代码:
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
using namespace std;
template<class T>
struct LinkNode
{
T data;
LinkNode<T>* link;
LinkNode(T value,LinkNode<T>* p=NULL):data(value)
{
link=p;
}
};
template<class T>
class Link_queue
{
protected:
LinkNode<T> *first,*rear;
public:
Link_queue():first(NULL),rear(NULL) {}
~Link_queue();
bool Enqueue(const T& x);
bool Dequeue(T& x);
bool IsEmpty(){return (first==NULL) ? true:false;}
void output();
};
template<class T>
void Link_queue<T>::output()
{
LinkNode<T>* p=first;
while(p!=NULL)
{
cout<<p->data;
p=p->link;
}
}
template<class T>
Link_queue<T>::~Link_queue()
{
LinkNode<T>* p;
while(first!=NULL)
{
p=first;
first=first->link;
delete p;
}
}
template<class T>
bool Link_queue<T>::Enqueue(const T& x)
{
if(first==NULL)
{
first=rear=new LinkNode<T>(x);
if(first==NULL)
return false;
}
else
{
rear->link=new LinkNode<T>(x);
if(rear->link==NULL)
return false;
rear=rear->link;
}
return true;
}
template<class T>
bool Link_queue<T>::Dequeue(T& x)
{
if(IsEmpty()==true)
return false;
LinkNode<T>* p=first;
x=first->data;
first=first->link;
delete p;
return true;
}
int Levels(char*& str)
{
int levels=0,n=strlen(str);
for(int i=0;i<n;i++)
{
if(str[i]=='(')
levels++;
}
return levels;
}
int InLevels(char*& str,char& x)
{
int i=0,left=0,right=0;
char ch=str[0];
while(ch!=x)
{
ch=str[i];
i++;
if(ch=='(')
left++;
if(ch==')')
right++;
}
return left-right;
}
int main()
{
string string_str;
cin>>string_str;
int Count=string_str.length();
char* str=new char[Count+1];
for(int i=0;i<Count;i++)
{
str[i]=string_str[i];
}
int levels=Levels(str);
Link_queue<char>* levels_queue=new Link_queue<char>[levels];
int i;
for(i=0;i<Count;i++)
{
if(str[i]!=','&&str[i]!='('&&str[i]!=')')
{
int n=InLevels(str,str[i]);
levels_queue[n].Enqueue(str[i]);
}
}
for(i=0;i<levels;i++)
{
levels_queue[i].output();
}
cout<<endl;
delete [] str;
delete [] levels_queue;
return 0;
}