中置記法から逆ポーランド記法への変換

中置記法から逆ポーランド記法への変換 - みずぴー日記 にインスパイヤされて awk で中置記法から逆ポーランド記法への変換を行います。 awk ユーザーにとっての経典でもある『Amazon.co.jp： プログラミング言語AWK (新紀元社情報工学シリーズ): A. V. エイホ, P. J. ワインバーガー, B. W. カーニハン, Alfred V. Aho, Peter J. Weinberger, Brian W. Kernighan, 足立 高徳: 本』に既に中置記法の計算方法は記載されていますし、今でも同書籍のサンプルはここから入手することができます。

#! /usr/local/bin/nawk -f
# infix2rep.awk
# 中置記法から逆ポーランド記法への変換
# usage: nawk -f infix2rep.awk

BEGIN {
    print infix2rep("( 1 + 2 / 2 ) - ( 3 + 4 * 5 )");
}

# infix2rep():  中置記法から逆ポーランド記法への変換
#   in:     数式 (eqn)
#   out:    expr
function infix2rep(eqn) {
    num_term = split(eqn, term, /[ ]+/);
    i = 1;
    return expr();
}

# Ref: 『プログラミング言語AWK』
#       Alfred V.Aho (著), Brian W.Kernighan (著), Peter J.Weinberger (著)
# Ref: http://cs.bell-labs.com/cm/cs/who/bwk/awkcode.txt - calc3
function expr(    e) {
    e = terms();
     while (term[i] == "+" || term[i] == "-") {
        e = term[i++] == "+" ? e " " terms() " +" : e " " terms() " -";
    }
    return e;
}

function terms(    e) {
    e = factor();
    while (term[i] == "*" || term[i] == "/") {
        e = term[i++] == "*" ? e " " factor() " *" : e " " factor() " /";
    }
    return e;
}

function factor(    e) {
    if (term[i] ~ /^[+-]?([0-9]+[.]?[0-9]*|[.][0-9]+$)/) {
        return term[i++];
    } else if (term[i] == "("){
        i++;
        e = expr();
        i++;
        return e;
    } else {
        return 0;
    }
}

実行してみましょう。

$ nawk -f infix2rep.awk
1 2 2 / + 3 4 5 * + -

このように逆ポーランドに変換されました。

ちなみに awk では Kenny McCormack が作った中置記法電卓が有名で、これを xgawk の MPFR 拡張で書き直したものはOSC2008 Tokyo/Spring :: Calculator に置いてありますので、参考にしてみてください。