program Tree5;

{$APPTYPE CONSOLE}

uses SysUtils;

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

var
  Root  : PTree;
  Shiki : String;

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

  procedure Level3Shiki(var Ptr : PTree); forward;

  procedure Level1Shiki(var Ptr : PTree);
            {Shiki の Nth 文字目から始まるレベル１の式を変換して Ptr に指させる}
            {レベル１の式とは 変数または( )でくくられた式                      }
    begin
      case Shiki[Nth] of
        '(' : begin
                Inc(Nth);                      // '('の次を見る
                Level3Shiki(Ptr);              // レベル３の式
                {Shiki[Nth]は')'のはず}
                Inc(Nth);                      // ')'の次を見る
              end;
        else  begin
                {Shiki[Nth]は変数のはず}
                New(Ptr);                      // 空の節を新しく作る
                Ptr^.Left   := Nil;
                Ptr^.Right  := Nil;
                Ptr^.Symbol := Shiki[Nth];     // Symbol に変数を入れる
                Inc(Nth);                      // 変数の次を見る
              end;
      end;
    end; {Level1Shiki}

  procedure Level2Shiki(var Ptr : PTree);
            {Shiki の Nth 文字目から始まるレベル２の式を変換して Ptr に指させる}
            {レベル２の式とは レベル１の式を * / で結んだ式                    }
    var
      P : PTree;
    begin
      Level1Shiki(Ptr);                        // レベル１の式
      while (Nth <= Length(Shiki)) and
            (Shiki[Nth] in ['*','/']) do       //
        begin
          P := Ptr;                            // 仮に保存
          New(Ptr);                            // 空の節を新しく作る
          Ptr^.Left   := P;                    // 今までの式が左になる
          Ptr^.Symbol := Shiki[Nth];           // Symbol に演算子を入れる
          Inc(Nth);                            // 演算子の次を見る
          Level1Shiki(Ptr^.Right);             // レベル１の式が右に来る
        end;
    end; {Level2Shiki}

  procedure Level3Shiki(var Ptr : PTree);
            {Shiki の Nth 文字目から始まるレベル３の式を変換して Ptr に指させる}
            {レベル３の式とは レベル２の式を + - で結んだ式                    }
    var
      P : PTree;
    begin
      Level2Shiki(Ptr);                        // レベル２の式
      while (Nth <= Length(Shiki)) and
            (Shiki[Nth] in ['+','-']) do       //
        begin
          P := Ptr;                            // 仮に保存
          New(Ptr);                            // 空の節を新しく作る
          Ptr^.Left   := P;                    // 今までの式が左になる
          Ptr^.Symbol := Shiki[Nth];           // Symbol に演算子を入れる
          Inc(Nth);                            // 演算子の次を見る
          Level2Shiki(Ptr^.Right);             // レベル２の式が右に来る
        end;
    end; {Level3Shiki}

  begin{ChuuchiShikiToTree}
    Nth := 1;                                  // １文字目を見る
    Level3Shiki(Root)                          // １文字目から始まるレベル２の式
  end; {ChuuchiShikiToTree}

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);
    ChuuchiShikiToTree;
    WriteLn('木の形 :');
    TreeWoKaku(Root,'R');
    Write('前置記法 : ');
    ZenchiKihou(Root);
    WriteLn;
    Write('中置記法 : ');
    ChuuchiKihou(Root);
    WriteLn;
    Write('後置記法 : ');
    KouchiKihou(Root);
    WriteLn;
    Kaihou(Root);
  until Shiki = 'z';
end.