We help IT Professionals succeed at work.

# Help on an algorithm!!!

on
Medium Priority
447 Views
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
Comment
Watch Question

## View Solution Only

Commented:
Edited text of question

Commented:
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

Commented:
/* this is the token type for the token stream */
enum OpType {
ENDEXPR = 0,
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;
}

/* 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)++;
op = tokens[*p].op;
if (op != RPAREN) return NULL;
(*p)++;
break;
case CONST:
pNode = NewNodeNubmer(tokens[*p].number);
(*p)++;
break;
}
return pNode;
}

Commented:

Commented:
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.

Commented:
Edited text of question
Commented:
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 
* 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 
* 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 
* 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 
* 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 
* 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 
* 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 
* Compilers Principles, Techniques, and Tools
* pages 73 - 78
*/
#include "global.h"
parse()                  /* parses and translates expression list */
{
expr(); match(';');
}
}

expr()
{
int t;
term();
while (1)
case '+': case '-':
continue;
default:
return;
}
}

term()
{
int t;
factor();
while (1)
case '*': case '/': case DIV: case MOD:
continue;
default:
return;
}
}

factor()
{
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;
{
else error("syntax error");
}
/*
* SYMBOL.H
* Aho, A. V., R Sethi, and J. D. Ullman 
* 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)

Not the solution you were looking for? Getting a personalized solution is easy.

Commented:
#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?
##### Thanks for using Experts Exchange.

• View three pieces of content (articles, solutions, posts, and videos)
• Ask the experts questions (counted toward content limit)
• Customize your dashboard and profile