逆ポーランド記法で与えられた数式の計算結果を出力するアルゴリズムの実装

逆ポーランド記法

逆ポーランド記法（Reverse Polish Notation, RPN）とは、数式の記述方法で、演算子を被演算子の後に記述する表記法である。日本語では、後置記法とも呼ばれたりする。この記法は、演算の優先順位を指定する括弧が不要な点が特徴のひとつである。

たとえば、(1＋5) * (2+3)は、次のように記述する。

1 5 + 2 3 + *

演算子

演算子は、数式やコンピュータプログラミング言語などで、各種の演算を表わす記号・シンボルである。演算とは、計算をすること。

オペランド

オペランドとは、数式を構成する要素のうち、演算の対象となる値や変数、定数などのこと。プログラミングの分野ではこれに加えて、プログラム中の個々の命令・処理の対象となるデータや、データの所在情報などのこともオペランドという。

具体例

■入力
１つの数式が１行に与えられます。連続するシンボル（オペランドあるいは演算子）は１つの空白で区切られて与えられます。

■出力
計算結果を１行に出力してください。

■制約
2 ≤ 式に含まれるオペランドの数 ≤ 100
1 ≤ 式に含まれる演算子の数 ≤ 99
演算子は +、-、* のみを含み、１つのオペランドは106 以下の正の整数
-1 × 109 ≤ 計算途中の値 ≤ 109

use strict;
use warnings;
use utf8;
binmode(STDOUT, ":utf8");

&main;

sub main {
    print "逆ポーランド記法で数式を入力してください。\n";
    # reverse polish notation, rpn
    my $input_rpn = <STDIN>;

    chomp($input_rpn);
    my @input_rpn_arr = split(/ /, $input_rpn);

    my $calc_end_result = &stack_algorithm(@input_rpn_arr);
    print $calc_end_result;
}

sub stack_algorithm {
    my @input_rpn_arr = @_;
    $\="\n";

    my $cnt_rpn_arr = $#input_rpn_arr + 1;
    my @int_tmp;

    for (my $i = 0; $i < $cnt_rpn_arr; $i++) {
        push (@int_tmp, $input_rpn_arr[$i]);

        if ($input_rpn_arr[$i] eq '+' || $input_rpn_arr[$i] eq '-' || $input_rpn_arr[$i] eq '*') {
            my $operator = pop (@int_tmp);
            my $operand_1 = pop (@int_tmp);
            my $operand_2 = pop (@int_tmp);

            my $calc_result = &calculate($operator, $operand_2, $operand_1);
            push (@int_tmp, $calc_result);
        }
    }
    my $calc_end_result = $int_tmp[0];
    return $calc_end_result;
}

sub calculate {
    my ($operator, $operand_2, $operand_1) = @_;
    my $calc_result;

    if ($operator eq '+') {
        $calc_result = $operand_2 + $operand_1;
    }
    if ($operator eq '-') {
        $calc_result = $operand_2 - $operand_1;
    }
    if ($operator eq '*') {
        $calc_result = $operand_2 * $operand_1;
    }

    return $calc_result;
}

[hogefuga@data_structure]$ perl stack.pl
逆ポーランド記法で数式を入力してください。
1 2 +
3
[hogefuga@data_structure]$ perl stack.pl
逆ポーランド記法で数式を入力してください。
1 2 + -6 3 * *
-54

参考
C#:逆ポーランド記法を利用した数式の計算(1) 逆ポーランド記法の計算