Link to home
Start Free TrialLog in
Avatar of cbegin
cbegin

asked on

Help on an algorithm!!!

Question:

I am a C beginner. I am doing a program on a math expression
evalutation. In the program, I will input a math. expression like 2+3*5-5 in "stdin". First, I want to evaluate and the value for that expression ,which suppose return 12 as the answer. Second, I want to construct an expression tree for this expression tree. I know to put it vertically will be quite difficult! So I tried a horizontalone. Which it should look like this.


.......5.......
...-......5.....
+.....*........
...2......3.....              
..............
      However, since I am a C beginner and this is my first time write a C program dealing with the tree building stuff. I really a difficult job for me. I know the hard part of this program is to got the tree format done first. And I am working on that, however, every time I run the             program , my computer just halt. I wonder there may be something wrong with the pointer initiate on my program.
So if there are any C expert can help me with this program, I will highly appreciate. Since I am just a beginner, if you write the code,can you please write more specified so I won't have difficult to understand.

I really want to develop my programming skill on C and its
algorithm. I am looking for a C book that can guide me on those area. Also, if someone know there are some good C books teach me how to bulid trees and other algorithm in C, just let me know. I will highly appreciate !!!

                  Thanks,
                  A C beginner
Avatar of cbegin
cbegin

ASKER

Edited text of question
I've already answered this for someone else - you must be doing the same course.  I gave the other person some (untested) code that should build an expression tree.I'll supply that to you also.If you eMail me some code to mailto:Roger_Onslow@compsys.com.au then I may be able to have a look at it for you and point you in the right direction.See comments for code
/* this is the token type for the token stream */
enum OpType {
      ENDEXPR = 0,
      ADD = '+',
      SUB = '-',
      MUL = '*',
      DIV = '/',
      LPAREN = '(',
      RPAREN = ')',
      CONST = '#'
};

/* here is a token */
struct Token {
      OpType op;
      double number;      /* if op==CONST */
};

/* here is a node for the expression tree */
struct Node {
      OpType op;      /* type of node */
      union {
            double number;      /* if op==CONST */
            struct {
                  struct Node* pLhs;
                  struct Node* pRhs;
            } node;
      } arg;
}

/* create a new node with specified op type and args */
Node* NewNode (OpType op, Node* pLhs, Node* pRhs) {
      Node* pNode = malloc(sizeof(Node));
      pNode->op = op;
      pNode->node.pLhs = pLhs;
      pNode->node.pRhs = pRhs;
      return pNode;
}

/* create a new node for a constant number */
Node* NewNodeNumber (double number) {
      Node* pNode = malloc(sizeof(Node));
      pNode->op = CONST;
      pNode->arg.number = number;
      return pNode;
}

Node* IsConst(Node* pNode) {
      return pNode && pNode->op == CONST;
}

Node* IsOp(Node* pNode) {
      return pNode && pNode->op != CONST;
}

/* return Lhs pointer for node (if any) */
Node* Lhs(Node* pNode) {
      return IsOp(pNode) ? pNode->arg.node.pLhs : NULL;
}

/* return Rhs pointer for node (if any) */
Node* Rhs(Node* pNode) {
      return IsOp(pNode) ? pNode->arg.node.pRhs : NULL;
}

/* return number value for node (if any) */
double Number(Node* pNode) {
      return IsConst(pNode) ? pNode->arg.number : 0.0;
}

void DeleteNode (Node* pNode) {
      if (pNode) {
            if (IsOp(pNode)) {
                  DeleteNode(Lhs(pNode));
                  DeleteNode(Rhs(pNode));
            }
            free(pNode);
      }
}

/* assume an array of tokens has been built */
/* NOTE: token stream MUST finish with an ENDEXPR token */
/* then build an expression tree from the tokens */
/* and return a poitner to the root of the tree */
Node* BuildTree (Token tokens[]) {
      int i = 0;
      return BuildAddSub(tokens,&i);
}

/* build a tree for an add or subtract operation */
Node* BuildAddSub (Token tokens[], int& p) {
      Node* pNode = BuildMulDiv(tokens,p);
      while (pNode) {
            OpType op = tokens[*p].op;
            if (op == ADD || op == SUB) {
                  Node* pOther;
                  (*p)++;
                  pOther = BuildMulDiv(tokens,p);
                  pNode = NewNode(op,pNode,pOther);
            } else {
                  break;
            }
      }
      return pNode;
}

/* build a tree for a multiply or divide operation */
Node* BuildMulDiv (Token tokens[], int& p) {
      Node* pNode = BuildSimple(tokens,p);
      while (pNode) {
            OpType op = tokens[*p].op;
            if (op == MUL || op == DIV) {
                  Node* pOther;
                  (*p)++;
                  pOther = BuildSimple(tokens,p);
                  pNode = NewNode(op,pNode,pOther);
            } else {
                  break;
            }
      }
      return pNode;
}

/* build a tree for a () expression or a number */
Node* BuildSimple (Token tokens[], int& p) {
      Node* pNode = NULL;
      OpType op = tokens[*p].op;
      switch (op) {
      case LPAREN:
            (*p)++;
            pNode = BuildAddSub(tokens,p);
            op = tokens[*p].op;
            if (op != RPAREN) return NULL;
            (*p)++;
            break;
      case CONST:
            pNode = NewNodeNubmer(tokens[*p].number);
            (*p)++;
            break;
      }
      return pNode;
}

Hey - why the reject? What more do you want here?You still haven't show me any of your code - so I cannot tell you if your "pointer initiate" is the problem.  Please post it here or eMail it to me.Have a look at the code above (sorry about the formatting getting lost when the message was sent).  See if you can understand it.  I only provided minimal comments so you would have to LOOK at the code and YOU work out what it is doing.  If you have questions about what is going on, please ask.  If you really require fully commented code then I can give you that - but if you are trying to learn, then a little effort in trying to understand the raw code should be beneficial.Any good C book will help you with pointers - they are the most difficult and powerful features of C.  A bad pointer can wreak havoc, not only with the operation of your program, but also of your whole computer (if you don't have a nice protected operating system).This seems to be a programming assignment (as someone else had exactly the same problem, with the same expression tree) - are you after someone to write the assignment answer for you?  I am quite willing to help you write your own and to see why code you have written does not work - but don't expect a fully working program.
If you post your, non-functioning, code, perhaps some one can give you a better idea of what you are doing wrong.
I am not entirely sure about the "horizontal expression tree" structure that you are showing. It seems to me that Ronslow is right, you need to create a linked list. Algebraic notation can always be represented by a binary tree, so in that sense you are asking the right question.

Avatar of cbegin

ASKER

Edited text of question
ASKER CERTIFIED SOLUTION
Avatar of emmons
emmons

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
#include<stdio.h>
main()
{
      int ans;  //declare for answer of the expression
                int  i;      //for the for loop

      ans = 2+(3*5)-5 ; //expression

      printf("\n%d",ans);
      printf("\n\n");   //newline
      for (i=0;i<7;i++)    //for loop to repeat the act of the '.'
            printf(".");
      printf("5");
      for (i=0;i<7;i++)    //the same reason for the above
            printf(".");
      printf("\n...-......5.....");
      printf("\n+.....*..........");
      printf("\n...2......3.....\n");
      for(i=0;i<10;i++)
            printf(".");
      return 0;
}


If there is any doubt email me and i would like to know your full question because according to your question, there are some doubts that i'll like to clarify..eg..Do you ask user to key in anything?