datatype ('a, 'b, 'c) baum = Blt of 'a
                           | Knt1 of 'b * ('a, 'b, 'c) baum
                           | Knt2 of ('a, 'b, 'c) baum * 'c * ('a, 'b, 'c) baum;

exception ungueltig of string


fun lese istA a istB b istC c toString  nil    =
        raise ungueltig("Baum nicht abgeschlossen")
  | lese istA a istB b istC c toString (x::xs) =
        if istA(x) then (Blt(a(x)), xs)
        else if istB(x) then
          let
            val (baum,rest) = lese istA a istB b istC c toString xs;
          in
            (Knt1(b(x), baum), rest)
          end
        else if istC(x) then
          let
            val (linkerBaum, linkerRest)   =
                lese istA a istB b istC c toString xs;
            val (rechterBaum, rechterRest) =
                lese istA a istB b istC c toString linkerRest;
          in
            (Knt2(linkerBaum, c(x), rechterBaum), rechterRest)
          end
        else raise ungueltig("ungueltiges Zeichen: "^toString(x));

fun leereListe nil = true
  | leereListe _   = false;

fun erzeugeBaum istA a istB b istC c toString L =
  let
    val (baum,rest) = lese istA a istB b istC c toString L;
  in
    if leereListe(rest)
    then baum
    else raise ungueltig("Baum abgeschlossen, Eingabe nicht leer")
  end;


fun istKonstante x = isSome(Int.fromString(x));

fun konstante x = valOf(Int.fromString(x));


fun istUnaer "~"    = true
  | istUnaer "quad" = true
  | istUnaer _      = false;

fun unaer "~"    = op ~
  | unaer "quad" = fn x => x*x;


fun istBinaer "-" = true
  | istBinaer "+" = true
  | istBinaer "*" = true
  | istBinaer "/" = true
  | istBinaer "%" = true
  | istBinaer _   = false;

fun binaer "-" = op -
  | binaer "+" = op +
  | binaer "*" = op *
  | binaer "/" = op div
  | binaer "%" = op mod;