RPN - Perl extension for Reverse Polish Math Expression Evaluationc

Location : Home > Languages > Perl > Package
Title : RPN

　RPN - 逆ポーランド記法

use Math::RPN;

$value = rpn(expr...);
@array = rpn(expr...);

　expr... は１つ以上のスカラまたは逆ポーランド記法によるスカラのリストである。逆ポーランド記法による式はカンマで区切られた数及び／または演算子の列である。（カンマはスカラーの中だけで要請される。）

説明

　逆ポーランド記法による関数はカンマで区切られた値と演算子からなる逆ポーランド記法による式を含むスカラまたは巣からのリストをとり、コンテキストによって結果またはスタックを返す。配列コンテキストで呼び出されればスタック全部を返す。スカラコンテキストの場合はスタックの最上段を返す。スカラコンテキストではスタックに１つ以上の値が残っていれば標準エラー（STDERR）に警告を出す。
　エラー発生時にはエラーメッセージが表ジュネらーに出力され、逆ポーランド記法は undef を返す。
　式は値と演算子のいかなる組み合わせでもよい。
　演算子でないトークンはスタックにプッシュされる値と見なされる。

　逆ポーランド記法の説明はこのドキュメントの範囲を超えているが、簡単にスタックベースの数式記述法としておこう。この記法は括弧が不要で、通常の代数式と比べてコンピュータにおけるパースを単純化できる。またわずかの努力で人間にも可読である。
　この評価は式の左から右へと行う。トークンに出会うたびに演算子のリストと照らし合わせる。マッチするものがあればスタックが無くなるまで実行する。スタックが無くならなければ演算子が要求する被演算子の数だけスタックの上から削除する。結果はスタックにプッシュされる。演算の順序は重要であり（-, / , % 等）、スタックの最上の項目を右被演算子、次の項目を左被演算子として扱う。たとえば "5, 3, -" の結果は 2 であって、-2 ではない。トークンが既知の演算子とマッチしなければそのままスタックにプッシュされる。結果として意図しない結果を得ることもある。例えば式 "5, 3, grandma, +, *" は、5 * (3 + 0) までが処理可能な演算であるので 15 を返す。つまりまず 5 がスタックにプッシュされ、次に 3、grandma がプッシュされた後に、+ が評価される。ここでは 3 + "grandma" を評価しようとする。 Perl は "grandma" を数学的には 0 と評価するので 3 がスタックにプッシュされる。次に * はスタックの上から２つの要素 [5][3] を掛け合わせるので 15 を得、これをスタックにプッシュする。

演算子

　以下の演算子は単純なスタック文法に従う。
　各項目は括弧（[ ]）でスタックの要素であることを示している。
　-> は演算子が行う変換を示している。つまり -> よりも左のものはすべて演算子よりも先にスタックに現れなければならないし、右にあるものは演算子よりも後にこなければならない。例えば [a][b]->[a + b] は + 演算子の前に２つの要素がスタックになければならないし、その和がスタックに残されることを示している。
　 -> の左側の最初の項目以下のスタックにあるものは影響を受けず、右側に結果を示すスタックを残すことになる。言い換えれば、スタックが [5][3][2][5][6] であり、+ 演算子を評価する場合、変換 [a][b]->[a + b] はmeans thatスタックから 5 と 6 をプルし、[11] で置き換えるため、 [5][3][2][11] となる。
　ついでに、条件式を示す (condition ? result : otherwise) のようなコンストラクタは、条件が真ならスタックに結果を置く。条件が偽の場合は otherwise で指定されている値をスタックに格納する。つまり、(a != 0 ? [b] : [c]) は「 a が 0 に等しくなければ [b] をスタックに格納し、a が 0 に等しければ [c] を格納する」ということを意味する。
　他の記号の意味は後述する。
　以下の演算子がサポートされている。

演算子演算

+, ADD [a][b]->[a + b]

++, INCR [a]->[a + 1]

-, SUB [a][b]->[a - b]

--, DECR [a]->[a - 1]

*, MUL [a][b]->[a * b]

/, DIV [a][b]->[a / b]

%, MOD [a][b]->[a % b]

POW [a][b]->[a^b]

SQRT [a]->[sqrt(a)]

SIN [a]->[sin(a)]

COS [a]->[cos(a)]

TAN [a]->[tan(a)]

LOG [a]->[log(a)]

EXP [a]->[e^a]

ABS [a]->[abs(a)]

INT [a]->[int(a)]

&, AND [a][b]->[a & b]

|, OR [a][b]->[a | b]

!, NOT [a]->(a == 0 ? [1] : [0])

~ [a]->(a xor -1) （a の全ビットを反転）

<, LT [a][b]->(a < b ? [1] : [0])

<=, LE [a][b]->(a <= b ? [1] : [0])

=, ==, EQ [a][b]->(a == b ? [1] : [0])

>, GT [a][b]->(a > b ? [1] : [0])

>=, GE [a][b]->(a >= b ? [1] : [0])

!=, NE [a][b]=>(a != b ? [1] : [0])

IF [a][b][c]-> (a != 0 ? [b] : [c])

DUP [a]->[a][a]

EXCH [a][b]->[b][a]

POP [a][b]->[a]

MIN [a][b]->([a] < [b] ? [a] : [b])

MAX [a][b]->([a] > [b] ? [a] : [b])

TIME 現在の時刻をプッシュ
（midnight UTC 1970 からの秒数）

RAND 0< x <1 の範囲の乱数をスタックにプッシュする。

LRAND [a]->[x = rand(0 < x < a)]

　ビットワイズブール演算子（&, |, !, ~）はスタックの値を整数かした値に対して演算される。すなわち [a][b]->[a&b] は内部的には push(@stack, (int(pop(@stack))&int(pop(@stack)))) として処理される。
　また、IF 演算子はスタックにおいて "then" 及び "else" 節にあたる特別なコンストラクトをサポートする。括弧（{ }）を用いて逆ポーランド記法による式を示し、評価しないままスタックに格納する。 IF の結果としてスタックに式が格納されればそのときに評価される。柔軟性を確保でき、使用されない節の計算を行わないため効率的に処理ができる。
　例は以下の通り。

1, {, 5, 3, +, 10, *, }, {, 1, 2, 3, +, +, }, IF

　この例は評価の最後には 80 を得る。まず IF 節は 1 なので真であり、 {, 5, 3, +, 10, *, } は評価され、結果はスタックに格納される。
　ブール演算子 xorはコードには入れているがテストされていない。Perl における xor の機能が壊れテいるかも知れず、演算子は厳密に実験的なものと見なされる。そのため、自分のリスクで使って欲しい。xor 演算子はドキュメント化されていない。

使用例

　逆ポーランド記法による式の例を以下に挙げる。これにより逆ポーランド記法の例示と文法のよい例になるだろう。

100, 9, *, 5, /, 32, +    ：摂氏100度を華氏212度に変換
(100 * 9 / 5 + 32)

5, 3, LT, 100, 500, IF	Yields 500
(5! < 3 = 0, 100, 500, IF == 500, "else" 節)

参照

　以下の記号は逆ポーランド記法の記述で用いられる。ここにおける説明は短い参照である。詳しい情報については適宜、数学・ブール代数・三角法のテキストにあたって欲しい。

記号カテゴリ意味

^ 数学べき乗（x^y は X の Y 乗を意味する。x^2 なら X の２乗）

% 数学法または剰余

& ブール代数ブール代数における AND

| ブール代数ブール代数における OR

! ブール代数ブール値の逆転（true->false, false->true）

sqrt 数学平方根（sqrt(9) ならば 3）

sin 三角法所与の角度（ラジアン）のSINE

cos 三角法所与の角度（ラジアン）のCOSINE

tan 三角法所与の角度（ラジアン）のTANGENT

log 数学所与の値の対数
e^log(x) は x [e は自然対数]

exp 数学指数関数。 exp(x) は e^x を返す。exp(log(x)) は x を返す。

abs 数学所与の値の絶対値を返す。abs(-5) は5。abs(5) は5。
基本的に x = (x < 0 ? x * -1 : x)

int 数学所与の値を小数部分を切り捨てて整数にした値。
（これは丸目を意味しない。
4.9は4になる。もし丸めを行いたければ n, .5, +, INT を行う。）

著者

　Owen DeLong, <owen@delong.com>

参考資料

　perl(1)

Updated : 2007/05/22

演算子	演算
+, ADD	[a][b]->[a + b]
++, INCR	[a]->[a + 1]
-, SUB	[a][b]->[a - b]
--, DECR	[a]->[a - 1]
*, MUL	[a][b]->[a * b]
/, DIV	[a][b]->[a / b]
%, MOD	[a][b]->[a % b]
POW	[a][b]->[a^b]
SQRT	[a]->[sqrt(a)]
SIN	[a]->[sin(a)]
COS	[a]->[cos(a)]
TAN	[a]->[tan(a)]
LOG	[a]->[log(a)]
EXP	[a]->[e^a]
ABS	[a]->[abs(a)]
INT	[a]->[int(a)]
&, AND	[a][b]->[a & b]
\|, OR	[a][b]->[a \| b]
!, NOT	[a]->(a == 0 ? [1] : [0])
~	[a]->(a xor -1) （a の全ビットを反転）
<, LT	[a][b]->(a < b ? [1] : [0])
<=, LE	[a][b]->(a <= b ? [1] : [0])
=, ==, EQ	[a][b]->(a == b ? [1] : [0])
>, GT	[a][b]->(a > b ? [1] : [0])
>=, GE	[a][b]->(a >= b ? [1] : [0])
!=, NE	[a][b]=>(a != b ? [1] : [0])
IF	[a][b][c]-> (a != 0 ? [b] : [c])
DUP	[a]->[a][a]
EXCH	[a][b]->[b][a]
POP	[a][b]->[a]
MIN	[a][b]->([a] < [b] ? [a] : [b])
MAX	[a][b]->([a] > [b] ? [a] : [b])
TIME	現在の時刻をプッシュ（midnight UTC 1970 からの秒数）
RAND	0< x <1 の範囲の乱数をスタックにプッシュする。
LRAND	[a]->[x = rand(0 < x < a)]

記号	カテゴリ	意味
^	数学	べき乗（x^y は X の Y 乗を意味する。x^2 なら X の２乗）
%	数学	法または剰余
&	ブール代数	ブール代数における AND
\|	ブール代数	ブール代数における OR
!	ブール代数	ブール値の逆転（true->false, false->true）
sqrt	数学	平方根（sqrt(9) ならば 3）
sin	三角法	所与の角度（ラジアン）のSINE
cos	三角法	所与の角度（ラジアン）のCOSINE
tan	三角法	所与の角度（ラジアン）のTANGENT
log	数学	所与の値の対数 e^log(x) は x [e は自然対数]
exp	数学	指数関数。 exp(x) は e^x を返す。exp(log(x)) は x を返す。
abs	数学	所与の値の絶対値を返す。abs(-5) は5。abs(5) は5。基本的に x = (x < 0 ? x * -1 : x)
int	数学	所与の値を小数部分を切り捨てて整数にした値。（これは丸目を意味しない。 4.9は4になる。もし丸めを行いたければ n, .5, +, INT を行う。）