Hey Folks,
I've had this project in the back of my mind for about a year now. I
never seem to get enough time to work in it. I am offering up an
outline of the initial objectives so that I might find other people who
are interested in contributing. I simply don't have the time to do it
myself. I apologize if I am not as clear as I would like to, or should,
be regarding all aspects of what I am attempting.
I am trying to write a "logical parser" that will read in symbolic logic
statements and parse them into trees. For example it would read A & B
and create a tree with & as the root, A as the left child, and B as the
right child. After the tree is created I want to evaluate (traverse)
the tree for every possible combination of truth values. In my example
that would be A=1, B=1, result=1; A=1, B=0, result=0; and etc. Here's a
URL to a graphical representation of what I'm talking about: [
http://www.geocities.com:80/Heartland/Estates/2913/calc/treea_38.htm ]
There are 39 slides total, including the summary. You may wish to look
at a few of them. I have a 21" monitor with 1600 x 1200 res, so the
slides may seem a little large to folks with more limited resources.
There are links at the bottom of each slide that allow you to navigate
the sequence of iterations. I suggest looking at the first few slides
and the last one in order to get a good feel for what is supposed to
happen. The slides were developed using Star Office 4.0. & should have
precedence over ||, so the expression that created the tree would be A &
B & C & D || E & F || G. (I hope I'm doing this right.)
I came up with an algorithm that I think will create the tree. (I
believe the one I dredged up is the correct one.) Here it is:
struct node{
char* token;
int value; //holds boolean value
node* lc; //left child
node* rc; //right child
};
initilize //get the first input token and set up the pointers
curr = new node(token) //points to the current data object and gets the
value of token from input
root = curr //points to the root data object
sr = curr //points to
while curr = new node(token)->name != EOL // stop when you run out of
input
{
if curr->token is var // us the token a variable? e.g. A, B, or C
sr->rc=curr
if sr->token == ||
sr=sr->rc
else if curr->token == &
curr->lc = sr
sr=curr
if sr->lc == root
root = sr
else
root->rc = sr
else if curr->token == ||
curr->lc = root
sr = curr
if sr->lc == root
root = sr
}
"||" may be a bad choice of symbols for "or". That really doesn't
matter at this point. If you wish to test the algorithm just create
some logical string and then run it through. My slides were produced by
doing just that.
One question I have regarding an implementation of this is whether I
should attempt to use OOP, messages and methods for the act of adding
children and redirecting the root pointer etc., or just use structures
and functions to do the job. I would love to try both approaches and
see what happens in each. Currently I don't deal with parentheses. My
long-term objective is to algorithmically code most of foundational
mathematics. Who knows where this may lead? Perhaps nowhere but my
getting flamed for posting it here. :-\
This may not be exactly SuSE related, but I've got to start somewhere.
I figure I should start with folks I already know. If people object to
my/our discussing this on this list I will try to find another place to
work on it. BTW, I don't know if this is legally binding, but this
algorithm is hereby GPL'ed.
--
http://www.winehq.com | I think.
http://www.suse.com | I think I am.
http://www.kde.org | Therefore I am.
http://samba.anu.edu.au | I think? - Moody Blues
--
To get out of this list, please send email to [EMAIL PROTECTED] with
this text in its body: unsubscribe suse-linux-e
Check out the SuSE-FAQ at http://www.suse.com/Support/Doku/FAQ/ and the
archive at http://www.suse.com/Mailinglists/suse-linux-e/index.html
