Solved

Help on an algorithm!!!

Posted on 1997-04-22
8
375 Views
Last Modified: 2006-11-17
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
0
Comment
Question by:cbegin
  • 3
  • 2
  • 2
  • +1
8 Comments
 

Author Comment

by:cbegin
ID: 1250058
Edited text of question
0
 
LVL 10

Expert Comment

by:RONSLOW
ID: 1250059
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
 
LVL 10

Expert Comment

by:RONSLOW
ID: 1250060
/* 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
 
LVL 10

Expert Comment

by:RONSLOW
ID: 1250061
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
Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

 
LVL 4

Expert Comment

by:emmons
ID: 1250062
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
 

Author Comment

by:cbegin
ID: 1250063
Edited text of question
0
 
LVL 4

Accepted Solution

by:
emmons earned 200 total points
ID: 1250064
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
 

Expert Comment

by:lyn042297
ID: 1250065
#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

Featured Post

Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.

747 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now