数式の表現と日本語 データ構造とプログラミング（６）

Presentation on theme: "数式の表現と日本語 データ構造とプログラミング（６）"— Presentation transcript:

1 数式の表現と日本語 データ構造とプログラミング（６）
大岩 元 慶応大学環境情報学部

2 3通りの数式表現 Infix Notation Postfix (Inverse Polish) Notation
(A + B) / C Postfix (Inverse Polish) Notation A B + C / Prefix (Polish) Notation / + A B C / C + A B

3 Postfix Notation の プログラミング言語
PostScript APL(A Programming Language) FORTH MIND 言霊

4 高級言語の役割 数式を書けば、機械語に翻訳される
Infix Notation の数式をスタックを用いてPostfix Notationに翻訳する Postfix Notationの数式をスタックを用いて計算する

5 数式表現の比較 Infix Notation 数学 Postfix Notation 日本語 Prefix Notation 英語
　数学 Postfix Notation 　日本語 Prefix Notation 　英語 A + B / C A B C / + + A / B C (A + B) / C A B + C / / + A B C A / B + C A B / C + + / A B C A / (B + C) A B C + / / A + B C

6 Infix と Postfix の比較 1 2 + 3 * 4 – 5 / ((1 + 2) * 3 –4) / 5
* 4 – 5 / ((1 + 2) * 3 –4) / 5 1 2 3 * + 4 – 5 * (1+2 * 3 –4) *5

7 括弧の効用と処理の問題点 全体の構造を一望できる 逐次処理が難しい ポーランド記法の利点 括弧が不要 逐次処理が容易

8 スタックとキュー スタックとは キューとは 中のものはとり出せない 情報を積み上げる とり出す時は上から
Last In Fast Out(LIFO) キューとは 情報を並ばせる とり出す時は最初のものから First In First Out(FIFO) 中のものはとり出せない C B A

9 スタックを用いた計算 A B + C / (A+B)/C
-- | 3 -- | 3 | 5 --| 8 --| 8 | 4 --| 2 A = 3 B = 5 C = 4

10 スタックを用いた数式変換 (A+B*C-D)/E
--|( --|(|+ --|(|+|* --|(| --|(|- --| --|/

11 括弧の埋め込み構造 ((A+B)*C+B)/((A+B)/C) Infixの括弧は埋め込み構造を表現できる
スタックの用いてInfixから Postfixに変換できる 埋め込み構造は複雑 　　なものを表現できる / C + A B * C

12 まとめ 典型的な情報処理を指示する数式は、木構造で表わされる抽象構造を持っている
数式の持つ抽象構造はInfix, Postfix, Prefixの3通りの具体表現を持つ 通常使うInfixによる数式表現は、括弧を用いて木構造を分り易く表現できる 人間に分り易い括弧による構造は、コンピュータ処理が難しくなり、スタックを用いた処理を必要とする 処理の具体構造の背後にある抽象構造を理解できる