読者です 読者をやめる 読者になる 読者になる

逆ポーランド記法を使って四則演算を行なう

perl アルゴリズム

配列に入っている式から四則演算行なうプログラムをperlで書いてみました。
演算子とカッコの優先度を考慮しながら計算するために、逆ポーランド記法に直して計算するようにしています。

use strict;
use warnings;

{
    cal(qw|5 + 4 - 3|);
    cal(qw|5 + 4 * 3 + 12 / 6|);
    cal(qw|1 + ( 2 + 3 ) * 4|);
    cal(qw|( 1 + 4 ) * ( 3 + 7 ) / 5|);
    cal(qw|( ( 2 + 3 ) + 3 * 2 ) - 3 * 2|);
}


sub cal {
    my @exp = @_;

    my @post = convert_to_postfix(@exp);
    print "exp: ", join(' ',@exp),"\n";
    print "postfix: ", join(' ',@post), "\n";
    print "answer: ", cal_for_postfix(@post), "\n";
    print "\n";
}


sub convert_to_postfix {
    my @exp = @_;

    my @postfix = ();
    my @op = ();

    #print join(' ', @exp), "\n=================\n";                             
    for my $e (@exp) {
        if ($e =~ /\+|\-/) {
            if ($op[$#op] && $op[$#op] =~ /\*|\//) {
                my $o = pop @op;
                push @postfix, $o;
                push @postfix, $e;
            } else {
                push @op, $e;
            }
        } elsif ($e =~ /\*|\//) {
            push @op, $e;
        } elsif ($e eq ')') {
            while (my $op2 = pop @op) {
                if ($op2 eq '(') {
                    if (@op) {
                        if ($op[$#op] && $op[$#op] =~ /(\*|\/)/) {
                            my $op3 = pop @op;
                            push @postfix, $op3;
                        }
                    }
                    last;
                } else {
                    push @postfix, $op2;
                }
            }
        } elsif ($e eq '(') {
            push @op, $e;
        } else {
            push @postfix, $e;
        }
        #print "postfix: ",join(' ', @postfix), "\n";                            
        #print "op: ",join(' ', @op), "\n";                                      
        #print "\n";                                                             
    }

    while (my $o = pop @op) {
        push @postfix, $o;
        #print "postfix: ",join(' ', @postfix), "\n";                            
        #print "op: ",join(' ', @op), "\n";                                      
        #print "\n";                                                             
    }

    return @postfix;
}



sub cal_for_postfix {
    my @list = @_;

    my @stack = ();
    for my $l (@list) {
        if ($l =~ /\+|\-|\*|\//) {
            @stack = pop_and_cal($l, @stack);
        } else {
            push @stack, $l;
        }
    }

    return $stack[0];
}


sub pop_and_cal {
    my $op = shift;
    my @stack = @_;

    my $b = pop @stack;
    my $a = pop @stack;

    if ($op eq '+') {
        push @stack, $a + $b;
    } elsif ($op eq '-') {
        push @stack, $a - $b;
    } elsif ($op eq '*') {
        push @stack, $a * $b;
    } elsif ($op eq '/') {
        push @stack, $a / $b;
    }

    return @stack;
}

表示結果はこちら。

exp: 5 + 4 - 3
postfix: 5 4 3 - +
answer: 6


exp: 5 + 4 * 3 + 12.3 / 6
postfix: 5 4 3 * + 12.3 6 / +
answer: 19.05


exp: 1 + ( 2 + 3 ) * 4
postfix: 1 2 3 + 4 * +
answer: 21


exp: ( 1 + 4 ) * ( 3 + 7 ) / 5
postfix: 1 4 + 3 7 + * 5 /
answer: 10


exp: ( ( 2 + 3 ) + 3 * 2 ) - 3 * 2
postfix: 2 3 + 3 2 * + 3 2 * -
answer: 5


バグがありそうで、結構不安です^^;