program Tree3;

{$APPTYPE CONSOLE}

uses SysUtils;

type
  PTree = ^TTree;
  TTree = record
            Left   : PTree;    // 左の部分式
            Symbol : Char;     // 記号（変数または演算子）
            Right  : PTree;    // 右の部分式
          end;

var
  Root  : PTree;
  Shiki : String;

procedure ZenchiShikiToTree;
          {前置記法の Shiki を Tree に変換して Root に指させる}
  var
    Nth : Integer;        // 今 Shiki の何文字目を見ているかを示す

  procedure BubunShiki(var Ptr : PTree);  {recursive}
            {Shiki の Nth 文字目から始まる部分式を変換して Ptr に指させる}
    begin
      New(Ptr);                                // 空の節を新しく作る
      Ptr^.Symbol := ' ';
      Ptr^.Left   := Nil;
      Ptr^.Right  := Nil;
      case Shiki[Nth] of
        '+','-','*','/' :
              begin
                Ptr^.Symbol := Shiki[Nth];     // Symbol に演算子を入れる
                Inc(Nth);
                BubunShiki(Ptr^.Left);         // 左の部分式を変換
                BubunShiki(Ptr^.Right);        // 右の部分式を変換
              end;
        else  begin
                {Shiki[Nth]は変数のはず}
                Ptr^.Symbol := Shiki[Nth];     // Symbol に変数を入れる
                Inc(Nth);                      // 変数の次を見る
              end;
      end;
    end; {BubunShiki}

  begin{ZenchiShikiToTree}
    Nth := 1;                                  // １文字目を見る
    BubunShiki(Root)                           // １文字目から始まる部分式
                                               // すなわち式
  end; {ZenchiShikiToTree}

procedure Kaihou(P : PTree);
          {Tree に使った領域を解放する(システムに戻す)}
  begin
    if P <> Nil
      then begin
             Kaihou(P^.Left);                  // 左の部分木を解放
             Kaihou(P^.Right);                 // 右の部分木を解放
             Dispose(P);                       // P が指している節をシステムに戻す
           end;
  end; {Kaihou}

procedure TreeWoKaku(P : PTree; Eda : String);
          {木を書く}

  procedure EdaWoKaku(Eda : String);
            {枝を書く}
    var
      Depth : Integer;
      K : Integer;
    begin
      Depth := Length(Eda);
      for K := 2 to Depth do
        if Eda[K-1] = Eda[K]
          then Write('　　')
          else Write('　│');
      case Eda[Depth] of
        'L' : Write('　┌');
        'R' : Write('　└');
      end;
    end; {EdaWoKaku}

  begin
    if P = Nil                                // 枝の先端か？
      then begin                              //   yes
             {
             EdaWoKaku(Eda);                  //     途中の枝を書く
             WriteLn;                         //
             }
           end
      else begin                              //   yes
             TreeWoKaku(P^.Left,Eda+'L');     //     左の部分木を書く
             EdaWoKaku(Eda);                  //     途中の枝を書く
             Write(P^.Symbol,' ');            //     記号を書く
             if P^.Left <> Nil
               then WriteLn('┤')
               else WriteLn;
             TreeWoKaku(P^.Right,Eda+'R');    //     右の部分木を書く
           end;
  end; {TreeWoKaku}

procedure ZenchiKihou(P : PTree);
          {前置記法で書く}
  begin
    if P <> Nil
      then begin
             Write(P^.Symbol);
             ZenchiKihou(P^.Left);
             ZenchiKihou(P^.Right);
           end;
  end; {ZenchiKihou}

procedure ChuuchiKihou(P : PTree);
          {中置記法で書く}
  begin
    if P^.Left <> Nil
      then if (P^.Symbol in ['*','/']) and (P^.Left^.Symbol in ['+','-'])
             then begin
                    Write('(');
                    ChuuchiKihou(P^.Left);
                    Write(')');
                  end
             else ChuuchiKihou(P^.Left);
    Write(P^.Symbol);
    if P^.Right <> Nil
      then if ([P^.Symbol,P^.Right^.Symbol] <= ['*','/']) or (P^.Right^.Symbol in ['+','-'])
             then begin
                    Write('(');
                    ChuuchiKihou(P^.Right);
                    Write(')');
                  end
             else ChuuchiKihou(P^.Right);
  end; {ChuuchiKihou}

procedure KouchiKihou(P : PTree);
          {後置記法で書く}
  begin
    if P <> Nil
      then begin
             KouchiKihou(P^.Left);
             KouchiKihou(P^.Right);
             Write(P^.Symbol);
           end;
  end; {KouchiKihou}

begin {Main}
  WriteLn('前置記法の式を入れてください');
  WriteLn('エラーチェックをしないので正しい式を入れてください');
  WriteLn('z だけを入れると終わります');
  repeat
    WriteLn;
    Write('式 ? ');
    ReadLn(Shiki);
    ZenchiShikiToTree;
    WriteLn('木の形 :');
    TreeWoKaku(Root,'R');
    Write('前置記法 : ');
    ZenchiKihou(Root);
    WriteLn;
    Write('中置記法 : ');
    ChuuchiKihou(Root);
    WriteLn;
    Write('後置記法 : ');
    KouchiKihou(Root);
    WriteLn;
    Kaihou(Root);
  until Shiki = 'z';
end.