Warning : Undefined variable $type in /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php on line 3 Warning : "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/includes/json/FormatJson.php on line 297 Warning : Trying to access array offset on value of type bool in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 660 Warning : session_name(): Session name cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 834 Warning : ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 126 Warning : ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 127 Warning : session_cache_limiter(): Session cache limiter cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 133 Warning : session_set_save_handler(): Session save handler cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 140 Warning : "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/languages/LanguageConverter.php on line 773 Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 294 Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 300 Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46 Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46 Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46
http:///mymemo.xyz/wiki/api.php?action=feedcontributions&user=121.94.62.250&feedformat=atom
miniwiki - 利用者の投稿記録 [ja]
2024-05-05T12:22:28Z
利用者の投稿記録
MediaWiki 1.31.0
逆ポーランド記法
2018-04-23T01:43:16Z
<p>121.94.62.250: </p>
<hr />
<div>{{Infobox notation<br />
|logo=[[Image:Postfix-dia.svg|125px]]<br />
}}<br />
'''逆ポーランド記法'''（ぎゃくポーランドきほう、{{Lang-en|Reverse Polish Notation, RPN}}）は、数式やプログラムの記法の一種。[[演算子]]を[[被演算子]]の後にすることから、'''後置記法''' (Postfix Notation) とも言う。<br />
<br />
その他の記法として、演算子を被演算子の中間に記述する'''[[中置記法]]'''、前に記述する'''[[ポーランド記法|前置記法]]'''（ポーランド記法）がある。<br />
<br />
逆ポーランド記法でも、演算子早出し逆ポーランド記法 ERP(early-operator reverse Polish notation)と、演算子遅出し(late-operator)逆ポーランド記法 LRP の分類があり、特に演算子早出し逆ポーランド記法は「その記号の配列順を些かも崩さずに和文に移せる」という特徴がある。<br />
<br />
名称の由来は、演算子と被演算子の順序が[[ポーランド記法]]の逆になっていることによる（「[[ポーランド記法]]」自体の由来については[[ポーランド記法]]の記事を参照のこと）。<br />
<br />
<br />
== 概要 ==<br />
例えば、「3 と 4 を加算する」という演算を、一般的に数式の表記に用いられる中置記法で記述すると、以下のようになる。<br />
<br />
3 + 4<br />
<br />
一方、逆ポーランド記法では、加算を表す演算子 + を、被演算子である 3 と 4 の後（右）に置いて、以下のよう記述する。<br />
<br />
3 4 +<br />
<br />
逆ポーランド記法による表現は[[日本語]]など[[SOV型]]の言語の[[語順]]とよく似ており、上式であれば「3 と 4 を加算する」とそのままの順序で読み下せる。逆ポーランド記法を使う[[Forth]]の影響を受けている[[プログラミング言語]][[Mind (プログラミング言語)|Mind]]では、上式を「<code>3と 4とを 足す</code><!--「3 と 4 とを」というように離すと、Mindでは構文エラーのはず-->」と記述する。（しかし、「1を 2から 引く」と「1から 2を 引く」で破綻する。以上のような類似は「たまたま一致する場合もある」だけに過ぎず、深入りするならきちんと言語学と日本語学や[[言語類型論]]を基礎から押さえる必要がある）<br />
<br />
もう少し複雑な例として、中置記法による以下の式は、<br />
<br />
(1 + 5) * (2 + 3)<br />
<br />
逆ポーランド記法で記述すると以下の通りとなる。<br />
<br />
1 5 + 2 3 + *<br />
<br />
つまり、逆ポーランド記法では後で使われる演算子ほど、右に位置することになる（ポーランド記法では逆になり、左に位置する演算子ほど後で使われる）。ちなみに上式を日本語で読み下すと「1 と 5 を足したものに 2 と 3 と足したものをかけ合わせる」となる。<br />
<br />
その他、逆ポーランド記法の特徴として括弧の使用法や[[区切り文字]]の必要性などがあるが、これらについては[[ポーランド記法]]と同様のため、そちらの項を参照のこと。<br />
<br />
== コンピュータへの応用 ==<br />
元々、逆ポーランド記法は[[ポーランド記法]]を[[コンピュータ]]での利用に適した形に改変したものである。<br />
<br />
逆ポーランド記法を使えば、式の[[計算]]をする（評価）には、先頭からひとつずつ順番に記号を読み込み、その記号が演算子以外であれば[[スタック]]に値を積み、演算子であればスタックから値を取り出して演算し結果をスタックに積む、という簡単な操作の繰り返しだけでよい。そのため、プログラミング初心者の練習課題として、逆ポーランド記法の電卓を作ることがよく行われる。<br />
<br />
前述の手順であれば、スタックに積むのは値（たとえば後述する例では整数値）だけである（例を見て確認されたい）。もしこれが他の順序だったとしたら、演算子に相当するものを記憶するか、順番に読むだけでは済まず行きつ戻りつするか、などしなければならない。<br />
<br />
[[プログラミング言語]]に[[Forth]]や[[PostScript]]などのこの記法を採用したものがある。<br />
<br />
[[ヒューレット・パッカード]]社の[[電卓]]（[[HP-35]]など）が有名で、他いくつかの電卓（特に[[関数電卓]]に採用がある）にもあるが、逆ポーランド記法'''順'''による入力方法を採用している電卓がある（近年の関数電卓のような数式入力ではなく、計算機械としてスタックモデルであり、それを直接操作しているという形なので、厳密なことを言うと逆ポーランド記法'''「順」'''ということになる）。<br />
<br />
=== 計算動作の例 ===<br />
（このような動作をベースとしている計算モデルやコンピュータを、[[スタックマシン]]と言う）<br />
<br />
例題として以下の式を考える。スタックの他に1個の[[アキュムレータ (コンピュータ)|アキュムレータ]]を持つ計算機だとする。<br />
<br />
1 2 + 4 5 + *<br />
<br />
<tt>[]</tt>は[[スタック]]の内容。左から右に積む。最初は空である。<br />
<br />
# 1をスタックに積む <tt>[1]</tt><br />
# 2をスタックに積む <tt>[2 1]</tt><br />
# <tt>+</tt>が押されたら、<br />
## スタックからデータを下ろしアキュムレータに入れる（アキュムレータ ← 2） <tt>[1]</tt><br />
## スタックからデータを下ろしアキュムレータに足す（アキュムレータ += 1） <tt>[]</tt><br />
## アキュムレータの内容は 3 になる <tt>(1 + 2 = 3)</tt><br />
## アキュムレータの内容をスタックに積む <tt>[3]</tt><br />
# 4をスタックに積む <tt>[4 3]</tt><br />
# 5をスタックに積む <tt>[5 4 3]</tt><br />
# <tt>+</tt>が押されたら、<br />
## スタックからデータを下ろしアキュムレータに入れる（アキュムレータ ← 5） <tt>[4 3]</tt><br />
## スタックからデータを下ろしアキュムレータに足す（アキュムレータ += 4） <tt>[3]</tt><br />
## アキュムレータの内容は 9 になる <tt>(4 + 5 = 9)</tt><br />
## アキュムレータの内容をスタックに積む <tt>[9 3]</tt><br />
# <tt>*</tt>が押されたら、<br />
## スタックからデータを下ろしアキュムレータに入れる（アキュムレータ ← 9） <tt>[3]</tt><br />
## スタックからデータを下ろしアキュムレータに掛ける（アキュムレータ *= 3） <tt>[]</tt><br />
## アキュムレータの内容は 27 になる <tt>(3 * 9 = 27)</tt><br />
## アキュムレータの内容をスタックに積む <tt>[27]</tt><br />
<br />
このように<br />
* スタックにデータを積む (PUSH) 操作<br />
* スタックからデータを下ろす (POP) 操作<br />
* 二つのオペランド間の演算<br />
だけで計算動作が可能である。<br />
<br />
スタックトップの直接演算が可能な構造ならば、例えば最初の部分は<br />
# 1をスタックに積む <tt>[1]</tt><br />
# 2をスタックに積む <tt>[2 1]</tt><br />
# +が押されたら、<br />
## スタックからデータを下ろしレジスタに入れる（レジスタ←2） <tt>[1]</tt><br />
## スタックトップにレジスタの値を加算する <tt>[3]</tt><br />
と簡略化される。<br />
<br />
== 文献 ==<br />
* [[水谷静夫]] 「日本語の語順と逆ポーランド記法」 第7回 プログラミング・シンポジウム (1966)<br />
* [[水谷静夫]] 「和文の語順と逆ポーランド記法」 『国語学』第61集 (1965年6月30日)<br />
* [[斎藤正彦]] 『数のコスモロジー』、[[筑摩書房]]〈[[ちくま学芸文庫]]Math＆Science〉、2007年、189から192頁。<br />
<br />
== 関連項目 ==<br />
* [[操車場アルゴリズム]]<br />
* [[Intel 8087]]<br />
<br />
== 外部リンク ==<br />
* [http://www.nendai.nagoya-u.ac.jp/~kato/HP48/rpn.html RPNとRPL（Kato Takenori）]<br />
* [http://calccafe.s1001.xrea.com/readings/4LEVEL_RPN/4LEVEL_RPN.html RPN と 4 Level RPN 電卓（電卓喫茶）]<br />
<br />
[[Category:数学の表記法|きやくほおらんときほう]]<br />
[[Category:プログラミング言語の構文|きやくほおらんときほう]]<br />
[[Category:数学に関する記事|きやくほおらんときほう]]</div>
121.94.62.250
中置記法
2018-04-23T01:42:07Z
<p>121.94.62.250: </p>
<hr />
<div>{{Infobox notation<br />
|logo=[[Image:Infix-dia.svg|125px]]<br />
}}<br />
'''中置記法'''（ちゅうちきほう、<em lang=en>infix notation</em>）とは、数式やプログラムを記述する方法（記法）の一種。[[演算子]]を操作対象の中間に記述することから、このように呼ばれる。<br />
<br />
その他の記法として、演算子を操作対象の前（左）に記述する'''[[ポーランド記法|前置記法]]'''（ポーランド記法）、演算子を操作対象の後（右）に記述する'''[[逆ポーランド記法|後置記法]]'''（逆ポーランド記法）がある。<br />
<br />
四則演算など初歩的な[[算術]]においては、もっぱら中置記法が多用されている。<br />
<br />
== 多義性 ==<br />
次のような[[バッカス・ナウア記法|BNF]]の構文規則群で定義される中置記法の文法について考える。<br />
<br />
<expr> = <infix> | <num><br />
<infix> = <expr> <op> <expr><br />
<num> = 0 | 1 | 2 | 3 | 4 | ...<br />
<op> = ＋ | ー | × | ÷<br />
<br />
この文法には多義性（ambiguity。[[曖昧]]さ、とも言うが、「曖昧」という語には「輪郭がはっきりしない」というような意味もあるがそちらの意味ではない）がある（「[[曖昧な文法]]」の記事を参照）。たとえば、<br />
<br />
"1 - 2 + 3"<br />
<br />
が、この構文規則からは「(1 - 2) + 3」と「1 - (2 + 3)」の、どちらに相当する[[構文木]]にも[[構文解析]]できてしまう。<br />
<br />
加算のような[[結合法則]]の成り立つ演算だけが対象である場合など、むしろ便利である場合もあるが、一般の場合には補助的なカッコを多用して明示するなどの必要がある。算術の四則演算では、加減算の両方が使われている場合などについて、左から右という規則で意味の一意化が図られている。また、カッコの省略を意図して、加減算に対する乗除算の優先という規則も、もっぱら付加される。<br />
<br />
[[yacc]]などでは、BNFによる定義に、さらに「[[演算子の優先順位]]」と「演算子の結合性」（[[結合法則#プログラミング言語]]を参照）に相当する規則を付加することができ、これは大変に使い良い機能である。特に（yaccは違うが）[[再帰下降構文解析]]など[[LL法]]の構文解析では、四則演算の式のような左から右の順をナイーブに実装すると[[左再帰]]の問題があるので、問題を避けて簡潔に定義する方法があると良い。<br />
<br />
== 関連項目 ==<br />
* [[ポーランド記法]]（前置記法）<br />
* [[逆ポーランド記法]]（後置記法）<br />
* [[操車場アルゴリズム]]<br />
<br />
{{DEFAULTSORT:ちゆうちきほう}}<br />
[[Category:数学の表記法]]<br />
[[Category:プログラミング言語の構文]]<br />
[[Category:数学に関する記事]]</div>
121.94.62.250
ポーランド記法
2018-04-23T01:37:56Z
<p>121.94.62.250: </p>
<hr />
<div>{{Infobox notation<br />
|logo=[[Image:prefix-dia.png|125px]]<br />
}}<br />
'''ポーランド記法'''（ポーランドきほう、Polish Notation）とは、数式やプログラムを記述する方法（記法）の一種。[[演算子]]（オペレータ）を[[被演算子]]（オペランド）の前（左）に記述することから、'''前置記法'''（ぜんちきほう、prefix notation）とも言う。<br />
<br />
その他の記法として、演算子を被演算子の中間に記述する'''[[中置記法]]'''、後（右）に記述する'''[[逆ポーランド記法|後置記法]]'''（逆ポーランド記法）がある。<br />
<br />
名称の由来は、[[ポーランド]]人の論理学者[[ヤン・ウカシェヴィチ]] (Jan &#321;ukasiewicz) が考案したことによる。<br />
<br />
== 概要 ==<br />
例えば、「1 と 2 を加算する」という演算を、一般的に数式の表記に用いられる中置記法で記述すると、以下のようになる。<br />
<br />
1 + 2<br />
<br />
一方、ポーランド記法では、加算を表す演算子 + を、被演算子である 1 と 2 の前（左）に置いて、以下のように記述する。<br />
<br />
+ 1 2<br />
<br />
ポーランド記法は、演算子と被演算子を分離して記述することで、式の解釈を明確にするために考えだされたものであり、二項演算であれば、括弧を使うことなく演算を一意に表記することができる。<br />
<br />
例えば、中置記法による以下の式を考える。<br />
<br />
(1 + 5) * (2 + 3)<br />
<br />
これをポーランド記法で記述すると以下の通りとなり、括弧が不要である。<br />
<br />
* + 1 5 + 2 3<br />
<br />
一方、ポーランド記法では、被演算子同士を区切る記号（[[区切り文字]]）が必要である（中置記法では演算子が区切り文字として働くため不要）。一般には空白が用いられることが多く、上の例では1と5の間、2と3の間にある空白がそれに当たる。<!--<br />
<br />
なお、ポーランド記法においても、読みやすくするために括弧を用いることがあり、以下のように記述しても間違いではない。<ref>[[LISP]]はこのような見た目だが、LISPで括弧が必須なのはLISPの理由による。すなわち、LISPでは式を読み込む時に式の木構造を構築するのだが、括弧なしで式の木構造を構築するには、演算子を識別し、その引数の数がわかっていなければならない。しかし、読み込み時にはその文字列から演算子かどうかはわからないし、任意個の引数をとる演算子もある。このため括弧なしには木構造を構築できないので、LISPでは括弧が必須なのである。</ref><br />
<br />
(* (+ 1 5) (+ 2 3))<br />
--><!--<br />
↑LISPは「ポーランド記法」だ、と強弁するために付け加えられたもののような気がします<br />
--><!--<br />
また、3つ以上の被演算子に対して同じ演算を行う場合、括弧を使って演算子を省略し、以下のように記述することがある。<br />
<br />
(+ 1 2 3 4)<br />
<br />
これは、中置記法による以下の式と同じ意味である。<br />
<br />
1 + 2 + 3 + 4<br />
--><!-- ← これはLISPの + が不定個の引数に対応してるという話で、ここに書くべきこっちゃありません。LISPのように演算子が任意個の引数を取るようにする場合は、括弧が必要になります、という解説なら一応はアリでしょうが、英語版を見ても特にそういう解説はないですし、削るだけとします--><br />
<br />
== コンピュータへの応用 ==<br />
ポーランド記法では、演算子があたかも関数適用のような形態をとる。これを直接利用したのが[[LISP]]で、LISPでは、たとえば <code>+</code> も <code>cons</code> などと同じ、関数の名前に過ぎず、関数と全く同じに実引数リストの前に置く。これは、たとえば[[C++]]の、演算子（その多くが[[中置記法]]）の[[多重定義|オーバーロード]]のために、<code>operator+</code> というような特別な構文を使ったりしているのなどとは対照的である。<br />
<br />
== 関連項目 ==<br />
* [[逆ポーランド記法]]<br />
<br />
== 脚注・参照 ==<br />
<references/><br />
<br />
[[Category:数学の表記法]]<br />
[[Category:ポーランド]]<br />
[[Category:プログラミング言語の構文]]<br />
[[Category:数学に関する記事]]<br />
{{デフォルトソート:ほおらんときほう}}</div>
121.94.62.250
Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46