http://58.51.82.174/JudgeOnline/showproblem?problem_id=1168
#include <iostream>
using namespace std;
string origindata;
int length;
int fa[101];
int curpointer;
struct
treenode
{
int father;
int leftc;
int rightc;
char data;
treenode()
{
father =
leftc =
rightc = -1;
data = '!';
}
}tr[101];
void
__read__()
{
cin >> origindata;
length = origindata.length();
}
void
__convert__( int x, int father )
{
if( x < length )
{
if( origindata[x] != '(' && origindata[x] != ')' )
{
if( tr[father].leftc == -1 )
{
tr[father].leftc = ++curpointer;
tr[tr[father].leftc].data = origindata[x];
tr[tr[father].leftc].father = father;
}
else
{
int pointer = tr[father].leftc;
while( tr[pointer].rightc != -1 )
pointer = tr[pointer].rightc;
tr[pointer].rightc = ++curpointer;
tr[tr[pointer].rightc].data = origindata[x];
tr[tr[pointer].rightc].father = tr[pointer].father;
}
__convert__( x + 1, father );
}
if( origindata[x] == ')' )
__convert__( x + 1, tr[father].father );
if( origindata[x] == '(' )
{
int pointer = 1;
for( int i = 1; i <= curpointer; i++ )
if( tr[i].data == origindata[x - 1] )
pointer = i;
__convert__( x + 1, pointer );
}
}
}
void
__previsit__( int x )
{
if( tr[x].data != '!' )
cout << tr[x].data;
if( tr[x].leftc != -1 )
__previsit__( tr[x].leftc );
if( tr[x].rightc != -1 )
__previsit__( tr[x].rightc );
}
void
__midvisit__( int x )
{
if( tr[x].leftc != -1 )
__midvisit__( tr[x].leftc );
if( tr[x].data != '!' )
cout << tr[x].data;
if( tr[x].rightc != -1 )
__midvisit__( tr[x].rightc );
}
void
__posvisit__( int x )
{
if( tr[x].leftc != -1 )
__posvisit__( tr[x].leftc );
if( tr[x].rightc != -1 )
__posvisit__( tr[x].rightc );
if( tr[x].data != '!' )
cout << tr[x].data;
}
void
__outp__()
{
__previsit__( 0 ); cout << endl;
__midvisit__( 0 ); cout << endl;
__posvisit__( 0 ); cout << endl;
}
int
main()
{
__read__();
__convert__( 0, 0 );
__outp__();
return 0;
}