# Verwandelt vollständig (!) geklammerten Term in TEX-Code mit
# der Darstellung des Rechenbaumes. Jede Eingabezeile wird in
# einen Block überführt.
#
# Parameter:
#    include - Wenn 0, vollständige TEX-Datei erstellen
#    solve   - Wenn 0, leere Felder ausgeben, sonst Lösung.
#
# Stephan Höhrmann & Xenia Rendtel, 28.12.2003

function tilt()
{
  printf("Falsch geklammerte Formel!\n") > "/dev/stderr";
  exit;
}

function atom(formel)
{
  return(!match(formel,"[\\(\\)]"));
}

function left(formel,  res,depth,pos)
{
  if (!match(formel,"^\\(.*\\)$")) tilt();
  res=substr(formel,2,length(formel)-2);
  depth=0;
  pos=1;
  while (!((depth==0) && (match(substr(res,pos,1),"[\\-\\+\\*:]")))) {
    if (substr(res,pos,1)=="(") depth++;
    if (substr(res,pos,1)==")") depth--;
    if ((depth<0) || (pos>length(res))) tilt();
    pos++;
  }
  return substr(res,1,pos-1);
}

function op(formel)
{
  return substr(formel,length(left(formel))+2,1);
}

function right(formel)
{
  return substr(formel,length(left(formel))+3,
		length(formel)-length(left(formel))-3);
}

function depth(formel,   dl,dr)
{
  if (atom(formel)) return 0;
  dl=depth(left(formel));
  dr=depth(right(formel));
  return (dl<dr)?(dr+1):(dl+1);
}

function width(formel)
{
  if (atom(formel)) return 1;
  return width(left(formel))+1+width(right(formel));
}

function eval(formel)
{
  if (atom(formel)) return formel;
  if (op(formel)=="+") return eval(left(formel))+eval(right(formel));
  if (op(formel)=="-") return eval(left(formel))-eval(right(formel));
  if (op(formel)=="*") return eval(left(formel))*eval(right(formel));
  if (op(formel)==":") return eval(left(formel))/eval(right(formel));
  return "?";
}

function arrow(dx,dy,  res)
{
  res="\\ar@{-}";
  if (dy*dy>1) res=res sprintf(" '[%i,0]+0",dy-1);
  res=res sprintf(" `d[%i,%i] [%i,%i]",dy,dx,dy,dx);
  return res;
}

function layout(formel,x,  froml,fromr,mid,y,dx,dy)
{
  y=depth(formel);
  if (atom(formel)) {
    grid[x,0]=formel;
    return x;
  } else {
    mid=x+width(left(formel));
    froml=layout(left(formel),x);
    fromr=layout(right(formel),x+width(left(formel))+1);
    grid[mid,y*2-1]=sprintf("*+[o][F]{%s}",
			    (op(formel)!="*")?op(formel):"\\txt{$\\cdot$}");
    grid[mid,y*2]=sprintf("*+%s{%s}",(solve)?"":"[F]",(solve)?eval(formel):"\\makebox(30,10){}");

    grid[froml,depth(left(formel))*2]=grid[froml,depth(left(formel))*2] arrow(mid-froml,2*(depth(formel)-depth(left(formel)))-1);
    grid[fromr,depth(right(formel))*2]=grid[fromr,depth(right(formel))*2] arrow(mid-fromr,2*(depth(formel)-depth(right(formel)))-1);
    grid[mid,2*y-1]=grid[mid,2*y-1]sprintf("\\ar@{-}[d]");
    return mid;
  }
}

BEGIN {
  if (!include) {
    printf("\\documentclass{article}\n");
    printf("\\usepackage[all]{xy}\n");
    printf("\\begin{document}\n");
    printf("\\thispagestyle{empty}\n\n");
  }
}
/./ {
  gsub(" ","");
  delete grid;
  layout($0,0);

  printf("%% %s\n\n",$0);
  printf("\\scalebox{0.8}{ \n");
  printf("\\centerline{");
  printf("\\xymatrix@R=5pt{\n");
  for (y=0; y<=depth($0)*2; y++) {
    printf("  ");
    len=2;
    for (x=0; x<=width($0); x++) {
      len+=length(grid[x,y]);
      if (len>=74) {
	printf("\n    ");
	len=4;
      }
      printf("%s",grid[x,y]);
      if (x<width($0)) {
	printf("&"); 
	len++;
      } else {
	if (y<depth($0)*2) printf(" \\\\");
	printf("\n");
	len=0;
      }
    }
  }
  printf("}\n");
  printf("}\n");
  printf("}\n\n");
}
END {
  if (!include) {
    printf("\\end{document}\n");
  }
}