ここでは括弧の位置を覚えておくために，整数のスタックを用いる。スタック操作には，Push，POPとスタックが空かどうかを調べるempty及びスタックの一番上のデータの値を返すpeekが使えるものとする。
スタック操作以外に，関数nextch，kindを使うことができる。nextchはファイルから次の1文字を読み込む関数で，入力文字を1文字読み込んで返すと同時に，読み込んだ文字が何行目の何文字目かを，変数lineとposに設定する。ただし，ファイルの終わりでは変数EOFを“真”に設定し，空白を返す。変数EOFの初期値は“偽”である。また，kindは1引数の関数で，文字を引数で受け取り，文字が括弧かどうかを整数値で返す。その関数値は，次のとおりである。 |
|
| kind(c)= |
0 cが括弧以外の文字 |
|
1 cが開き括弧 |
|
2 cが閉じ括弧 |
|
|
| この考察に基づいて書いたアルゴリズムは次のようになった｡ |
|
〔アルゴリズム1]
|
|
|
|
スタックを空に初期化
ch←nextch( )
While(not EOF)
k←kind(ch)
|
| if（ |
|
） |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
elseif（ |
|
） |
|
|
|
|
if( |
|
） |
|
|
|
|
dummy←POP( ) |
|
|
|
dummy←POP( ) |
|
|
else |
|
|
|
|
|
メッセージを表示 (Ａ) |
|
|
|
何行目(line)と何文字目(pos)を表示 |
|
|
endif |
|
|
endif |
|
|
|
ch←nextch( ) |
|
|
endwhile
if(not empty( ) )
メッセージを表示 (Ｂ)
While(not empty( ))
dummy←POP( )
L←POP( )
P←POP( )
何行目(L)と何文字目(P)を表示
endwhile
endif
|
|
|
|
|
| |
|
括弧が2種類以上あるときには,括弧の種類ごとに対応を調べる必要がある｡括弧は(・・・[・・・](・・・))のように完全な入れ子構造になっていることが要求されており,
(・・・[・・・)]のようなものは許されない。
ここでは,3種類の括弧() {} [] を対象とするようにアルゴリズム1を修正した｡
この場合はスタックに括弧の種類,行番号及び文字位置の三つのデータを積む必要がある｡まず,括弧の種類を識別するために,括弧を表のとおりにコード化する｡
kindは,括弧の場合には表のコードを,括弧以外の文字の場合には0を関数値として返すように修正した｡
|
| |
|
|
| |
|
閉じ括弧が出てきた場合に,異なる種類の開き括弧がスタックの一番上にあったときは,この閉じ括弧に対応する開き括弧がないというメッセージとこの閉じ括弧の位置を表示して,スタック上の開き括弧はそのままにして処理を続けることにする｡
これに従うと,アルゴリズムは次のようになる｡
|
| |
|
〔アルゴリズム2〕
|
|
|
|
スタックを空に初期化
ch←nextch( )
While(not EOF)
k←kind(ch)
if(k>0)
|
|
|
| スタックに情報を積む |
|
|
|
dummy←POP( )
dummy←POP( )
dummy←POP( )
else
メッセージを表示 (Ａ)
何行目(line)と何文字目(pos)を表示
endif
endif
ch←nextch( )
endwhile
if(not empty( ))
メッセージを表示 (Ｂ)
while(not empty( ))
dummy←POP( )
L←POP( )
P←POP( )
何行目(L)と何文字目(p)を表示
endwhile
endif
|
|
|
|
| |
| 設問１ |
| アルゴリズム１の |
|
〜 |
|
に入れる適切な字句を答えよ。 |
|
| 設問2 |
アルゴリズム1,2の(A),(B)の位置で表示するメッセージを答えよ｡ |
| 設問3 |
| アルゴリズム２の |
|
〜 |
|
で行う処理内容を解答群から選び,記号で答えよ｡また,その処理内容を具体的な式で示せ｡ |
|
|
必要なら余りを求める演算には“%"を使うこと｡条件式は左から順に評価を行い,途中で値が確定した場合は,残りの評価は行わないものとする｡ |
| |
|
|
| 解答群 |
|
(a) kが括弧以外のコードか
(b) kが開き括弧のコードか
(c) kが閉じ括弧のコードか
(d) スタックの一番上のデータがkに対応する開き括弧か
(e) スタックの一番上のデータがkに対応する閉じ括弧か
(f) スタックが空か
(g) スタックが空でないか
|
|