Document

数式の表現と日本語
大岩元
慶応大学環境情報学部
[email protected]
3通りの数式表現
• Infix Notation
–
(A + B) / C
• Postfix (Reverse Polish) Notation
–
AB+C/
/
• Prefix (Polish) Notation
–
+
/ +AB C
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)
• 中のものはとり出せない
in
out
in
C
C
B
B
A
A
out
スタックを用いた計算
AB+C/
•
•
•
•
•
-- | A
-- | A | B
-- | A + B
-- | A + B | C
-- | (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
B
C
B
/
+
A
C
B
まとめ
• 典型的な情報処理を指示する数式は、木構造で表わさ
れる抽象構造を持っている
• 数式の持つ抽象構造はInfix, Postfix, Prefixの3通りの具
体表現を持つ
• 通常使うInfixによる数式表現は、括弧を用いて木構造を
分り易く表現できる
• 人間に分り易い括弧による構造は、コンピュータ処理が
難しくなり、スタックを用いた処理を必要とする
• 処理の具体構造の背後にある抽象構造を理解できるこ
とが、情報教育の重要な目的である

Download Report