🚀 go-pugleaf

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


>