Hello Wor.log

IT系大学生4人による備忘録のようなもの

ICPC計算機

競技プログラミング C ICPC

こんにちは。CPPXのCです。

ICPCも近いということで、今日はICPCの過去問であるICPC計算機を解いてみることにしました。（実際にこの記事が公開されるのはいつになっているかわかりませんが…）
ICPCというのは国際大学対抗プログラミングコンテストのことで、実際にはJavaかC++を使わなければならないのですが
今回からPython2、Python3も対応となりました。
慣れた言語でアルゴリズムを先に考えてみるということでPythonで解いてみました。

概要

問題はこちらです。

ICPC Calculator | Aizu Online Judge

今回の問題は、カッコを使わない新しい数学の計算記法から計算結果を導出せよというもの。 新しい記法は加算演算子 (+)、乗算演算子 (*)、あるいは整数からなる行を並べて式を表し、式は整数ひとつか被演算子への演算子の適用のどちらかで表されます。演算子の適用の場合は、演算子の行を先に書き、直後の行から演算子が適用されるふたつ以上の被演算子を並べて書くことで表現されます。

式はいくらでも入れ子になるので、どの演算子がどの被演算子に適用されるのかをわかるようにしなければなりません。 そのためには式には入れ子レベルを考える必要があります。最上位の式は入れ子レベル 0 とし、 レベル n の式が演算子適用の場合、その被演算子はレベル n + 1 の式になるように記します。 式の最初の行は入れ子レベルの数だけのピリオド (.) から始めることで深度を表現しています。

つらつらと書きましたが具体的に見たほうが理解が早いと思うので具体例を以下に示すこととします。 たとえば、通常の数学では 2 + ３ と表記するような式の場合は以下のように記すことができます。

+
.2
.3

また、通常の数学で (2 + 3 + 4) * 5 と示すような式は以下のようになります。

*
.+
..2
..3
..4
.5

解法

解き方を考えてみます。
入力を眺めてみると、基本的には後ろに行くほど階層が深くなっていることがわかります。演算子の直後では必ず階層が変化するので、演算子を見つけたらその直後の被演算子を計算すればいいということになります。

しかし、プログラムではそう単純ではありません。先頭から順番に計算してしまうと、被演算子に演算子が出現してしまうことがあります。これは浅い階層から計算しようとしているからです。
したがって、この問題を解くためには後ろから計算し、深い階層の演算を先に済ませて数値としてしまう必要があります。

そこで、入力された式を後ろから計算してみることにします。演算子が見つかるまでは数値をストックし、演算子が出現したらストックの中から一つ下の階層の数値をさがし、演算します。演算子は二種類しかなく、乗算と加算のみなので、あまり深く考えずに場合分けすればよさそうです。演算子のあとは必ず被演算子が出現し、後ろから見る限りは同じ階層の演算が複数でてきてしまうことはないので、これで計算できそうです。

要は深い階層から順番に演算子を探し、被演算子になっている演算子を計算済みの数値に変えてしまおうということです。

ソースコードは以下のようになりました。

import re

while True:
    N = int(input())
    if N == 0:
        break
    input_list = [input() for i in range(N)]
    stack = []

    for i in reversed(input_list):
        if re.match("\.*(\*|\+)", i):
            # 演算子が出てきたら処理　それまではスタックに数字を突っ込み続ける
            operator = re.sub("\.*", "", i)
            depth = i.count(".")
            if operator == "+":
                tmp_num = 0
            else:
                tmp_num = 1
            for s in reversed(stack):
                # 今までつっこんだ中から一つ深い層を全部取り出して計算する
                if re.match("." * (depth + 1) + "\d", s):
                    num = int(re.sub("\.*", "", s))
                    if operator == "+":
                        tmp_num += num
                    else:
                        tmp_num *= num
                    stack.pop()
            stack.append("." * depth + str(tmp_num))
        else:
            stack.append(i)

    print(stack[0])

まずは入力されたリストを後ろから見ていき、演算子が出てくるまでは数値をストックし続けます。 演算子を見つけたら演算子の深さを . の数から調べ、保存しています。その後、演算子の種類によりストック済みの数値のうち演算子より一つ深い階層にある数値を演算、演算子があった位置に演算子の代わりにその結果を入れなおします。 これを繰り返すことにより演算子をすべて消化し答えがでるというわけです。

結構悩んでしまった…