はい。これはかなり面白いPerl CGIです。
factor.cgi
#!/usr/local/bin/perl
use strict;
use CGI qw{:standard :html3 -no_xhtml};
my $in = new CGI;
print header( -type =>"text/html; charset=euc-jp"),
start_html(-title=>'rpn');
my $str = $in->param('value') || ' 8x^3+12x^2-2x-3 '; #<-----
$str =~ s/\s//g;
print factor($str)."\n";
print end_html;
sub factor{
my @a = arrange(shift); # 式の整理 次数でまとめる
if((my $i = arrayGcd(@a)) > 1){
for(@a){ $_ /= $i;}
return ed2(ed($i).factor(array2expr(@a)));
}
return factor_div(@a) if($#a > 2); #3次以上の時は因数定理?除算の定理?で求める
return ed2("x(".ed($a[2])."x".ed($a[1]).")") unless($a[0]);
my @a0 = measure($a[0],1); # 約数を求める a0 = (b1,b2)...
my @a2 = measure($a[2],0); # " a2 = (c1,c2)...
for (@a0){ # (a0,a1,a2)=(b1,c1)(b2,c2)
my ($b1,$b2) = split ","; # a1=b1*c2+b2*c1となるb1,b2,c1,c2を求める
for(@a2){
my ($c1,$c2) = split ",";
return ed2("(".ed($c1)."x".ed($b1).")(".ed($c2)."x".ed($b2).")")
if($a[1] == $b1*$c2+$b2*$c1);
return ed2("(".ed($c2)."x".ed($b1).")(".ed($c1)."x".ed($b2).")")
if($a[1] == $b1*$c1+$b2*$c2);
}
}
return "(".array2expr(@a).")"; # 数値を式に変換 -> a2 x^2 + a1 x + a0
}
sub factor_div{ # 因数定理? 除算の定理?
my @a = @_;
my ($tmp,$tmp1,$k);
for my $z (1..abs($a[$#a])){
for(my $i=1;$i<=abs($a[0]);$i++){
$tmp = $tmp1 = 0;
$k = 0 - $i;
for(my $j=0;$j<=$#a;$j++){
my $z2 = ($j) ? $z : 1;
$tmp += $a[$j]*($i**$j)/($z2**$j);
$tmp1 += $a[$j]*($k**$j)/($z2**$j);
} # 誤差調整の為、sprintfを追加
return ed2("(".ed($z)."x".ed(0-$i).")".factor(array2expr(array_div($z,0-$i,@a))))
unless(sprintf("%f",$tmp)+0);
return ed2("(".ed($z)."x".ed(0-$k).")".factor(array2expr(array_div($z,0-$k,@a))))
unless(sprintf("%f",$tmp1)+0);
}
}
if($a[0]==0){
shift @a;
return ed2("x".factor(array2expr(@a)));
}
if(@a==5 and $a[1]==0 and $a[2]==0 and $a[3]==0 and
$a[4] >= 0 and $a[4] == (int(sqrt($a[4])))**2){
my @b = ($a[0],0,1);
my $n=sqrt($a[4]);
my $ans = factor(array2expr(@b));
if($n == 1){$n="";};
if($ans =~ s/x([+-])/${n}x\^2$1/g){
return $ans;
}else{
return "(".array2expr(@a).")";
}
}elsif(@a==5 and $a[1]==0 and $a[3]==0){
my @b = @a[0,2,4];
my $ans = factor(array2expr(@b));
if($ans !~ /(\(.+\)){2,}/){ # X^2をXと置いてa^2-b^2=(a+b)(a-b)の公式にて
if($b[0] >= 0 and $b[2] == 1 and $b[1]+1 == sqrt($b[0])*2){
return "(" . array2expr(sqrt($b[0]),1,1) . ")(" . array2expr(sqrt($b[0]),-1,1) . ")" ;
}
return "(" . array2expr(@a) . ")";
}
$ans =~ s/x/x^2/g;
return $ans;
}else{
return "(".array2expr(@a).")";
}
}
sub array_div{
my ($x,$z,@a) = @_;
my @b;
for (my $i = $#a;$i>0;$i--){
$b[$i-1]=$a[$i]/$x;
$a[$i-1]-= $z*$b[$i-1];
}
return @b;
}
sub arrange{ # 式の整理
my $str = shift;
my @a = (0,0,0);
my ($b,$c);
while($str =~ s/([+-]*[\d\.]*)x\^([\d\.]*)//){
$b=$2;
$c=$1;
$a[$b] += ($c =~ /^[+-]*$/) ? "$c" . "1" : $c;
}
while($str =~ s/([+-]*[\d\.]*)x//){
$c = $1;
$a[1] += ($c =~ /^[+-]*$/) ? "$c" . "1" : $c;
}
while($str =~ s/([+-]*[\d\.]{1,})//){
$a[0] += $1;
}
return @a;
}
sub measure{ # 約数を求める
my ($a,$flag) = @_;
my $n = abs($a);
my @ans = ();
for (my $j = int(sqrt($n)); $j > 0;$j--){
unless ($n % $j){
if($a<0){
push(@ans,join(",",$j,$n/$j*(-1)));
push(@ans,join(",",$j*(-1),$n/$j));
}else{
push(@ans,join(",",$j,$n/$j));
push(@ans,join(",",$j*(-1),$n/$j*(-1))) if($flag);
}
}
}
return @ans;
}
sub array2expr{ # 数値を式に変換
my @a = @_;
my $new = "";
for (my $i = $#a ; $i>=0;$i--){
next if($a[$i] ==0);
$new .= ed($a[$i]);
if($i == 1){
$new .= "x";
}elsif($i > 1){
$new .= "x^".$i;
}
}
return ed2($new);
}
sub arrayGcd{
# my @a = @_;
my $ans = 0;
for(@_){ $ans = gcd($ans,$_);}
return abs($ans);
}
sub gcd{
my ($x,$y) = @_;
return $y ? gcd($y,$x % $y) : $x ;
}
sub ed{
my $n = shift;
return ($n >= 0) ? "+" . $n : $n;
}
sub ed2{
my $str = shift;
$str =~ s/([+-])1(x)/$1$2/g;
$str =~ s/^\+//;
$str =~ s/\(\+/\(/g;
my $sub = 1;
if ($str =~ s/xx(\^(\d+))/XX/){
$sub = $2;
}
while($str =~ s/xx/X/i){$sub++;}
$str =~ s/X/x^$sub/ ;
return $str;
}
入力された多項式を、Perlで因数分解してHTMLとして返すCGI
です。
例えばデフォルトの
8x^3+12x^2-2x-3
を受け取ると、因数分解して
(2x-1)(2x+1)(2x+3)
のような形に変換します。
しかも、単純な文字列処理ではなく、多項式を「係数の配列」に変換してから因数分解するという作りになっています。
1. 全体の流れ
まず全体像を見ると、かなり分かりやすくなります。
ブラウザ
│
│ ?value=8x^3+12x^2-2x-3
▼
factor.cgi
│
├─ CGIパラメータ取得
│
├─ 空白除去
│
└─ factor($str)
│
▼
arrange()
式を係数配列へ
│
▼
係数のGCDを調べる
│
├─ 共通因数あり
│ ↓
│ factor() 再帰
│
└─ 共通因数なし
│
├─ 3次以上
│ ↓
│ factor_div()
│
└─ 2次
↓
measure()
約数を列挙
↓
(bx+c)(dx+e)
を試す
│
▼
ed2()
表記を整える
この構造を見ると、以前見ていた ASTのコードとは違って、かなり「数学アルゴリズムそのもの」をPerlで書いているタイプですね。
2. CGIとしての入り口
最初はここです。
#!/usr/local/bin/perl
use strict;
use CGI qw{:standard :html3 -no_xhtml};
my $in = new CGI;
CGIとして動かすPerlです。
CGIモジュールによって、
$in->param('value')
でURLなどから渡された value パラメータを取得できます。
例えば、
factor.cgi?value=8x^3+12x^2-2x-3
なら、
$in->param('value')
は
8x^3+12x^2-2x-3
になります。
3. HTMLを出力
print header(
-type => "text/html; charset=euc-jp"
),
start_html(-title=>'rpn');
HTTPレスポンスとして
Content-Type: text/html; charset=euc-jp
を出して、その後HTMLを開始しています。
最後に
print end_html;
でHTMLを閉じています。
つまり非常に古典的なPerl CGIですね。
4. 入力を取得
my $str = $in->param('value') || ' 8x^3+12x^2-2x-3 ';
$str =~ s/\s//g;
print factor($str)."\n";
ここが実質的なメイン処理です。
入力がなければ、
8x^3+12x^2-2x-3
を使います。
そして
$str =~ s/\s//g;
で空白を全部削除。
例えば
8x^3 + 12x^2 - 2x - 3
↓
8x^3+12x^2-2x-3
となります。
そして
factor($str)
です。
5. このプログラムの中心 factor()
sub factor{
my @a = arrange(shift);
ここが一番重要です。
arrange()によって多項式を配列に変換します。
例えば
8x^3+12x^2-2x-3
なら、本来、
-3 - 2x + 12x^2 + 8x^3
なので、
@a = (-3, -2, 12, 8)
となります。
つまり、
a[0] = 定数項
a[1] = xの係数
a[2] = x^2の係数
a[3] = x^3の係数
...
という設計です。
これはかなり重要なポイントです。
6. arrange() が面白い
sub arrange{
my $str = shift;
my @a = (0,0,0);
my ($b,$c);
最初は
@a = (0,0,0)
です。
つまり
定数
x
x^2
の3項分を用意しています。
x^nを取り出す
while($str =~ s/([+-]*[\d\.]*)x\^([\d\.]*)//){
$b=$2;
$c=$1;
$a[$b] += ($c =~ /^[+-]*$/) ? "$c" . "1" : $c;
}
ここはPerl正規表現の力がかなり出ています。
例えば
8x^3
に対して、
([+-]*[\d\.]*)x\^([\d\.]*)
で、
8
と
3
を取り出します。
つまり、
8x^3
↑ ↑
係数 次数
です。
そして
$a[$b] += ...
なので、
$a[3] += 8
になります。
7. 次に x の項
while($str =~ s/([+-]*[\d\.]*)x//){
$c = $1;
$a[1] += ($c =~ /^[+-]*$/) ? "$c" . "1" : $c;
}
例えば
-2x
なら、
$c = "-2"
なので、
$a[1] += -2;
です。
一方、
+x
なら係数部分は + なので、
"$c" . "1"
によって
+1
にしています。
つまり、
x
を
1x
として扱っているわけです。
8. 最後に定数
while($str =~ s/([+-]*[\d\.]{1,})//){
$a[0] += $1;
}
残った数字を定数項として処理します。
例えば
-3
なら
$a[0] += -3;
です。
9. GCDを調べる
factor()に戻ります。
if((my $i = arrayGcd(@a)) > 1){
for(@a){ $_ /= $i;}
return ed2(ed($i).factor(array2expr(@a)));
}
ここは非常に分かりやすいアルゴリズムです。
例えば、
8x^3 + 12x^2 - 2x - 6
なら係数は
8, 12, -2, -6
です。
GCDは
2
なので、
2(4x^3 + 6x^2 - x - 3)
にします。
そして、
factor(array2expr(@a))
で残った式をもう一度因数分解します。
つまりここで再帰が登場しています。
10. arrayGcd() と gcd()
sub arrayGcd{
my $ans = 0;
for(@_){ $ans = gcd($ans,$_);}
return abs($ans);
}
配列全体の最大公約数を求めます。
実際のGCDは、
sub gcd{
my ($x,$y) = @_;
return $y ? gcd($y,$x % $y) : $x;
}
です。
これは有名なユークリッドの互除法です。
例えば
gcd(12, 8)
なら、
12 % 8 = 4
8 % 4 = 0
なので、
4
です。
しかもこれも再帰になっています。
11. 3次以上の場合
return factor_div(@a) if($#a > 2);
$#a > 2ということは、配列の添字が
0,1,2,3,...
まであるので、3次以上ということです。
そこで
factor_div()
に進みます。
コメントにも、
#3次以上の時は因数定理?除算の定理?で求める
とあります。
おそらく作者自身も「これは因数定理だったかな?」という感じだったのでしょう(笑)。
実際にやっていることは、有理根を探して、その根に対応する一次因子で割るという方法です。
12. factor_div() の核心
ここです。
for my $z (1..abs($a[$#a])){
for(my $i=1;$i<=abs($a[0]);$i++){
最高次係数と定数項の絶対値を使って候補を総当たりします。
そして、
$tmp += $a[$j]*($i**$j)/($z2**$j);
によって多項式に候補となる値を代入しています。
例えば、
P(x) = 2x^3+3x^2-x-?
という多項式があったら、
P(1)
P(-1)
P(1/2)
P(-1/2)
...
を試します。
13. 0になったら因数発見
ここです。
return ed2("(".ed($z)."x".ed(0-$i).")"
.factor(array2expr(array_div($z,0-$i,@a))))
unless(sprintf("%f",$tmp)+0);
もし、
P(i/z) = 0
になれば、その値は根です。
根が
x = i/z
なら、
zx - i
が因数になります。
つまり、
P(x)
を
(zx-i) × Q(x)
に分解します。
その後、
factor(Q(x))
として、さらに因数分解。
これも再帰です。
14. array_div() は多項式の割り算
sub array_div{
my ($x,$z,@a) = @_;
my @b;
for (my $i = $#a;$i>0;$i--){
$b[$i-1]=$a[$i]/$x;
$a[$i-1]-= $z*$b[$i-1];
}
return @b;
}
これは多項式を一次式で割っています。
例えば、
P(x) ÷ (2x-1)
のような処理を、係数配列だけで行っています。
ここも非常に「数学をそのままプログラムにした」感じがあります。
15. 2次式の場合
3次以上でなければ、
return ed2("x(".ed($a[2])."x".ed($a[1]).")")
unless($a[0]);
という処理があります。
これは定数項が0の場合。
例えば、
2x^2 + 3x
なら、
x(2x+3)
とできます。
16. 2次式の因数分解
普通の
ax² + bx + c
なら、
my @a0 = measure($a[0],1);
my @a2 = measure($a[2],0);
とします。
ここで measure() が重要です。
これは約数を全部作る関数です。
17. measure() の仕組み
例えば
12
なら、
1 × 12
2 × 6
3 × 4
などを作ります。
for (my $j = int(sqrt($n)); $j > 0;$j--){
unless ($n % $j){
平方根まで調べれば、それ以降は対になるので十分、という考え方です。
例えば12なら、
sqrt(12) ≒ 3.46
なので
3
2
1
だけ調べれば、
3 × 4
2 × 6
1 × 12
が得られます。
18. そして bx+c の組み合わせを探す
2次式
ax² + bx + c
を、
(px+q)(rx+s)
とすると、
pr = a
qs = c
ps + qr = b
となります。
このプログラムはまさにそれをやっています。
if($a[1] == $b1*$c2+$b2*$c1)
つまり、
b = b1*c2 + b2*c1
になる組み合わせを探しています。
見つかったら、
return ed2(
"(" . ed($c1)."x".ed($b1).")"
. "(" . ed($c2)."x".ed($b2).")"
);
として出力します。
19. 例えば 2x²+5x+3
この場合、
a = 2
b = 5
c = 3
なので、
2 = 1 × 2
3 = 1 × 3
を使って、
(2x+3)(x+1)
を試します。
展開すると、
2x² + 2x + 3x + 3
なので、
2x² + 5x + 3
です。
プログラム中の
$b1*$c2+$b2*$c1
は、まさにこの
2 + 3 = 5
を計算しているところです。
20. array2expr() は逆変換
最初の
文字列 → 配列
が
arrange()
でした。
その逆が、
array2expr()
です。
例えば、
@a = (-3,-2,12,8)
なら、
8x^3+12x^2-2x-3
に戻します。
つまり、
arrange()
文字列 --------------------> 配列
<----------------------
array2expr()
という関係です。
この設計はかなりきれいです。
21. ed() と ed2() は表示用
例えば普通に
$a[$i]
を出すと、
1
-1
+1
などの処理が面倒です。
そこで、
sub ed{
my $n = shift;
return ($n >= 0) ? "+" . $n : $n;
}
によって、
1 → +1
2 → +2
-1 → -1
とします。
そして最後に ed2() で、
+1x
を
+x
ではなく、
x
にしたり、
+x^2
の先頭の + を消したりします。
22. ed2() のちょっと面白いところ
$str =~ s/([+-])1(x)/$1$2/g;
これで、
+1x
-1x
を、
+x
-x
にします。
さらに、
$str =~ s/^\+//;
で先頭の + を消します。
そして、
$str =~ s/\(\+/\(/g;
で、
(+2x+3)
を
(2x+3)
にします。
23. xx を処理している部分
ここは少しトリッキーです。
if ($str =~ s/xx(\^(\d+))/XX/){
$sub = $2;
}
while($str =~ s/xx/X/i){$sub++;}
$str =~ s/X/x^$sub/ ;
例えば、
x*x
ではなく、このプログラムの内部表現では、
xx
になる場合があります。
それを、
x^2
に変換しています。
つまり、因数分解結果を人間が読みやすい数学表記に整形する最後の仕上げです。
24. このプログラムの特徴
このコードを少し俯瞰すると、かなり面白い構造です。
数学部分
多項式
↓
係数配列
↓
GCD
↓
約数列挙
↓
有理根探索
↓
多項式除算
↓
再帰
Perl部分
正規表現
s///による文字列分解
配列
再帰
サブルーチン
CGI
という二つが非常にうまく組み合わされています。
25. 実は chabo-dsl ともつながる
以前見ていたあなたの chabo-dsl のASTコードと比較すると面白いです。
この factor.cgi は、
文字列
↓
正規表現
↓
係数配列
↓
数学処理
↓
文字列
という方式です。
一方、chabo-dsl は、
文字列
↓
Tokenizer
↓
Parser
↓
AST
↓
Evaluator
です。
つまり、
factor.cgi は「正規表現+配列」で数式を理解している。
chabo-dsl は「Tokenizer+Parser+AST」で数式を理解している。
という違いがあります。
そして、この factor.cgi の
arrange()
は、ある意味では非常に原始的な
「数式を解析して内部表現に変換するParser」
なんですよね。
ただしASTではなく、
@a = (定数項, x係数, x²係数, ...)
という係数配列そのものを内部表現にしている。
ここがこのスクリプトの一番面白いところだと思います。
全サブルーチンを役割で分類すると
| サブルーチン | 役割 |
|---|---|
factor |
全体の因数分解制御 |
factor_div |
3次以上の因数分解 |
array_div |
多項式の除算 |
arrange |
文字列 → 係数配列 |
measure |
約数の列挙 |
array2expr |
係数配列 → 数式 |
arrayGcd |
係数のGCD |
gcd |
ユークリッドの互除法 |
ed |
数値を符号付き文字列へ |
ed2 |
数式文字列の最終整形 |
個人的には、このコードは**「昔のPerlらしい、数学アルゴリズムをそのままコードにしたプログラム」**という感じが強いです。
特に arrange → factor → factor_div → array_div → factor の流れは、あなたが以前見ていたASTコードを理解するうえでも比較対象としてかなり面白いと思います。