Thread View: bln.sci.informatik
4 messages
4 total messages
Started by Alex Scherbel
Tue, 15 Oct 2002 20:29
a+(b*c) in Baum darstellen (Algorithmus)
Author: Alex Scherbel
Date: Tue, 15 Oct 2002 20:29
Date: Tue, 15 Oct 2002 20:29
13 lines
1812 bytes
1812 bytes
Hallo!
Kennt jemand einen Algorithmus, der einen Infix-Ausdruck in einem Baum
darstellen kann?
Also zum Beispiel:
a+(b*c) => +
/ \
a *
/ \
b c
Gru� Andy
Re: a+(b*c) in Baum darstellen (Algorithmus)
Author: Hermann Kremer
Date: Tue, 15 Oct 2002 23:21
Date: Tue, 15 Oct 2002 23:21
532 lines
16966 bytes
16966 bytes
Alex Scherbel schrieb in Nachricht <3dac82a2$0$171$9b622d9e@news.freenet.de>...
>Hallo!
>
>Kennt jemand einen Algorithmus, der einen Infix-Ausdruck in einem Baum
>darstellen kann?
>Also zum Beispiel:
>
> a+(b*c) => +
> / \
> a *
> / \
> b c
>Gru� Andy
Der folgende macht noch viel mehr:
/*************************************************************************/
/* */
/* EVALUATE.C - A simple mathematical expression evaluator in C */
/* */
/* operators supported: Operator Precedence */
/* */
/* ( Lowest */
/* ) Highest */
/* + (addition) Low */
/* - (subtraction) Low */
/* * (multiplication) Medium */
/* / (division) Medium */
/* % \ (modulus) High */
/* ^ (exponentiation) High */
/* sin( Lowest */
/* cos( Lowest */
/* atan( Lowest */
/* abs( Lowest */
/* sqrt( Lowest */
/* ln( Lowest */
/* exp( Lowest */
/* ceil( Lowest */
/* floor( Lowest */
/* round( Lowest */
/* */
/* */
/* constants supported: pi */
/* */
/* */
/* SYNOPSIS: eval "expression" */
/* */
/* */
/* Original Copyright 1991-93 by Robert B. Stout as part of */
/* the MicroFirm Function Library (MFL) */
/* */
/* This subset version is hereby donated to the public domain. */
/* */
/*************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
typedef enum {Error_ = -1, Success_, False_ = 0, True_} Boolean_T;
typedef unsigned char BYTE;
typedef unsigned long DWORD;
typedef unsigned short WORD;
struct operator {
char token;
char *tag;
size_t taglen;
int precedence;
};
static struct operator verbs[] = {
{'+' , "+", 1, 2 },
{'-' , "-", 1, 3 },
{'*' , "*", 1, 4 },
{'/' , "/", 1, 5 },
{'%' , "%" , 1, 5 },
{'\\', "\\", 1, 5 },
{'^' , "^", 1, 6 },
{'(' , "(", 1, 0 },
{')' , ")", 1, 99},
{'S' , "SIN(", 4, 0 },
{'C' , "COS(", 4, 0 },
{'A' , "ABS(", 4, 0 },
{'L' , "LN(", 3, 0 },
{'E' , "EXP(", 4, 0 },
{'t' , "ATAN(", 5, 0 },
{'s' , "SQRT(", 5, 0 },
{'c' , "CEIL(", 5, 0 },
{'f' , "FLOOR(", 6, 0 },
{'r' , "ROUND(", 6, 0 },
{'\0', NULL, 0, 0 }
};
static char op_stack [256]; /* Operator stack */
static double arg_stack[256]; /* Argument stack */
static char token [256]; /* Token buffer */
static int op_sptr; /* op_stack pointer */
static int arg_sptr; /* arg_stack pointer */
static int parens; /* Nesting level */
static int state; /* 0 = Awaiting expression
1 = Awaiting operator
*/
const double Pi = 3.14159265358979323846;
static int do_op(void);
static int do_paren(void);
static void push_op(char);
static void push_arg(double);
static int pop_arg(double *);
static int pop_op(int *);
static char *get_exp(char *);
static struct operator *get_op(char *);
static int getprec(char);
static int getTOSprec(void);
static char *rmallws(char *);
static double round(double x)
{
return(x > 0.0 ? floor(x+0.5) : ceil(x-0.5));
}
/************************************************************************/
/* */
/* evaluate() */
/* */
/* Evaluates an ASCII mathematical expression. */
/* */
/* Arguments: 1 - String to evaluate */
/* 2 - Storage to receive double result */
/* */
/* Returns: Success_ if successful */
/* Error_ if syntax error */
/* R_ERROR if runtime error */
/* */
/* Side effects: Removes all whitespace from the string and converts */
/* it to U.C. */
/* */
/************************************************************************/
int evaluate(char *line, double *val)
{
double arg;
char *ptr = line, *str, *endptr;
int ercode;
struct operator *op;
strupr(line);
rmallws(line);
state = op_sptr = arg_sptr = parens = 0;
while (*ptr)
{
switch (state)
{
case 0:
if (((void *)0) != (str = get_exp(ptr)))
{
if (((void *)0) != (op = get_op(str)) &&
strlen(str) == op->taglen)
{
push_op(op->token);
ptr += op->taglen;
break;
}
if (Success_ == strcmp(str, "-"))
{
push_op(*str);
++ptr;
break;
}
if (Success_ == strcmp(str, "PI"))
push_arg(Pi);
else
{
if (0.0 == (arg = strtod(str, &endptr)) &&
((void *)0) == strchr(str, '0'))
{
return Error_;
}
push_arg(arg);
}
ptr += strlen(str);
}
else return Error_;
state = 1;
break;
case 1:
if (((void *)0) != (op = get_op(ptr)))
{
if (')' == *ptr)
{
if (Success_ > (ercode = do_paren()))
return ercode;
}
else
{
while (op_sptr &&
op->precedence <= getTOSprec())
{
do_op();
}
push_op(op->token);
state = 0;
}
ptr += op->taglen;
}
else return Error_;
break;
}
}
while (1 < arg_sptr)
{
if (Success_ > (ercode = do_op()))
return ercode;
}
if (!op_sptr)
return pop_arg(val);
else return Error_;
}
/*
** Evaluate stacked arguments and operands
*/
static int do_op(void)
{
double arg1, arg2;
int op;
if (Error_ == pop_op(&op))
return Error_;
pop_arg(&arg1);
pop_arg(&arg2);
switch (op)
{
case '+':
push_arg(arg2 + arg1);
break;
case '-':
push_arg(arg2 - arg1);
break;
case '*':
push_arg(arg2 * arg1);
break;
case '/':
if (0.0 == arg1)
return -2;
push_arg(arg2 / arg1);
break;
case '\\':
case '%' :
if (0.0 == arg1)
return -2;
push_arg(fmod(arg2, arg1));
break;
case '^':
push_arg(pow(arg2, arg1));
break;
case 't':
++arg_sptr;
push_arg(atan(arg1));
break;
case 'S':
++arg_sptr;
push_arg(sin(arg1));
break;
case 's':
if (0.0 > arg2)
return -2;
++arg_sptr;
push_arg(sqrt(arg1));
break;
case 'C':
++arg_sptr;
push_arg(cos(arg1));
break;
case 'A':
++arg_sptr;
push_arg(fabs(arg1));
break;
case 'L':
if (0.0 < arg1)
{
++arg_sptr;
push_arg(log(arg1));
break;
}
else return -2;
case 'E':
++arg_sptr;
push_arg(exp(arg1));
break;
case 'c':
++arg_sptr;
push_arg(ceil(arg1));
break;
case 'f':
++arg_sptr;
push_arg(floor(arg1));
break;
case 'r':
++arg_sptr;
push_arg(round(arg1));
break;
case '(':
arg_sptr += 2;
break;
default:
return Error_;
}
if (1 > arg_sptr)
return Error_;
else return op;
}
/*
** Evaluate one level
*/
static int do_paren(void)
{
int op;
if (1 > parens--)
return Error_;
do
{
if (Success_ > (op = do_op()))
break;
} while (getprec((char)op));
return op;
}
/*
** Stack operations
*/
static void push_op(char op)
{
if (!getprec(op))
++parens;
op_stack[op_sptr++] = op;
}
static void push_arg(double arg)
{
arg_stack[arg_sptr++] = arg;
}
static int pop_arg(double *arg)
{
*arg = arg_stack[--arg_sptr];
if (0 > arg_sptr)
return Error_;
else return Success_;
}
static int pop_op(int *op)
{
if (!op_sptr)
return Error_;
*op = op_stack[--op_sptr];
return Success_;
}
/*
** Get an expression
*/
static char * get_exp(char *str)
{
char *ptr = str, *tptr = token;
struct operator *op;
if (Success_ == strncmp(str, "PI", 2))
return strcpy(token, "PI");
while (*ptr)
{
if (((void *)0) != (op = get_op(ptr)))
{
if ('-' == *ptr)
{
if (str != ptr && 'E' != ptr[-1])
break;
if (str == ptr && !isdigit(ptr[1]) && '.' != ptr[1])
{
push_arg(0.0);
strcpy(token, op->tag);
return token;
}
}
else if (str == ptr)
{
strcpy(token, op->tag);
return token;
}
else break;
}
*tptr++ = *ptr++;
}
*tptr = '\0';
return token;
}
/*
** Get an operator
*/
static struct operator * get_op(char *str)
{
struct operator *op;
for (op = verbs; op->token; ++op)
{
if (Success_ == strncmp(str, op->tag, op->taglen))
return op;
}
return ((void *)0);
}
/*
** Get precedence of a token
*/
static int getprec(char token)
{
struct operator *op;
for (op = verbs; op->token; ++op)
{
if (token == op->token)
break;
}
if (op->token)
return op->precedence;
else return 0;
}
/*
** Get precedence of TOS token
*/
static int getTOSprec(void)
{
if (!op_sptr)
return 0;
return getprec(op_stack[op_sptr - 1]);
}
/*
** remove all whitespace from a string
*/
static char *rmallws(char *str)
{
char *obuf, *nbuf;
if (str)
{
for (obuf = str, nbuf = str; *obuf; ++obuf)
{
if (!isspace(*obuf))
*nbuf++ = *obuf;
}
*nbuf = '\0';
}
return str;
}
int main(int argc, char *argv[])
{
int retval;
double val;
printf("evaluate(%s) ", argv[1]);
printf("returned %d\n", retval = evaluate(argv[1], &val));
if (0 == retval)
printf("val = %f\n", val);
return 0;
}
/*************************************************************************/
Gru�
Hermann
--
>
Re: a+(b*c) in Baum darstellen (Algorithmus)
Author: Jelle Maybach
Date: Wed, 16 Oct 2002 17:26
Date: Wed, 16 Oct 2002 17:26
23 lines
2361 bytes
2361 bytes
Am Wed, 16 Oct 2002 01:21:17 +0200 schrieb Hermann Kremer: /*************************************************************************/ > /* > */ /* EVALUATE.C - A simple mathematical expression evaluator in C > */ /* > */ /* operators supported: Operator Precedence [usw.] Was f�r eine aparte Formatierung. H�bsch. Du wei�t schon, dass man mit /* ...*/ ohne weiteres mehr als eine Zeile Kommentar klammern kann? ;-) Vielleicht noch etwas zur Sache, bevor ich wegen solcher Kommentare Schl�ge bekomme: B. Stroustrup hat als Einf�hrung in C++ soweit ich mich erinnere (ist schon etwas her...) einen Taschenrechner entwickelt, der einfache Ausdr�cke auswerten kann. Macht vielleicht nix anderes, zeigt aber, wie man so etwas elegant in C++ l�sen kann. Au�erdem wird's ausf�hrlicher erkl�rt, so dass man "das n�chste mal" selbst drauf kommen kann. Jelle
Re: a+(b*c) in Baum darstellen (Algorithmus)
Author: Hermann Kremer
Date: Wed, 16 Oct 2002 21:53
Date: Wed, 16 Oct 2002 21:53
34 lines
2944 bytes
2944 bytes
Jelle Maybach schrieb in Nachricht <3dada270$1@news.piro.net>... >Am Wed, 16 Oct 2002 01:21:17 +0200 schrieb Hermann Kremer: > > /*************************************************************************/ >> /* >> */ /* EVALUATE.C - A simple mathematical expression evaluator in C >> */ /* >> */ /* operators supported: Operator Precedence >[usw.] > >Was f�r eine aparte Formatierung. H�bsch. Du wei�t schon, dass man mit >/* ...*/ ohne weiteres mehr als eine Zeile Kommentar klammern kann? Yep, wei� ich ... der Code ist nicht von mir ... ;-) >Vielleicht noch etwas zur Sache, bevor ich wegen solcher Kommentare >Schl�ge bekomme: B. Stroustrup hat als Einf�hrung in C++ soweit ich mich >erinnere (ist schon etwas her...) einen Taschenrechner entwickelt, der >einfache Ausdr�cke auswerten kann. Macht vielleicht nix anderes, zeigt >aber, wie man so etwas elegant in C++ l�sen kann. Au�erdem wird's >ausf�hrlicher erkl�rt, so dass man "das n�chste mal" selbst drauf >kommen kann. Hmm, kann ich mich im Augenblick nicht dran erinnern - aber im yacc-Manual von 4.3BSD ist als Beispiel ein in yacc geschriebener und gut dokumentierter Infix-Parser ... der sollte auch mit bison klappern ... Gru� Hermann -- > >Jelle
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads