Šî–{ î•ñ u À2(4_23)

基 本 情 報 第 ２回
2013/4/23
情 報 、通 信 、制 御 に関 する理 論
例 題 １：逆 ポーランド記 法
後 置 表 記 法 (逆 ポーランド表 記 法 )では，例 えば，式 Y＝(A－B)×C を YAB
－C×＝ と表 現 する。
次 の式 を後 置 表 記 法 で表 現 したものはどれか。
Y＝(A＋B)×(C－(D÷E))

YAB＋C－DE÷×＝
ア

YAB＋CDE÷－×＝
YAB＋EDC÷－×＝
YBA＋CD－E÷×＝
イ
ウ
エ


例題２：状態遷移表
次 の表 は，文 字 列 を検 査 するための状 態 遷 移 表 である。検 査 では，初 期 状
態 を a とし，文 字 列 の検 査 中 に状 態 が e になれば不 合 格 とする。
解 答 群 で示 される文 字 列 のうち，不 合 格 となるものはどれか。ここで，文 字
列 は左 端 から検 査 し，解 答 群 中 の△は空 白 を表 す。
＋0010
－1
12.2
9.△




1
ア
イ
ウ
エ
例題３：BNF
次 の規 則 から生 成 することができる式 はどれか。




〔規 則 〕
＜式 ＞ ::＝＜変 数 ＞｜(＜式 ＞＋＜式 ＞)｜＜式 ＞＊＜式 ＞
＜変 数 ＞ ::＝A｜B｜C｜D
A＋(B＋C)＊D
ア
(A＋B)＋(C＋D)
イ
(A＋B)＊(C＋D)
ウ
(A＊B)＋(C＊D)
エ
2
解説１：逆 ポーランド表 記 法
スタック、キュー、逆ポーランド記法
キューとスタック
──┐
│
： │↓
│
├────┤
１１│データ５│
├────┤
１２│データ４│
├────┤
１３│データ３│
├────┤
１４│データ２│
├────┤
１５│データ１│
├────┤
： │
││
Push ──┐
┌─→ Pop
│
│
： │↓
││
├────┤
１１│データ５│
├────┤
１２│データ４│
├────┤
１３│データ３│
├────┤
１４│データ２│
├────┤
１５│データ１│
├────┤
： │
│
│
└─→
キュー
ＦＩＦＯ
スタック
ＬＩＦＯ
配列の特殊な構造に、キューとスタックがあります。
キューは、ＦＩＦＯ（First In First Out：先入れ先出し）方式で、待ち行列ともいいます。
プリンタへのスプールによる出力処理やデータを入力された順番通りに処理するとき
などに用いられます。
それに対して、スタックは、ＬＩＦＯ（Last In First Out：後入れ先出し）方式です。新しい
データを入れる（Push）と、それまでのデータが下に押し下げられ、取り出すとき（Pop）
ときは、１番上のデータが取り出され、２番目以降のデータが上に押し上げられます。
スタックの利用
コンピュータでは、スタックが広い分野で用いられています。
3

ＣＰＵでは、命令を実行するためのレジスタの一つとして、スタックポインタというレジスタを
用いています。

コンパイラが数式を命令に展開する技法の一つに「逆ポーランド記法」がありますが、これ
にはスタックが重要な役割を持っています（これに関しては後述します）。

再帰呼び出しを実現するには、スタックが用いられます。

複雑な探索問題や最適化問題では、分枝限定法がとられますが、その中間結果を記録す
る手段（バックトラッキング）として、スタックが用いられます。
逆ポーランド記法との関係
逆ポーランド記法
数学の一般的な記法での数式 Ａ＋Ｂ×Ｃ を計算するには、発生順序により「(Ａ＋Ｂ)×
Ｃ」とするのは誤りです。日本語では「ＡにＢにＣを×したものを＋する」ことになりますが、
その順に「ＡＢＣ×＋」と記述する記法を逆ポーランド記法といいます。
もう少し複雑な例にして、数式を逆ポーランド記法にする手順を説明します。
数式 Ａ＋Ｂ×（Ｃ＋Ｄ）＋Ｅ は、演算の優先順位を（ ）で明示すれば、
（（Ａ＋（Ｂ×（Ｃ＋Ｄ）））＋Ｅ）
になります。
最も深い（ ）から、数式を逆ポーランド記法に置き換えていきます。
（
（Ａ＋（Ｂ×（Ｃ＋Ｄ））
）＋Ｅ）
└─①─┘
ＣＤ＋
└───②───┘
ＢＣＤ＋×
└─────③─────┘
ＡＢＣＤ＋×＋
└─────④─────────┘
ＡＢＣＤ＋×＋Ｅ＋
となり、逆ポーランド記法の
ＡＢＣＤ＋×＋Ｅ＋
になります。
なお、これを木構造（演算木）を用いて表現することもできます。
練習問題
問題１： (Ａ＋Ｂ)×(Ｃ－Ｄ) → ＡＢ＋ＣＤ－×
問題２： Ａ／(Ｂ－Ｃ)＋Ｄ
4
→ ＡＢＣ－／Ｄ＋
スタックによる計算方法
数学での記法を逆ポーランド記法に変換すれば、スタックを利用して簡単に計算すること
ができます。
そのルールは、次の通りです。
逆ポーランド記法で記述した数式を左から順番に処理する。スタックは空である。
数値ならば、スタックに Push する
演算子ならば、
スタックの１番上の数値を Pop して、その数値をＸとする。
新しくスタックの１番上にきた数値をＹとして、ＹにＸを演算する。
その結果をＹに代入する。
数式がなくなったとき、スタックには唯一の数値が残っており、それが数式の結果であ
る。
このように、逆ポーランド記法では、＋×や（ ）などの優先順位を考慮する必要がなく、
式の解釈が簡単になり、スタック操作だけで行えるので、初期の電卓では逆ポーランド記
法の順に入力するものもありました。また、コンパイラで数式を解釈するときにも利用されて
います。
例題
「ＡＢＣ／－」を例にして説明します。
Step1：Ａを Push する。
Step2：Ｂを Push する。
Step3：Ｃを Push する。
Step4：／になった。Ｃが Pop され、スタックの最上段がＢになる。
最上段の値を Ｂ／Ｃ の計算結果に置き換える。
Step5：－になった。Ｂ／Ｃ が Pop され、スタックの最上段がＡになる。
最上段の値を Ａ－(Ｂ／Ｃ) の計算結果に置き換える。
数式がなくなったので、計算結果は Ａ－(Ｂ／Ｃ) となる。
スタックの状況は、次のようになります。
Step1
Step2
Step3
Step4
Step5
Ａ
Ｂ
Ｃ
／
－
┌───┬───┬───┬───┬──────┐
１ │ Ａ │ Ｂ │
Ｃ │Ｂ／Ｃ│Ａ－(Ｂ／Ｃ)│
└───┼───┼───┼───┼───┬──┘
２
│ Ａ │
Ｂ │ Ａ │
└───┼───┼───┘
３
│
Ａ │
└───┘
5
└ 計算結果
＜例 題 １の解 説 ＞
通 常 の式 を、逆 ポーランド表 記 法 で表 現 するための基 本 は、 A＋B を AB＋
で表 すことです。これと一 回 使 った演 算 子 は 2 度 使 わないことに注 意 して、普
通 に計 算 式 を解 くのと同 じ要 領 で行 っていくことで逆 ポーランド表 記 法 の式 に
なります。
Y＝(A＋B)×(C－(D÷E))を、一 つずつ順 番 に逆 ポーランド表 記 法 に変 換 して
いきましょう。
1.
まず括 弧 内 の A＋B と D÷E を変 換 します。
Y＝AB＋×(C－DE÷)
2.
次 にもう一 つの括 弧 内 の(C－DE÷)を変 換 します。
Y＝AB＋×CDE÷－
この時 「DE÷」を一 つの項 として考 えると、「C」－「DE÷」⇒ CDE÷－となること
を理 解 しやすいかと思 います。
3.
次 に右 辺 でまだ演 算 をしていない、"×"の左 側 と右 側 で演 算 します。先
程 と同 様 に「AB＋」×「CDE÷－」⇒ AB＋CDE÷－×と考 えます。
Y＝AB＋CDE÷－×
4.
最 後 に 左 辺 と右 辺 を"＝"で演 算 して逆 ポーランド表 記 法 への変 換 が
完 了 します。
YAB＋CDE÷－×＝
したがって答 えは、「イ」となります。
通 常 の式 から、逆 ポーランド表 記 法 への変 換 はそれほど難 しくありませんが、
その逆 (逆 ポーランド⇒ 普 通 の式 )は、迷 ってしまう人 もいるのではないでしょう
か。今 後 も出 題 される可 能 性 がありますので押 さえておきたいですね。
＜例 題 ２の解 説 ＞：状 態 遷 移
＋0010


c(符 号 )→b(数 字 )→b(数 字 )→b(数 字 )→b(数 字 )と遷 移 するので問 題 ありま
せん。
－1
c(符 号 )→b(数 字 )と遷 移 するので問 題 ありません。
6

12.2
b(数 字 )→b(数 字 )→d(小 数 点 )と遷 移 し、現 在 の状 態 が d であり次 の文 字 が
数 字 であるので e に遷 移 します。したがって不 合 格 となります。

9.△
b(数 字 )→d(小 数 点 )→a(空 白 )と遷 移 するので問 題 ありません。
＜例 題 ３の解 説 ＞BNF
問 題 文 のような構 文 定 義 法 は、BNF(Backus-Naur Form，バッカス・ナウア
記 法 )と呼 ばれ、XML をはじめ多 くのプログラム言 語 の構 文 定 義 に用 いられ
ています。
BNF で使 われている各 記 号 は、「::＝」が左 辺 と右 辺 の区 切 り，「｜」が or(ま
たは)，「＜＞」は非 終 端 記 号 を表 しています。




各 式 を規 則 に従 って変 換 していき、最 後 に<式 >の形 になれば規 則 どおりであ
ることになります。
A＋(B＋C)＊D
A＋(B＋C)＊D→<式 >＋<式 >
(A＋B)＋(C＋D)
(A＋B)＋(C＋D)→<式 >＋<式 >
(A＋B)＊(C＋D)
正 しい。
(A＋B)＊(C＋D)→<式 >＊<式 >→<式 >
(A＊B)＋(C＊D)
(A＊B)＋(C＊D)→(<式 >)＊(<式 >)
7
第２回
小 テ ス ト (2013/4/24)
学番
氏名
問題１：
A＝ 1， B＝ 3， C＝ 5， D＝ 4， E＝ 2 の と き ， 逆 ポ ー ラ ン ド 表 記 法 で 表 現 さ れ た
式 AB＋ CDE／ － * の 演 算 結 果 は ど れ か 。

-12
ア、
2
イ、
12
ウ、
14
エ
正解 ウ
解説
逆 ポーランド記 法 で表 現 された計 算 式 には計 算 順 番 があります。以 下 のよう
にして解 いてみましょう。
まず演 算 子 (+-*/)の左 側 にある 2 つの項 に注 目 します。この計 算 式 の場 合 で
は、+の左 にある AB と、／の左 側 にある DE です。
まず最 初 に、この演 算 子 と 2 つの項 を計 算 します。
AB+ ＝1＋3＝4, DE／＝4÷2＝2
計 算 式 をまとめると 4C2－* になります。
再 び演 算 子 (+-*/)の左 側 にある 2 つの項 に注 目 し計 算 します。今 回 は"－"の
左 にある C と 2 です。
C2- ＝5－2＝3
計 算 式 をまとめると 43* になります。
再 び演 算 子 (+-*/)の左 側 にある 2 つの項 に注 目 し計 算 します。最 後 に残 った
43*です。
43* ＝12
よって答 えは 12 になります。
問題２：
次 の状 態 遷 移 表 をもつシステムの状 態 が S1 であるときに，信 号 を t1，t2，t3，
t4，t1，t2，t3，t4 の順 に入 力 すると，最 後 の状 態 はどれになるか。ここで，空
欄 は状 態 が変 化 しないことを表 す。
8

S1
ア、
S2
イ、
ウ、
S3
S4
エ
正解 ア
解説
[状 態
[状 態
[状 態
[状 態
[状 態
[状 態
[状 態
[状 態
1.
2.
3.
4.
5.
6.
7.
8.
S1，入 力
S1，入 力
S3，入 力
S4，入 力
S2，入 力
S3，入 力
S2，入 力
S2，入 力
t1]
t2]
t3]
t4]
t1]
t2]
t3]
t4]
空 欄 なので変 化 しません。
S3 に遷 移 します。
S4 に遷 移 します。
S2 に遷 移 します。
S3 に遷 移 します。
S2 に遷 移 します。
空 欄 なので変 化 しません。
S1 に遷 移 します。
したがって最 後 の状 態 は「S1」になります。
問題３：
次 の BNF で定 義 されるビット列 S であるものはどれか。
<S> ::＝ 01|0<S>1
000111 ア、

正解
解説
9
ア
010010 イ、
010101 ウ、
011111 エ
BNF(Backus-Naur Form，バッカス・ナウア記 法 )は、コンピュータ言 語 の構
文 などを記 述 するために使 用 される表 記 法 で、プログラム言 語 ALGOL(アル
ゴル)の文 法 を表 現 するためにジョン・バッカスなどによって考 案 されました。
「::＝」は等 号 「|」は論 理 和 (OR)を表 しているので、問 題 文 の BNF は「<S>は、
01 または 0<S>1 である」と解 釈 します。また<S>は両 辺 に表 れているので再
帰 的 に定 義 されていることになります。
<S>に右 辺 のいずれかを代 入 していくと、
<S>→0<S>1→00<S>11→000111
というように定 義 できることができるのは「000111」とわかります。
10