I keep getting WA on this problem, but I can't find a problem on my algorithm.
Here's my code:
http://pastebin.com/d6Xc7DP1
Code: Select all
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define NUM_NODES 256
template <class T>
class Tree
{
private:
T heap[NUM_NODES];
int hs[NUM_NODES]; // HeapStatus - 0: Não Setado; 1: Setado; 2: Não setado com filho
bool errflag;
int iCount;
int eCount;
public:
Tree()
{
this->errflag = false;
this->iCount = 0;
memset(this->heap, 0, NUM_NODES);
memset(this->hs, 0, NUM_NODES);
}
void insert(T content, char* dir);
void readTree();
bool isEmpty();
void setInvalid();
};
template <class T>
void Tree<T>::insert(T content, char* dir)
{
int aux = 1;
for(int i = 0; dir[i] != '\0'; i++)
{
// Nó da direita, posição 2n + 1
if(dir[i] == 'R')
{
aux *= 2;
aux += 1;
}
// Nó da esquerda, posição 2n
else if(dir[i] == 'L')
{
aux *= 2;
}
}
// Verifica se o nó inserido é filho de um nó não setado.
if(aux%2 && (aux - 1) && !this->hs[(aux - 1)/2 - 1])
{
this->hs[(aux - 1)/2 - 1] = 2;
this->iCount++;
} else if(!(aux%2) && !this->hs[aux/2 - 1])
{
this->hs[aux/2 - 1] = 2;
this->iCount++;
}
// Se o nó não foi setado e não tem filhos setados.
if(!this->hs[aux - 1])
{
this->heap[aux - 1] = content;
this->hs[aux - 1] = 1;
this->eCount++;
}
// Se o nó não foi setado mas tem filho setado.
else if(this->hs[aux - 1] == 2)
{
this->heap[aux - 1] = content;
this->hs[aux - 1] = 1;
this->iCount--;
this->eCount++;
} else this->errflag = true; // Se o nó já havia sido setado.
}
template <class T>
void Tree<T>::readTree()
{
if(!this->errflag && !this->iCount)
{
for(int i = 0; i < 256; i++)
{
if(this->hs[i])
{
this->eCount--;
if(this->eCount)
printf("%d ", (int) this->heap[i]);
else
printf("%d", (int) this->heap[i]);
}
}
printf("\n");
} else printf("not complete\n");
}
template <class T>
bool Tree<T>::isEmpty()
{
return !((bool) this->eCount);
}
template <class T>
void Tree<T>::setInvalid()
{
this->errflag = true;
}
int main()
{
Tree<unsigned long> *tree;
char buf[32];
unsigned long i_buf;
while(scanf("%s", buf) > 0)
{
tree = new Tree<unsigned long>();
while(strcmp(buf, "()"))
{
i_buf = 0;
for(int i = 1; buf[i] != ','; i++)
{
if(buf[i] == '-')
{
tree->setInvalid();
break;
}
if((buf[i] >= '0')&&(buf[i] <= '9'))
{
i_buf = i_buf*10 + (buf[i] - '0');
}
}
if(!i_buf) tree->setInvalid();
else tree->insert(i_buf, buf);
scanf("%s", buf);
}
if(!tree->isEmpty()) tree->readTree();
else printf("not complete\n");
delete tree;
}
return 0;
}
I've tried the following input:
Code: Select all
()
(,) ()
(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
(22,) (33,L) (44,LL) ()
(22,) (44,LL) ()
(11,LL) (7,LLL) (8,R) ()
(11,LL) (7,LLL) (8,R) (6,L) (4,) ()
(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) (2,RRR) ()
(5,) (4,L) (13,RL) (5,L) (6,R) ()
(5,) (6,L) ()
(3,) ()
(4,LL) (3,L) (2,) (6,R) ()
(,L) (22,L) (22,) ()
(3,R) (,L) (22,L) (22,) ()
My output was:
Code: Select all
not complete
not complete
5 4 8 11 13 4 7 2 1
not complete
22 33 44
not complete
not complete
4 6 8 11 7
5 4 8 11 13 4 7 2 1
not complete
not complete
not complete
5 6
3
2 3 6 4
not complete
not complete
Which seems about right to me.
I'd be glad if anyone could help me.
Thanks.
