0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

calc.pl 逆ポーランド記法への変換と計算

0
Posted at

全体像

このスクリプトは 「中置記法(普通に書く算術式)」 → 「後置記法(逆ポーランド記法)」 に変換したうえで、
その後置記法をスタックマシン方式で評価し、結果を標準出力に出すだけの ミニ電卓 です。

  • adjust : 入力文字列に空白を入れ、演算子のトークン化を正しく行えるように整形
  • infix_to_postfix : Shunting‑yard アルゴリズム(演算子スタックと出力スタック)で中置 → 後置へ変換
  • calc : 逆ポーランド記法を スタック評価 して数値を求める
  • $op : 演算子の 動作・優先順位・結合性・引数数 をハッシュリファレンスにまとめたテーブル

1. 演算子テーブル $op

my $op = {
    '-'   => [ sub { $_[1] - $_[0] }, 1, 'L', 2 ],
    '+'   => [ sub { $_[1] + $_[0] }, 1, 'L', 2 ],
    '*'   => [ sub { $_[1] * $_[0] }, 2, 'L', 2 ],
    '/'   => [ sub { $_[1] / $_[0] }, 2, 'L', 2 ],
    '%'   => [ sub { $_[1] % $_[0] }, 2, 'L', 2 ],
    'NGE' => [ sub { -$_[0]        }, 3, 'R', 1 ],   # 単項マイナス (Negative)
    '**'  => [ sub { $_[1] ** $_[0]}, 4, 'R', 2 ],
    'x'   => [ sub { $_[1] * $_[0] }, 2, 'L', 2 ],   # 多項式で暗黙の掛け算を許す
    '('   => [ sub { },               0, 'L', 2 ],   # カッコは演算子としては無視
};
項目 意味
キー 演算子文字列(-、+、** など)
0 実際の計算を行うコードリファレンス。引数は スタックから pop した順番($_[0] が右側、$_[1] が左側)。
1 優先順位(数が小さいほど低い)。+ と - が 1、* / % が 2、単項マイナスが 3、べき乗が 4。
2 結合性(L = left‑associative, R = right‑associative)。
3 必要なオペランド数。単項マイナスは 1 個、他は 2 個。

ポイント

  • NGE は「Negative (Unary)」の略で、- が単項マイナスとして現れたときだけ使われます。
  • x は * と同じ意味だけど、2x や 3(x+1) のように 暗黙の掛け算 を許すために入れられたものです。
  • ( は優先順位 0 でスタック上に置かれ、括弧の閉じ時に 捨てられ ます。

2. 入力文字列の前処理 adjust

sub adjust{
    my $text = shift;
    $text =~ s{([\-\+\*\/\%\(\)x])}{ $1 }g;   # 演算子の前後に必ず空白を入れる
    $text =~ s{\s+}{ }g;                     # 連続空白を 1 つに
    $text =~ s{\* \*}{\*\*}g;                # **(べき乗)を元に戻す
    $text =~ s{([\d\)]\s+)\(}{$1 * (}g;       # 2(3+4) → 2 * (3+4)  …多項式対応?
    return $text;
}
  1. 演算子を空白で囲む
    3+4*5 → 3 + 4 * 5 になるので、split /\s+/ だけでトークン化できる。
  2. 余分な空白は 1 個にまとめる。
  3. ** が * * に分割されるのを防ぐために * * → ** に戻す。
  4. 数字または閉じ括弧の直後に開き括弧が来たら暗黙の掛け算 * を挿入する。
    • 例: 2(3+4) → 2 * ( 3 + 4 )

adjust が返す文字列は 空白で区切ったトークン列 になるので、次の行で

split /\s+/, adjust(pop)

とすれば配列 @tokens が得られます。


3. 中置 → 後置変換 infix_to_postfix

sub infix_to_postfix{
    my @post = ();   # 出力スタック(後置記法の列)
    my @opr  = ();   # 演算子スタック
    my $prev = 'START';

    for ('(', @_, ')') {                # 入力の前後に '(' と ')' を付けて簡単化
        if ($_ eq ')') {                # 閉じ括弧
            push @post, pop @opr while @opr && $opr[-1] ne '(';
            pop @opr;                  # '(' を捨てる
        }
        elsif (exists $op->{$_}) {      # 演算子
            my $cur = $_;

            # ------------------------------
            # 1️⃣ 単項マイナスかどうかの判定
            #    前トークンが START, '(' , OP のときは
            #    たとえば   -3  ( - ( 5 )  + 2 )
            #    の最初の - を単項マイナス (NGE) に置き換える
            # ------------------------------
            if ($cur eq '-' && ($prev eq 'START' || $prev eq '(' || $prev eq 'OP')) {
                $cur = 'NGE';
            }

            # ------------------------------
            # 2️⃣ 優先順位比較 (Shunting-yard)
            #    $cur の優先順位がスタックトップより低い、または
            #    同じ優先順位で左結合 (L) のときはスタックから pop して
            #    出力側に移す
            # ------------------------------
            push @post, pop @opr
                while $_ ne '(' && @opr && juge_priority($cur, $opr[-1]);

            push @opr, $cur;          # 現在の演算子をスタックに積む
            $prev = 'OP';
        }
        else {                          # オペランド(数値・変数など)
            push @post, $_;
            $prev = 'NUM';
        }
    }
    return @post;
}

3‑1. ループの開始と終端

for ('(', @_, ')') { ... }
  • 入力トークン列 @_ の 前後に '(' と ')' を付加 することで、
    • 文字列が 3 + 4 のだけでも必ず「開始‐括弧」から処理が始まり、
    • 「終了‐括弧」までで必ず演算子スタックが空になることが保証されます。

3‑2. 単項マイナスの判定

if ($cur eq '-' && ($prev eq 'START' || $prev eq '(' || $prev eq 'OP')) {
    $cur = 'NGE';
}
  • - が 「演算子の直前」 ではなく 「項の先頭」 に来たときだけ単項マイナスに変換します。
  • 判定に使う $prev は直前のトークンの種別を示す文字列です。
    • START : 式の冒頭(左側に何も無い)
    • ( : 開き括弧の直後
    • OP : 直前が別の演算子(例: * - 5)

3‑3. 優先順位・結合性の比較 juge_priority

sub juge_priority {
    $op->{$_[0]}->[2] eq 'R'   # 右結合か?
        ? $op->{$_[0]}->[1] <  $op->{$_[1]}->[1]   # 低ければ pop
        : $op->{$_[0]}->[1] <= $op->{$_[1]}->[1];  # 左結合は同順位でも pop
}
  • 右結合(例: **)は 「現在の演算子の優先順位がスタックトップより低い」 ときだけスタックをポップ。
  • 左結合(例: + - * /)は 「同順位でもスタックトップが先に出る」 ので <= で判定します。

3‑4. 閉じ括弧の処理

if ($_ eq ')') {
    push @post, pop @opr while @opr && $opr[-1] ne '(';
    pop @opr;  # '(' を捨てる
}
  • ) が現れたら、直前の ( が出てくるまでスタックから演算子をすべて出力側へ移す。
  • ( 自体は出力列に 入れません(演算子テーブルにエントリはあるが、評価時には無視されます)。

4. 後置記法の評価 calc

sub calc {
    my @stack = ();

    push @stack,
        (exists $op->{$_}
            ? $op->{$_}->[3] == 1
                ? $op->{$_}->[0] (pop @stack)               # 単項演算子
                : $op->{$_}->[0] (pop @stack, pop @stack)   # 2 項演算子
            : $_)                                            # オペランドはそのまま
        for @_;
    return pop @stack;
}

4‑1. 1 行で書かれた「スタック評価ロジック」

  • for @_ で後置記法のトークンを左から右へ順に走査。
  • 演算子かどうかは exists $op->{$_} で判定。
  • 演算子ならテーブルの 第 4 要素 (->[3]) がオペランド数を示すので、
    • 1 → 単項(pop @stack で 1 個取り出す)
    • 2 → 二項(pop @stack, pop @stack で 2 個取り出す)
  • 取り出したオペランドは 右から左 の順序で sub に渡されることに注意($_[1] が左、$_[0] が右)。
  • 演算子でなければ そのまま数値(文字列) をスタックに push。

4‑2. 結果の取得

最後に pop @stack すれば、スタックに残っている唯一の要素=演算結果です。


5. スクリプトのエントリポイント

print calc(
    infix_to_postfix(
        split /\s+/,                     # 空白区切りでトークン列化
        adjust(pop)                     # 標準入力の 1 行だけを整形
    )
);
  1. pop → 標準入力 から 1 行だけ読む(<> の代わりに pop が使われている)。
  2. adjust でトークン化しやすい形に整形。
  3. split /\s+/ で空白区切りの配列に変換。
  4. その配列を infix_to_postfix に渡し、後置記法の配列を得る。
  5. さらにそれを calc に渡して評価し、print で結果を出力。

実行例

$ echo "3 + 4 * 2 / ( 1 - 5 ) ** 2 ** 3" | perl simple_calc.pl
3.0001220703125

6. 各部の細かいポイントと注意点

部位 ポイント 注意・改善点
$op の NGE 単項マイナスを別演算子として扱うことで、-3^2 が (-3)^2 になるようにしている。 - が二項なのか単項なのか判定は前トークンだけで決めている。文字列 '(-5)' のように空白が無くても正しく判定できる。
x 演算子 暗黙の掛け算を許すためのエイリアス。adjust の最後の置換で 2(3+4) → 2 * (3+4) に変換しているので、実際に x が使われるケースは少ない。 多項式を扱う意図があるなら、変数名(a, b など)への対応は未実装。
adjust の正規表現 簡潔に空白挿入・削除・暗黙掛け算補完を実装。 * と ** の置換は \* \* → ** のみで、***(* と ** が混ざるケース)には弱い。
juge_priority 結合性と優先順位の判定が一行で完結。 名前が juge...(typo)になっているが、機能には問題なし。
infix_to_postfix のループ 最初と最後に ( と ) を付加し、終端処理の特別ケースを省いている。 ( がスタックに残らない保証は for ('(', @_, ')') があるので安全。
calc の実装 演算子のオペランド数で pop の回数を切り替えているので、拡張が容易(たとえば三項演算子 ?:)でも追加できる。 pop @stack の戻り値は文字列になることがあるので、数値として評価したい場合は +0 で数値化しても良い。
エラーハンドリング 無し。入力が正しいこと前提。 整数除算の % は 0 除算エラー時に Division by zero が致命的に死ぬ。
数値リテラルの形式 整数・実数のどちらでも文字列としてスタックに入れ、演算時に Perl の自動型変換で数値になる。 指数 ** で負の指数や非整数指数を使うと 浮動小数点 になるので、結果が期待どおりか確認が必要。

7. 具体的な実行フロー(例:-3 + 4 * (2 - 1))

ステップ 処理 スタック・配列の状態
① adjust -3 + 4 * ( 2 - 1 )(空白が入る)
② split ('-3','+','4','*','(','2','-','1',')')
③ infix_to_postfix ('NGE','3','4','2','1','-','*','+')(後置記法)
④ calc スタック操作(NGE → -3、4 2 1 - * → 4 * (2-1))
⑤ 結果 1 がスタックに残り print → 1

8. まとめ

  • 演算子テーブルに「実装コード・優先順位・結合性・引数数」を集約し、
    Shunting‑yard で 中置 → 後置、スタック評価で 結果取得という古典的構造を、Perl のコードリファレンスと配列操作だけで実装しています。
  • 単項マイナスの判定や 暗黙の掛け算(2(3+4))といった、算術式でよく見かける曖昧さを トークン整形と 前処理で解決しています。
  • 1 行で完結した calc の実装は、オペランド数がテーブルで管理されているため演算子の増減が容易。
  • 改善点としてはエラーハンドリング、変数や関数のサポート、そして正規表現のロバスト化(*** など)がありますが、「最小限の機能だけで動く」 という目的に対しては十分にシンプルで読みやすいコードです。

この解説が コードの動き と 各部の役割 を把握する手助けになれば幸いです。もし実装の拡張やテスト例が必要であれば遠慮なく聞いてください。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?