Aritalab:Lecture/Algorithm/PolishNotation - Revision history

Adm: /* 演算子を後置する逆ポーランド記法 */

2011-12-28T09:19:38Z

‎演算子を後置する逆ポーランド記法

Adm: moved Aritalab:Lecture/Basic/PolishNotation to Aritalab:Lecture/Algorithm/PolishNotation

2011-06-01T15:30:13Z

moved Aritalab:Lecture/Basic/PolishNotation to Aritalab:Lecture/Algorithm/PolishNotation

Adm at 08:58, 21 October 2010

2010-10-21T08:58:01Z

Adm at 08:57, 21 October 2010

2010-10-21T08:57:51Z

Adm: New page: ポーランド人論理学者ウカシェヴィチが考案したポーランド記法はLISPにおける演算の記述法に同じで、演算子を前置きします。ここでは逆...

2010-10-20T02:52:15Z

New page: ポーランド人論理学者ウカシェヴィチが考案したポーランド記法はLISPにおける演算の記述法に同じで、演算子を前置きします。ここでは逆...

New page

ポーランド人論理学者ウカシェヴィチが考案したポーランド記法はLISPにおける演算の記述法に同じで、演算子を前置きします。ここでは逆ポーランド記法と呼ばれる、演算子を後置きする記述法を考えます。

===演算子を後置する逆ポーランド記法===
演算子を後置する逆ポーランド記法はスタックを利用して簡単に演算をおこなえるメリットがあります。まず、入力文字列から数値を順番に切り出し（トークン token と呼びます）、スタックに積んでいきます。もし演算子トークンがきたら、スタックから演算を施す数値（オペランド operand と呼びます）を取り出して演算結果を再びスタックに積みます。

入力文字列が終わりにきたとき、最後の演算子を用いてスタックの中身を処理すると、スタックに
は一つだけ数値が残されているはずです。これが計算の最終結果になります。

===演算子を中置する通常の電卓===
普通の数式を処理するには、演算子の優先度を考慮しなくてはなりません。
たとえば
: 2 + 3 * 5
と書かれたら、掛け算を先に処理して結果が30になります。
: 2 + log 3 * 5
と書かれたら、log を計算してから掛け算、足し算の順番になります。この式が左から順番
に読み込まれたと仮定しましょう。スタックには、
: 2, +, log, 3
が積まれます。次に * を読み込んだ時点で 3, log と逆に pop し、 log 3 = 1.09 を push します。その後、掛け算、足し算と処理を進めます。

つまり、演算子の優先度は、
: log などの単項演算子 > 乗除算 > 加減算
です。

===括弧つきの数式===
: 1 / (2 + 3) * 5
と書かれたら、括弧の中身を先に計算せねばなりません。また括弧は入れ子状に書けます。
括弧つきの数式を処理するには、スタックに積んである情報をいったん退避させ、新しい数式が始まると考えなくてはいけません。例えば以下の式を考えてみましょう。
: 2 + log ( ( 2 + 3 ) * 5 + 2 ) + 1
括弧の外側にある log は、括弧の中身が全て計算された後に適用します。
プログラム中では、左括弧をみつけたらトークンを読み込む関数を再帰呼び出しし、右括弧が数式の最後であるかのように処理します。

@@ Line 5: / Line 5: @@
 : 2 3 +
 : 2 log
-のような書き方です。演算子を後置します。
+のような、演算子を後置する書き方です。若い人には信じられないでしょうが、昔は逆ポーランド記法で数式を入力する電卓が存在しました。
-こうすると、スタックを利用して簡単に演算処理をおこなえます。まず、入力文字列から数値を順番に切り出し（トークン token と呼びます）、スタックに積んでいきます。もし演算子トークンがきたら、スタックから演算を施す数値（オペランド operand と呼びます）を取り出して演算結果を再びスタックに積みます。
 ;　足し算しか許さない逆ポーランド記号計算機の処理
 <pre>

← Older revision		Revision as of 08:58, 21 October 2010
Line 1:		Line 1:
	ポーランド人論理学者ウカシェヴィチが考案したポーランド記法はLISPにおける演算の記述法に同じで、演算子を前置きします。ここでは逆ポーランド記法と呼ばれる、演算子を後置きする記述法を、[[Aritalab:Lecture/Programming/Java/Calculator\|サンプルプログラム]]を見ながら考えます。		ポーランド人論理学者ウカシェヴィチが考案したポーランド記法はLISPにおける演算の記述法に同じで、演算子を前置きします。ここでは逆ポーランド記法と呼ばれる、演算子を後置きする記述法を、[[Aritalab:Lecture/Programming/Java/Calculator\|サンプルプログラム]]を見ながら考えます。
−
−

	===演算子を後置する逆ポーランド記法===		===演算子を後置する逆ポーランド記法===

@@ Line 1: / Line 1: @@
-ポーランド人論理学者ウカシェヴィチが考案したポーランド記法はLISPにおける演算の記述法に同じで、演算子を前置きします。ここでは逆ポーランド記法と呼ばれる、演算子を後置きする記述法を考えます。
+ポーランド人論理学者ウカシェヴィチが考案したポーランド記法はLISPにおける演算の記述法に同じで、演算子を前置きします。ここでは逆ポーランド記法と呼ばれる、演算子を後置きする記述法を、[[Aritalab:Lecture/Programming/Java/Calculator|サンプルプログラム]]を見ながら考えます。
 入力文字列が終わりにきたとき、最後の演算子を用いてスタックの中身を処理すると、スタックに
 は一つだけ数値が残されているはずです。これが計算の最終結果になります。
@@ Line 16: / Line 48: @@
 に読み込まれたと仮定しましょう。スタックには、
 : 2, +, log, 3
-が積まれます。次に * を読み込んだ時点で 3, log と逆に pop し、 log 3 = 1.09 を push します。その後、掛け算、足し算と処理を進めます。
+が積まれます。次に * を読み込んだ時点で 3, log と pop し、 log 3 = 1.09 を push します。その後、入力トークンがないので掛け算を実施、最後に足し算を行います。演算子の優先度は、
-−
-つまり、演算子の優先度は、
 : log などの単項演算子 > 乗除算 > 加減算
-です。
+です。この優先度を調べるため、関数 getPriority を用意します。
 ===括弧つきの数式===
@@ Line 29: / Line 94: @@
 括弧の外側にある log は、括弧の中身が全て計算された後に適用します。
 プログラム中では、左括弧をみつけたらトークンを読み込む関数を再帰呼び出しし、右括弧が数式の最後であるかのように処理します。