Document

数式の表現と日本語
データ構造とプログラミング（６）
大岩元
慶応大学環境情報学部
[email protected]
3通りの数式表現
Infix Notation
(A + B) / C
Postfix (Inverse Polish) Notation
AB+C/
Prefix (Polish) Notation
/
/+ABC
+
A
C
B
Postfix Notation の
プログラミング言語
PostScript
APL(A Programming Language)
FORTH
MIND
言霊
高級言語の役割
数式を書けば、機械語に翻訳される
Infix Notation の数式をスタックを用いてPostfix
Notationに翻訳する
Postfix Notationの数式をスタックを用いて計算す
る
数式表現の比較
Infix Notation
数学
A+B/C
Postfix Notation Prefix Notation
日本語
英語
ABC/+
+A/BC
(A + B) / C
AB+C/
/+ABC
A/B+C
AB/C+
+/ABC
A / (B + C)
ABC+/
/A+BC
Infix と Postfix の比較
1 2 +3 * 4–5/
((1 + 2) * 3 –4) / 5
123*+4–5*
(1+2 * 3 –4) *5
括弧の効用と処理の問題点
全体の構造を一望できる
逐次処理が難しい
ポーランド記法の利点
括弧が不要
逐次処理が容易
スタックとキュー
スタックとは
情報を積み上げる
とり出す時は上から
Last In Fast Out(LIFO)
キューとは
情報を並ばせる
とり出す時は最初のものから
First In First Out(FIFO)
中のものはとり出せない
C
C
B
B
A
A
スタックを用いた計算
AB+C/
(A+B)/C
-- | A
-- | A | B
-- | A + B
-- | A + B | C
-- | (A + B) / C
-- | 3
-- | 3 | 5
--| 8
--| 8 | 4
--| 2
A=3 B=5 C=4
スタックを用いた数式変換
(A+B*C-D)/E
--|(
--|(|+
--|(|+|*
--|(|
--|(|--|
--|/
--|
A
AB
ABC
ABC*+
ABC*+D
ABC*+DABC*+D-E
ABC*+D-E/
括弧の埋め込み構造
((A+B)*C+B)/((A+B)/C)
Infixの括弧は埋め込み構
造を表現できる
スタックの用いてInfixから
Postfixに変換できる
埋め込み構造は複雑 +
なものを表現できる
A
/
+
*/
+
C
B
C
/
B
A
C
B
まとめ
典型的な情報処理を指示する数式は、木構造で表
わされる抽象構造を持っている
数式の持つ抽象構造はInfix, Postfix, Prefixの3通り
の具体表現を持つ
通常使うInfixによる数式表現は、括弧を用いて木構
造を分り易く表現できる
人間に分り易い括弧による構造は、コンピュータ処
理が難しくなり、スタックを用いた処理を必要とする
処理の具体構造の背後にある抽象構造を理解でき
る

Download Report