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