This IS a class project.
If this is frowned upon getting help for, then I apologize.
The project is to take a data set of species, and organize it into a data structure of our choice (I chose a tree). The user enters a search query based on county, for example, NC:Camden (would you Camden county, North Carolina). The user can enter mutiple counties and search for something like County1 AND County2 OR County3 AND County4.
My program correctly creates a post fix expression out of this (County1 County2 AND County3 County4 AND OR). It however, does not evaluate it correctly. The result of County1 and County2 seems to get lost, and when it gets to the OR stage, it does County3 AND County4 OR County3 AND County4.
A little bit of how my program is set up. The postfix expression is stored in a string array called pquery, and the stack contains pointers to the resulting trees formed by the AND and OR operations and the initial trees it operates on.
Code:
for (int i = 0; i < 20; i++) //evalute postfix
{
if (pquery[i] == "OR" || pquery[i] == "AND") //if an operator, pop two from the stack, operate on them, then push the result back on
{
a = tree.top();
tree.pop();
b = tree.top();
tree.pop();
if (pquery[i] == "OR")
{
a->merge(a, b); //a is the resulting tree from this operation.
cTree *n = new cTree;
n = a;
tree.push(n);
}
else
{
a->both(a, b, t); //t is the resulting tree from this operation
cTree *n = new cTree;
n = t;
tree.push(n);
}
}
else if (pquery[i] != "")
{
cTree *n = new cTree;
in[i].open(pquery[i].c_str()); // This reads from the appropriate text file and builds a tree out of it.
//Finally it pushes the tree onto the stack.
in[i] >> family >> genus;
in[i].get(c);
getline(in[i], species);
n->insert(family, genus, species);
in[i] >> family >> genus;
in[i].get(c);
getline(in[i], species);
while (in[i])
{
n->insert(family, genus, species);
in[i] >> family >> genus;
in[i].get(c);
getline(in[i], species);
}
in[i].close();
tree.push(n);
}
}
Here is the output log of the push/pop operations.
Code:
Enter a search query: NC:Test1 AND NC:Test2 OR NC:Test3 AND NC:Test4
Pushed:
F = Asteraceae
G = Solidago
S = Soligago radula
G = Madia
S = Madia sativa
F = Acanthaceae
G = Justicia
S = Justicia ovata
Pushed:
F = Asteraceae
G = Madia
S = Madia sativa
F = Acanthaceae
G = Justicia
S = Justicia ovata
Popped:
F = Asteraceae
G = Madia
S = Madia sativa
F = Acanthaceae
G = Justicia
S = Justicia ovata
Popped:
F = Asteraceae
G = Solidago
S = Soligago radula
G = Madia
S = Madia sativa
F = Acanthaceae
G = Justicia
S = Justicia ovata
Pushed:
F = Asteraceae
G = Madia
S = Madia sativa
F = Acanthaceae
G = Justicia
S = Justicia ovata
Pushed:
F = Aceraceae
G = Acer
S = Acer rubrum
S = Acer negundo
Pushed:
F = Aceraceae
G = Acer
S = Acer negundo
F = Alismataceae
G = Sagittaria
S = Sagittaria latifolia
Popped:
F = Aceraceae
G = Acer
S = Acer negundo
F = Alismataceae
G = Sagittaria
S = Sagittaria latifolia
Popped:
F = Aceraceae
G = Acer
S = Acer rubrum
S = Acer negundo
Pushed:
F = Aceraceae
G = Acer
S = Acer negundo
Popped:
F = Aceraceae
G = Acer
S = Acer negundo
Popped:
F = Aceraceae
G = Acer
S = Acer negundo
Pushed:
F = Aceraceae
G = Acer
S = Acer negundo
Final Result:
F = Aceraceae
G = Acer
S = Acer negundo
If you follow the push/pop log, you'll notice that the third item pushed (which is the result of NC:Test1 AND NC:Test2):
Code:
F = Asteraceae
G = Madia
S = Madia sativa
F = Acanthaceae
G = Justicia
S = Justicia ovata
Never makes it to the end to be OR'ed with Test3 AND Test4. It just of gets lost in the stack somehow. I've looked at this and stepped through the program at all the branch points, and I just have no idea what is happening to the tree that's getting lost, however I'm certain that I'm messing a pointer up somewhere and I'm just not seeing it.
Any suggestions?
Dev Articles Community Forums Sponsor:
April 20th, 2006, 05:34 PM
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
