• C

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
cbeginAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

cbeginAuthor Commented:
Edited text of question
0
RONSLOWCommented:
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
0
RONSLOWCommented:
/* 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;
}

0
Do You Have a Trusted Wireless Environment?

A Trusted Wireless Environment is a framework for building a complete Wi-Fi network that is fast, easy to manage, and secure.

RONSLOWCommented:
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.
0
emmonsCommented:
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.

0
cbeginAuthor Commented:
Edited text of question
0
emmonsCommented:
OK, I am still not certain what you are looking for.
In lieu of you actually POSTING YOUR CODE.
Try this. It will parse an arithmetic expression.
/*
* MAIN.C
 * Aho, A. V., R Sethi, and J. D. Ullman [1986]
 * Compilers Principles, Techniques, and Tools
 * pages 73 - 78
 */
#include "global.h"
main()
{
    init();
    parse();
    exit(0);            /* successful termination */
}

/*
* EMITTER.C
 * Aho, A. V., R Sethi, and J. D. Ullman [1986]
 * Compilers Principles, Techniques, and Tools
 * pages 73 - 78
 */
#include "global.h"
emit(t, tval)            /* generates output */
    int t, tval;
{
    switch(t) {
      case '+': case '-': case '*': case '/':
          printf("%c\n", t); break;
      case DIV:
          printf("DIV\n"); break;
      case MOD:
          printf("MOD\n"); break;
      case NUM:
          printf("%d\n", tval); break;
      case ID:
          printf("%s\n", symtable[tval].lexptr); break;
      default:
           printf("token %d, tokenval %d\n", t, tval);
    }
}
/*
* ERROR.C
 * Aho, A. V., R Sethi, and J. D. Ullman [1986]
 * Compilers Principles, Techniques, and Tools
 * pages 73 - 78
 */
#include "global.h"
error(m)            /* generates all error messages */
    char *m;
{
    fprintf(stderr, "line %d: %s\n", lineno, m);
    exit(1);            /* unsuccessful termination */
}

/*
* GLOBAL.H
 * Aho, A. V., R Sethi, and J. D. Ullman [1986]
 * Compilers Principles, Techniques, and Tools
 * pages 73 - 78
 */
#include <stdio.h>
#include <ctype.h>

#define BSIZE 128            /* buffer size */
#define NONE -1
#define EOS '\0'
#define NUM 256
#define DIV 257
#define MOD 258
#define ID 259
#define DONE 260

int tokenval;                  /* value of token attribute */
int lineno;

struct entry {                  /* form of symbol table entry */
    char *lexptr;
    int token;
};

struct entry symtable[];      /* symbol table */

/*
* INIT.H
 * Aho, A. V., R Sethi, and J. D. Ullman [1986]
 * Compilers Principles, Techniques, and Tools
 * pages 73 - 78
 */
#include "global.h"
struct entry keywords[] = {
    "div", DIV,
    "mod", MOD,
    0, 0
};

init()                  /* loads keywords into symtable */
{
    struct entry *p;
    for (p = keywords; p->token; p++)
      insert(p->lexptr, p->token);
}
/*
* LEXER.H
 * Aho, A. V., R Sethi, and J. D. Ullman [1986]
 * Compilers Principles, Techniques, and Tools
 * pages 73 - 78
 */
#include "global.h"
char lexbuf[BSIZE];
int lineno = 1;
int tokenval = NONE;

int lexan()                  /* lexical analyzer */
{
    int t;
    while (1) {
      t = getchar();
      if (t == ' ' || t == '\t')
          ;                  /* strip out white space */
      else if (t == '\n')
          lineno = lineno + 1;
      else if (isdigit(t)) {      /* t is a digit */
          ungetc(t, stdin);
          scanf("%d", &tokenval);
          return NUM;
      }
      else if (isalpha(t)) {      /* t is a letter */
          int p, b = 0;
          while (isalnum(t)) { /* t is alphanumeric */
              lexbuf[b] = t;
            t = getchar();
            b = b + 1;
            if (b >= BSIZE)
                error("compiler error");
          }
          lexbuf[b] = EOS;
          if (t != EOF)
              ungetc(t, stdin);
          p = lookup(lexbuf);
          if (p == 0)
              p = insert(lexbuf, ID);
          tokenval = p;
          return symtable[p].token;
      }
      else if (t == EOF)
          return DONE;
      else {
          tokenval = NONE;
          return t;
      }
    }
}
/*
* PARSER.H
 * Aho, A. V., R Sethi, and J. D. Ullman [1986]
 * Compilers Principles, Techniques, and Tools
 * pages 73 - 78
 */
#include "global.h"
int lookahead;
parse()                  /* parses and translates expression list */
{
    lookahead = lexan();
    while (lookahead != DONE) {
      expr(); match(';');
    }
}

expr()
{
    int t;
    term();
    while (1)
        switch (lookahead) {
          case '+': case '-':
              t = lookahead;
            match(lookahead); term(); emit(t,NONE);
            continue;
          default:
              return;
      }
}

term()
{
    int t;
    factor();
    while (1)
        switch(lookahead) {
          case '*': case '/': case DIV: case MOD:
              t = lookahead;
            match(lookahead); factor(); emit(t,NONE);
            continue;
          default:
              return;
      }
}

factor()
{
    switch(lookahead) {
      case '(':
          match('('); expr(); match(')'); break;
      case NUM:
          emit(NUM, tokenval); match(NUM); break;
      case ID:
          emit(ID, tokenval); match(ID); break;
      default:
          error("syntax error");
    }
}

match(t)
    int t;
{
    if (lookahead == t)
        lookahead = lexan();
    else error("syntax error");
}
/*
* SYMBOL.H
 * Aho, A. V., R Sethi, and J. D. Ullman [1986]
 * Compilers Principles, Techniques, and Tools
 * pages 73 - 78
 */
#include "global.h"
#define STRMAX 999            /* size of lexemes array */
#define SYMMAX 100            /* size of symtable */

char lexemes[STRMAX];
int lastchar = -1;            /* last used position in lexemes */
struct entry symtable[SYMMAX];
int lastentry = 0;            /* last used position in symtable */

int lookup(s)                  /* returns position of entry for s */
    char s[];
{
    int p;
    for (p = lastentry; p > 0; p = p - 1)
        if (strcmp(symtable[p].lexptr, s) == 0)
          return p;
    return 0;
}

int insert(s, tok)            /* returns position of entry for s */
    char s[];
    int tok;
{
    int len;
    len = strlen(s);            /* strlen computes length of s */
    if (lastentry + 1 >= SYMMAX)
        error("symbol table full");
    if (lastchar + len + 1 >= STRMAX)
      error("lexemes array full");
    lastentry = lastentry + 1;
    symtable[lastentry].token = tok;
    symtable[lastentry].lexptr = &lexemes[lastchar + 1];
    lastchar = lastchar + len + 1;
    strcpy(symtable[lastentry].lexptr, s);
    return lastentry;
}

------------Makefile (for Unix)--------------
SRCS            = lexer.c parser.c emitter.c symbol.c init.c error.c main.c
OBJS            = lexer.o parser.o emitter.o symbol.o init.o error.o main.o
HDRS            = global.h /usr/include/stdio.h /usr/include/ctype.h
PROG            = trans

all:            $(PROG)

trans:            $(HDRS) $(OBJS)
            $(CC) $(CFLAGS) -o $(PROG) $(OBJS)

clean:
            -rm $(OBJS) $(PROG)

lint:
            lint -lc $(SRCS)

0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
lyn042297Commented:
#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?
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.