Trees Query

Discussion in 'C Programming' started by ekiMbo, Oct 21, 2004.

  1. ekiMbo

    ekiMbo Guest

    Hey, I'm a newbie C programmer doing first semester kind of coding. I'm
    attempting to read input from the keyboard of the form "Af RtS"
    representing a boolean logic expression, here it represents ((NOT a AND f)
    OR (NOT R and t and NOT s)).

    This will (eventually) get simplified as much as possible and be used to
    generate a PostScript file to draw a circuit diagram (logic gates etc).
    I've only just started though and I'm wondering what the best data
    structure to store characters is. A linked list will work with the simple
    things I'm doing now but ideally I want to be able to use parenthesis to
    allow more complicated statements to be made. At the moment I have a kind
    of binary tree with each node having an AND and an OR pointer.

    A -OR-> R

    | |
    and and
    v v

    f t
    |
    and
    v

    S

    Traversing it by going down each branch sequentially... Not sure how I'm
    going to allow parentheses though.

    Just wondering if this is a decent way of doing it, any suggestions on
    improvements or different ideas much appreciared. Also any comments on
    general coding style etc. would be helpful.

    #include <stdio.h>
    #include <stdlib.h>

    typedef struct node {
    char letter;
    struct node *child;
    struct node *sibling;
    } node;

    node *createFirstNode(char c)
    {
    node *firstNode = malloc(sizeof(node));
    firstNode->letter = c;
    firstNode->child = NULL;
    firstNode->sibling = NULL;
    return firstNode;
    }
    node *createNode(char c)
    {
    node *newNode = malloc(sizeof(node));

    if(currentNode==NULL)
    {
    currentParent->sibling = newNode;
    currentParent = newNode;
    currentNode = newNode;
    }
    else if(currentNode==currentParent)
    {
    currentNode->child = newNode;
    currentNode = newNode;
    }
    else
    {
    currentNode->sibling = newNode;
    currentNode = newNode;
    }

    newNode->letter = c;
    return newNode;
    }
    node *firstNode, currentNode, currentParent;
    int main()
    {
    int i;
    char c;
    while(1)
    {
    c = getchar;
    if ( c >= 97 && c <= 122 )
    {
    firstNode=createFirstNode(c);
    break;
    }
    }
    currentParent = firstNode;
    currentNode = firstNode;

    while(1)
    {
    c = getchar();
    if (c == 10) /*if c is the enter key */
    {
    printf("Finished inputting the tree\n");
    break;
    }
    if (c == 32) /*if c is the space key*/
    currentNode=NULL;
    if ( c >= 97 && c <= 122 )
    {
    createNode(c);
    printf("fn:%p cp:%p cn:%p\n",firstNode,currentParent,currentNode);
    }
    }

    return(0);
    }
    ekiMbo, Oct 21, 2004
    #1
    1. Advertising

  2. ekiMbo

    Michael Mair Guest

    ekiMbo wrote:
    > Hey, I'm a newbie C programmer doing first semester kind of coding. I'm
    > attempting to read input from the keyboard of the form "Af RtS"
    > representing a boolean logic expression, here it represents ((NOT a AND f)
    > OR (NOT R and t and NOT s)).
    >
    > This will (eventually) get simplified as much as possible and be used to
    > generate a PostScript file to draw a circuit diagram (logic gates etc).
    > I've only just started though and I'm wondering what the best data
    > structure to store characters is. A linked list will work with the simple
    > things I'm doing now but ideally I want to be able to use parenthesis to
    > allow more complicated statements to be made. At the moment I have a kind
    > of binary tree with each node having an AND and an OR pointer.
    >
    > A -OR-> R
    >
    > | |
    > and and
    > v v
    >
    > f t
    > |
    > and
    > v
    >
    > S
    >
    > Traversing it by going down each branch sequentially... Not sure how I'm
    > going to allow parentheses though.
    >
    > Just wondering if this is a decent way of doing it, any suggestions on
    > improvements or different ideas much appreciared. Also any comments on
    > general coding style etc. would be helpful.


    Algorithms and the like are offtopic here.
    <OT>
    If you are going to evaluate the expressions eventually and for one
    set of values for your variables, I suggest going directly for it by
    using operator precedence and (recursive) function calls. Only for
    evaluating many state combinations of the variables I would go to
    the effort of handling a binary tree.
    You pass on the read-in string or copies of parts (but I would then
    rather use explicit AND and OR operators).

    This is no precise formulation of the algorithm, just something to get
    you started:
    EvalExpression("Af RtS")
    looks for the first operator of lowest priority (OR) and passes
    everything that comes before encountering ' '/OR (here:"Af") to
    EvalOr(). If this returns TRUE, EvalExpression() returns TRUE, else
    EvalExpression() returns EvalExpression() of the rest of the string
    or FALSE if there is no rest.
    EvalOr() looks for AND-Expressions and passes the first to EvalAnd()
    in the same way.
    EvalAnd() can either look at the value or can pass it on to EvalNot()
    or EvalValue(), respectively.
    Parentheses and other operators can be fit easily into this scheme;
    if you encounter '(', you start looking for the closing parenthesis
    (which balances the opening and closing parentheses for the first time)
    and pass the "content", that is, the stuff between the parentheses to
    EvalExpression() if necessary. You can do this equivalently for your
    binary tree.
    </OT>
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    >
    > typedef struct node {
    > char letter;
    > struct node *child;
    > struct node *sibling;
    > } node;
    >
    > node *createFirstNode(char c)
    > {
    > node *firstNode = malloc(sizeof(node));
    > firstNode->letter = c;
    > firstNode->child = NULL;
    > firstNode->sibling = NULL;
    > return firstNode;
    > }
    > node *createNode(char c)
    > {
    > node *newNode = malloc(sizeof(node));
    >
    > if(currentNode==NULL)
    > {
    > currentParent->sibling = newNode;
    > currentParent = newNode;
    > currentNode = newNode;
    > }
    > else if(currentNode==currentParent)
    > {
    > currentNode->child = newNode;
    > currentNode = newNode;
    > }
    > else
    > {
    > currentNode->sibling = newNode;
    > currentNode = newNode;
    > }
    >
    > newNode->letter = c;
    > return newNode;
    > }
    > node *firstNode, currentNode, currentParent;

    This certainly is not your code -- firstNode, currentNode and
    currentParent are first declared here but not known in the
    above functions. Please give us code that compiles.
    Apart from that: You probably mean
    node *firstNode, *currentNode, *currentParent;
    > int main()
    > {
    > int i;
    > char c;
    > while(1)
    > {
    > c = getchar;

    You probably mean getchar()
    > if ( c >= 97 && c <= 122 )

    Do not use hard-coded numbers but the functions from <ctype.h>
    to check. Example: If you mean lowercase letters, use islower().
    > {
    > firstNode=createFirstNode(c);
    > break;
    > }
    > }
    > currentParent = firstNode;
    > currentNode = firstNode;
    >
    > while(1)
    > {
    > c = getchar();
    > if (c == 10) /*if c is the enter key */

    Dito: use '\n'
    > {
    > printf("Finished inputting the tree\n");
    > break;
    > }
    > if (c == 32) /*if c is the space key*/

    Dito: use ' '
    > currentNode=NULL;
    > if ( c >= 97 && c <= 122 )
    > {
    > createNode(c);
    > printf("fn:%p cp:%p cn:%p\n",firstNode,currentParent,currentNode);
    > }
    > }
    >
    > return(0);
    > }


    Please give us the code you work with. This crap does not compile
    and certainly will not give results of any sensible kind.
    Moreover, it does not implement the algorithm you suggest.


    Michael
    --
    E-Mail: Mine is a gmx dot de address.
    Michael Mair, Oct 21, 2004
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Pif

    Trees in java

    Pif, Apr 6, 2004, in forum: Java
    Replies:
    1
    Views:
    433
    Manolo
    Apr 6, 2004
  2. jova

    Binary Trees

    jova, Apr 25, 2004, in forum: Java
    Replies:
    11
    Views:
    730
    Roedy Green
    Apr 26, 2004
  3. Joona I Palaste

    Trees in the Java Collections framework

    Joona I Palaste, Jun 8, 2004, in forum: Java
    Replies:
    5
    Views:
    549
    Chris Uppal
    Jun 9, 2004
  4. Rico

    B+-trees

    Rico, Jul 29, 2004, in forum: Java
    Replies:
    10
    Views:
    1,715
    Eric Sosman
    Aug 2, 2004
  5. jacob navia

    Binary search trees (AVL trees)

    jacob navia, Jan 3, 2010, in forum: C Programming
    Replies:
    34
    Views:
    1,411
    Dann Corbit
    Jan 8, 2010
Loading...

Share This Page