中置記法から後置記法（逆ポーランド記法）への変換と計算

  Calculation and conversion to postfix notation (Reverse Polish Notation) from infix notation

perlでは入力内容をevalすれば良いだけだけどアルゴリズム(algorithm)の備忘録として書いてみた。

  使い方

$ perl calc.pl "((1+5)*(-2+-3) * -1)**2 % 8"
4$
$ perl calc.pl "6/2(1+2)"
1$

【計算】

  [calc.pl]

use strict;
my $op = { '-' => [sub {$_[1] - $_[0]},1],
           '+' => [sub {$_[1] + $_[0]},1],
           '*' => [sub {$_[1] * $_[0]},2],
           '/' => [sub {$_[1] / $_[0]},2],
           '%' => [sub {$_[1] % $_[0]},2],
           '**' => [sub {$_[1] ** $_[0]},3],
           'x' => [sub {$_[1] * $_[0]},9], # 多項式対応？
           '(' => [sub { },0],
       };
# 中置記法の引数をスペースで分割し後置記法に変換し計算を行う
print calc(infix_to_postfix(split (/\s+/,adjust(pop))));

sub infix_to_postfix{      # 中置記法を後置記法に変換
    my @post = ();                                                     # 後置記法用スタック
    my @opr = ();                                                      # 演算子用のワークスタック
    for ('(',@_,')'){                                                  # 中置記法の要素をカッコでくくり（処理を単純にする為）先頭から最後まで処理を行う。
        if ($_ eq ")"){                                                # 要素が閉じカッコの場合
            push @post,pop @opr while( @opr && $opr[-1] ne "(" );      #     開きカッコまで演算子用スタックから要素を取出し後置記法用スタックに積む。
            pop @opr;                                                  #     開きカッコを読み捨てる。
        }elsif(exists $op->{$_}){                                      # 要素が演算子の場合
                                                                       #     要素が開きカッコでなく要素のプライオリティが低い間、
                                                                       #     演算子スタックを取出し後置記法用スタックに積む。
            push @post,pop @opr while($_ ne "(" && @opr && $op->{$_}->[1] <= $op->{$opr[-1]}->[1]);
            push @opr,$_;                                              #     要素を演算子スタックに積む。
        }else{                                                         # 要素が演算子以外の場合
            push @post,$_;                                             #     要素を後置記法用スタックに積む。     
        }
    }
    return @post;                                                      # 後置記法用スタックを返却する。
}
sub calc {                 # 逆ポーランド記法の計算
    my @stack = ();
                                                                       # 1.逆ポーランド記法の要素を先頭から最後まで処理を行う。
                                                                       # 2.要素が演算子の場合にスタックから２つの要素を取出し計算結果をスタックに積む。
                                                                       # 3.要素が演算子でない場合に要素をスタックに積む。
    push @stack,(exists $op->{$_} ?  $op->{$_}->[0](pop @stack,pop @stack) : $_) for @_;
    return pop @stack;                                                 # スタックから要素を取出し返却する。
}
sub adjust{
    my $text = shift;
    $text =~ s{([\-\+\*\/\%\(\)x])}{ $1 }g;
    $text =~ s{\s+}{ }g;
    $text =~ s{\* \*}{\*\*}g;
    $text =~ s{(\D\s+)\- (\d)}{$1 -$2}g;
    $text =~ s{([\d\)]\s+)\(}{$1 x (}g;    # 多項式対応？
    return $text;
}