プログラミング学習 DAY 3

データ構造の続きを説明します。
HLPのプログラミングを正確に、バグが少なくなるようにいろんなデータ構造が発案されています。
以下はその中でも代表的なものを紹介します。

■Stack（スタック）

スタックというデータ構造を考えてみましょう。
満員電車で、扉のしまる寸前に飛び込んだ人は、次の駅で扉が開いたときには真っ先に外に出なければ
なりません。最後に入れたものを最初に出す、（LIFO）という構造をスタックと呼びます。
PASCALのシンタックスで、ブロックの始まりと終わりの記号として
begin end
を使いますが、endを忘れていたりすることがよくあります。
PHPですと、カッコ　｛　｝でくくる必要があります。
一行のみのデータを読み込んで、カッコ｛　｝のバランスをチェックするプログラムを作ります。

日常語によるロジックの説明は下記の通り。

画面入力より1行のデータを読み込む。

読み込んだ文字列を最初から順番に取り出す。
もし、取り出した文字が’{‘ があれば、
スタックに’{‘をPush

もし、’}‘ があれば、
スタックをPopして文字を取り出す
スタックが空であれば、エラー(no Balanced)
最後に
	スタックが空ではなく、残っていればエラー（no Balanced)

以下のプログラムはPOPとPUSHとIsBalancedに分けて、それぞれをコンパクトにしています。

program Kakko_1;
{$mode objfpc}{$H+}


uses
  SysUtils;

type
  TCharStack = array of Char;

procedure Push(var st: TCharStack; c: Char);
begin
  SetLength(st, Length(st) + 1);
  st[High(st)] := c;
end;

function Pop(var st: TCharStack): Char;
begin
  if Length(st) = 0 then
    Exit(#0);
  Result := st[High(st)];
  SetLength(st, Length(st) - 1);
end;



function IsBalanced(const s: string): Boolean;
var
  st: TCharStack;
  i: Integer;
  c, t: Char;
begin
  st := nil;
  for i := 1 to Length(s) do
  begin
    c := s[i];
    if (c = '{') then
      Push(st, c)
    else if  (c = '}') then
    begin
      t := Pop(st);
      if (t = #0)  then
        Exit(False);
    end;
  end;
//スタックが空であれば、結果がTrue
  Result := Length(st) = 0;
end;

var
  line: string;
begin
  
  Write('Input> ');

  if Eof then Exit; 
  ReadLn(line);
  if IsBalanced(line) then
    WriteLn('Balanced')
  else
    WriteLn('Not balanced');
end.

これを、Pythonでコードを書いてみます。
List構造を使った簡単なプログラムです。
こちらは複数行にまたがったカッコのペアのバランスをチェックします。

まず、StackのPopとPushを表現する関数を作ります。
次に、CSVファイルを各行ごとに読み込んでSpaceで区切られるStringをListに入れる。
そのListから、要素を順番に取り出して、
’{‘ があれば、Push
‘}’があれば Pop
Popの時にStackがEmptyであれば、エラーで　”}”が多すぎる

すべての行が読み終わったときに、Stackに ‘{‘が残っていればエラー　”{“が多すぎる
StackがEmptyであれば、Balanced

Python Program
#Use Stack.append, Stack.pop
import csv
import os
def stack_push(stack,item):
	stack.append(item)
	print ("after pushstack",stack)
def stack_pop(stack):
	if (len(stack)==0):
		print ("empty")
		print ("error:less }")
	else:
		x=stack.pop(len(stack)-1)
		print ("popped ",x)
# main
with open('stackdata.csv',encoding='utf-8') as h:
    
    reader = csv.reader(h,delimiter=' ')
    st = [row for row in reader]
gstack=[]
for i in range(len(st)):
	
	line=st[i]
	
	for k in range(len(line)):
		if (line[k]=='{'):

			stack_push(gstack,'{')
		elif (line[k]=='}'):

			x=stack_pop(gstack)
		else:
			print ("no")
print("finally ",gstack)
if (len(gstack)==0):
	print ("balanced")
else:
	print ("Error:Unbalanced more }")
			

■QUEUE（キュー）

次は、キュー（Queue）というデータ構造を考えます。
これは、スタックと違って、順番に入ったものは順番に出ていく。
FIFOです。
レストランで順番を待っているとき、呼ばれるのがこのFIFOです。
QUEUEの中に、予約の入っている人の名前を入れる。
席が空いたときは順番に名前を呼び出す。

プログラムの設計では、
データ構造として、
ノードには、名前を入れるValueと
次のノードへのポインタを入れている。
QUEUEはオブジェクトを使って指定する。
頭と尾のポインタとカウントを持つ。
手続き（Procedure)として３つ、初期値設定、キューに入れる、キューを開放する。
関数（Function）として次の３つ。
キューから取り出す、キューが空かどうかの判定、キューの中にある数。

program junbanmachi;
{$mode objfpc}{$H+}

uses
  SysUtils;

type
  PNode = ^TNode;
  TNode = record
    Value: string;
    Next: PNode;
  end;

  TLinkedQueue = object
  private
    head, tail: PNode;
    cnt: Integer;
  public
    procedure Init;
    procedure Enqueue(const s: string);
    function Dequeue: string;
    function IsEmpty: Boolean;
    function Count: Integer;
  end;

procedure TLinkedQueue.Init;
begin
  head := nil;
  tail := nil;
  cnt := 0;
end;


procedure TLinkedQueue.Enqueue(const s: string);
var
  p: PNode;
begin
  New(p);
  p^.Value := s;
  p^.Next := nil;
  if tail = nil then
  begin
    head := p;
    tail := p;
  end
  else
  begin
    tail^.Next := p;
    tail := p;
  end;
  Inc(cnt);
end;
procedure TLinkedQueue.Done;
var
  p: PNode;
begin
  while head <> nil do
  begin
    p := head;
    head := head^.Next;
    Dispose(p);
  end;
  tail := nil;
  cnt := 0;
end;

function TLinkedQueue.Dequeue: string;
var
  p: PNode;
begin
  if head = nil then
    raise Exception.Create('Dequeue from empty queue');
  p := head;
  Result := p^.Value;
  head := head^.Next;
  if head = nil then
    tail := nil;
  Dispose(p);
  Dec(cnt);
  if head = nil then tail := nil;
end;


function TLinkedQueue.IsEmpty: Boolean;
begin
  Result := head = nil;
end;

function TLinkedQueue.Count: Integer;
begin
  Result := cnt;
end;

// テスト部分　キューに3名の名前を入れます
var
  q: TLinkedQueue;
  s: string;
begin
  q.Init;
  try
    q.Enqueue('masa');
    q.Enqueue('ogawa');
    q.Enqueue('yoshida');
    WriteLn('Count=', q.Count);
//キューから順番に取り出す
    while not q.IsEmpty do
    begin
      s := q.Dequeue;
      WriteLn('Dequeued: ', s);
    end;
  finally
    q.Done;
  end;
end.

■LinkList（単方向リスト）

次は、単方向のリンクリストです。

type PNode = ^TNode;
     TNode = record
       Value: Integer;
       Next: PNode;
     end;
procedure AddFront(var head: PNode; v: Integer);
var 
  p: PNode;
begin
  New(p); p^.Value := v; p^.Next := head; head := p;
end;

双方向のLinkListを使って、次に、バイナリツリーを実装します。

■バイナリツリー

バイナリーツリーの構造は階層構造を表現するときによく使われます。
データーベースのIndexを作成したり、データを検索するときにツリーをトラバース
することで、検索時間を縮小できます。




右のリンクと左のリンクをノードに持ちます。
ツリーもノードに、右、左のノードへのリンクを入れます。
下のプログラムでは、ノードに整数を入れます。
ツリーを左からたどると数字の小から大の順に並んだ列が得られます。
これを使うと、数字列のソートが可能になります。


program BST;
{$mode objfpc}{$H+}
uses
  SysUtils;

type
  PBNode = ^TBNode;
  TBNode = record
    Key: Integer;
    Left, Right: PBNode;
  end;

procedure InsertNode(var root: PBNode; k: Integer);
begin
  if root = nil then
  begin
    New(root);
    root^.Key := k;
    root^.Left := nil;
    root^.Right := nil;
    Exit;
  end;
  if k < root^.Key then
    InsertNode(root^.Left, k)
  else if k > root^.Key then
    InsertNode(root^.Right, k);
  // duplicates: ignore
end;
procedure PrintInOrder(root: PBNode);
begin
  if root = nil then Exit;
  PrintInOrder(root^.Left);
  Write(root^.Key, ' ');
  PrintInOrder(root^.Right);
end;



//Main サンプルの数字列をBSTに入れる
var
  root: PBNode;
  keys: array[0..9] of Integer = (400,10,30,500,600,2,5,8,9,10);
  i: Integer;
begin
  root := nil;
  // insert keys into Tree
  for i := 0 to High(keys) do 
InsertNode(root, keys[i]);
 Write('InOrder: ');
 PrintInOrder(root);
  WriteLn;
  
 end.

■応用問題１

バイナリーツリーを使った例として、最小の数字を出す関数は以下のようになります。

左端にあるツリーの終端ノードに入っている数字です。

function BSTMin(root: PBNode): Integer;
begin
if root=nil then raise Exception.Create(‘empty’);
while root^.Left<>nil do root:=root^.Left;
Result := root^.Key;
end;

■応用問題２

与えられた数字がツリーの中にあるかどうかを判定する関数です。

function BSTContains(root: PBNode; k: Integer): Boolean;
begin
if root=nil then Exit(False);
if k=root^.Key then Exit(True);
if k<root^.Key then Result := BSTContains(root^.Left,k) else Result := BSTContains(root^.Right,k);
end;

小見出しを3つ以上入れると、自動で目次が作成されます。
この投稿のスラッグはprogramming3としてあります。次回からもprogramming#の形にするとわかりやすくてよいと思います。
カテゴリーはComputer Science、プログラミング学習を選んでください。（この投稿では選択済み）

著者：松尾正信
株式会社京都テキストラボ代表取締役