a+(b*c) in Baum darstellen (Algorithmus)
Alex Scherbel
Kennt jemand einen Algorithmus, der einen Infix-Ausdruck in einem Baum
darstellen kann?
Also zum Beispiel:
a+(b*c) => +
/ \
a *
/ \
b c
Gruß Andy
Hermann Kremer
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
--
>
Jelle Maybach
/*************************************************************************/
> /*
> */ /* 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
Hermann Kremer
>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