逆ポーランド記法による数式処理

逆ポーランド記法とは

逆ポーランド記法(Reverse Polish Notation: RPN)は、演算子をオペランドの後に記述する数式やプログラムの記法の一つです。

例えば、一般的な中間記法で記述された数式 (1+2)*(5+4) は逆ポーランド記法では 1 2 + 5 4 + * と記述されます。

逆ポーランド記法では、中間記法で必要とされた括弧が不要であり、また式の計算(評価) の実装が容易であるためコンピュータでの利用に適しています。

演算子を被演算子の後ろに置くことから、後置記法 (Postfix Notation) とも言うらしいです。

逆ポーランド記法で表された数式の評価

実装にはスタックを用います。

先頭から順に記号を読み込み、その記号が演算子以外であればスタックに値を積み、演算子であればスタックから値を2つ取り出して演算結果をスタックに積む、という簡単な操作の繰り返していき、最後にスタックの中に残った値が答えとなります。

AOJ 0087: Strange Mathematical Expression

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0087

試しにこの問題を解いてみましょう。

• C++による解答例

#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <cstdlib>
#include <cctype>
#include <cstdio>

using namespace std;

int main()
{
    string s;
    stack<double> St;
    double a, b;
    while (getline(cin, s)) {
        stringstream ss(s);

        while (ss >> s) {
            if (s == "+") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a+b);
            }
            else if (s == "-") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a-b);
            }
            else if (s == "*") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a*b);
            }
            else if (s == "/") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a/b);
            }
            else {
                St.push(atoi(s.c_str()));
            }
        }
        printf("%.6f\n", St.top());
        St.pop();
    }
    return 0;
}   

• Pythonによる解答例

# coding: utf-8

def Calculate_RPN(L):
    St = []
    for i in L:
        if i == '+':
            b, a = float(St.pop()), float(St.pop())
            St.append(a+b)
        elif i == '-':
            b, a = float(St.pop()), float(St.pop())
            St.append(a-b)
        elif i == '*':
            b, a = float(St.pop()), float(St.pop())
            St.append(a*b)
        elif i == '/':
            b, a = float(St.pop()), float(St.pop())
            St.append(a/b)
        else:
            St.append(i)

    return St[0]


while True:
    try:
        s = raw_input().split()

    except EOFError:
        break

    print Calculate_RPN(s)

中間記法で記述された数式を逆ポーランド記法に変換する

この変換もスタックを用いて行うことが出来ます。

次のような手順で変換できます。

ほぼここ(http://knowledge.sakura.ad.jp/etc/220/)に書いてあることのコピペ。

• 数式を左から順に読み込む
• 数値だったら出力（だったらスタックに積む ）だったらスタック上の演算子を（が出てくるまで出力し（と）は削除する
• 演算子だったらスタックに積む
  • スタックトップの演算子の優先順位がスタックに積まれる演算子より高ければそれを出力する
• 数式を最後まで読み込んだ後、スタック上に演算子が残っていればそれをスタックが空になるまで順に出力する

逆ポーランド記法では演算子の優先順位は左に行くほど高くなります。

中間記法の数式を左から読み込んでいき演算子をスタックに積んだとき、+と-や*と/などの同じ優先順位のものは先にスタックに入っているものの方が当然優先順位は高くなります。(中間記法では同じ優先順位なら左から計算が行われるから) (それはそう)

空白区切りなしで中間記法で表された数式1行が与えられ逆ポーランド記法に変換したものを出力するプログラムは次のように書けます。

動けばいいやと思って書いたクッソ汚いコードなのであまり参考にしないほうが良いと思います。

• C++

#include <iostream>
#include <string>
#include <stack>
#include <map>
#include <cstdlib>
#include <cctype>

using namespace std;

void str2arr(string s, string A[]) {
    int n = 0;
    string tmp = "";

    for (int i = 0; s[i] != '=' ; i++) {
        if ('0' <= s[i] && s[i] <= '9') {
            tmp += s[i];
        }
        else {
            if (tmp != "") { 
                A[n++] = tmp;
                tmp = "";
            }
            A[n++] = s[i];
        }
    }
    if (tmp != "") { A[n++] = tmp; }
    A[n++] = "=";
}

void Generate_RPN(string A[], string B[]) {
    map<string, int> table;
    stack<string> St;
    table["*"] = 1;
    table["/"] = 1;
    table["+"] = 0;
    table["-"] = 0;
    table["("] = -1;
    table[")"] = -1;

    int j = 0;
    for (int i = 0; A[i] != "="; i++) {
        if ('0' <= A[i][0] && A[i][0] <= '9') {
            B[j++] = A[i];
        }
        else if (A[i] == "(") {
            St.push(A[i]);
        }
        else if (A[i] == ")") {
            while (St.top() != "(") {
                B[j++] = St.top(); St.pop();
            }
            St.pop();
        }
        else {
            while ((!St.empty()) && (table[St.top()] >= table[A[i]])) {
                B[j++] = St.top(); St.pop();
            }
            St.push(A[i]);
        }
    }
    while (!St.empty()) {
        B[j++] = St.top(); St.pop();
    }
    B[j] = "=";
}

int main() {
    string A[100], B[100];
    string s;

    cin >> s;
    s += "=";

    str2arr(s, A);
    Generate_RPN(A, B);

    for (int i = 0; B[i] != "="; i++) {
        cout << B[i];
        cout << (B[i+1] == "=" ? "\n" : " ");
    }

    return 0;
}

• Python

# coding: utf-8

# Convert String to List
def String2List(s):
    L = []; tmp = ""
    for i in s:
        if i.isdigit():
            tmp += i
        else:
            if tmp != "":
                L.append(tmp)
                tmp = ""
            L.append(i)
    if tmp != "":
        L.append(tmp)

    return L

# generate Reverse Polish Notation
def Generate_RPN(L):
    S, L2 = [], []
    table = {"*": 1, "/": 1, "+": 0, "-": 0, "(": -1, ")": -1}
    for i in L:
        if i.isdigit():
            L2.append(i)
        elif i == "(":
            S.append(i)
        elif i == ")":
            while S[-1] != "(":
                L2.append(S.pop())
            S.pop()
        else:
            while len(S) != 0 and (table[S[-1]] >= table[i]):
                L2.append(S.pop())
            S.append(i)

    while len(S) != 0:
        L2.append(S.pop())

    return L2

s = raw_input()
print " ".join(Generate_RPN(String2List(s)))

中間記法で記述された数式を評価する

先に書いた2つのコードを組み合わせれば中間記法で記述された数式の評価が出来ます。

AOJ0109: Smart Calculator

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0109&lang=jp

この問題を解いてみましょう。

C++で逆ポーランド記法の数式を評価するとき全てdoubleで計算して最後にintにキャストするみたいにやったら Wrong Answer が出て辛かったです。

• C++による解答例

#include <iostream>
#include <string>
#include <stack>
#include <map>
#include <cstdlib>
#include <cctype>

using namespace std;

void str2arr(string s, string A[]) {
    int n = 0;
    string tmp = "";

    for (int i = 0; s[i] != '=' ; i++) {
        if ('0' <= s[i] && s[i] <= '9') {
            tmp += s[i];
        }
        else {
            if (tmp != "") { 
                A[n++] = tmp;
                tmp = "";
            }
            A[n++] = s[i];
        }
    }
    if (tmp != "") { A[n++] = tmp; }
    A[n++] = "=";
}

void Generate_RPN(string A[], string B[]) {
    map<string, int> table;
    stack<string> St;
    table["*"] = 1;
    table["/"] = 1;
    table["+"] = 0;
    table["-"] = 0;
    table["("] = -1;
    table[")"] = -1;

    int j = 0;
    for (int i = 0; A[i] != "="; i++) {
        if ('0' <= A[i][0] && A[i][0] <= '9') {
            B[j++] = A[i];
        }
        else if (A[i] == "(") {
            St.push(A[i]);
        }
        else if (A[i] == ")") {
            while (St.top() != "(") {
                B[j++] = St.top(); St.pop();
            }
            St.pop();
        }
        else {
            while ((!St.empty()) && (table[St.top()] >= table[A[i]])) {
                B[j++] = St.top(); St.pop();
            }
            St.push(A[i]);
        }
    }
    while (!St.empty()) {
        B[j++] = St.top(); St.pop();
    }
    B[j] = "=";
}

int Calculate_RPN(string s[]) {
    stack<double> St;
    double a, b;

    for (int i = 0; s[i] != "="; i++) {
        if (s[i] == "+") {
            b = int(St.top()); St.pop();
            a = int(St.top()); St.pop();
            St.push(a+b);
        }
        else if (s[i] == "-") {
            b = int(St.top()); St.pop();
            a = int(St.top()); St.pop();
            St.push(a-b);
        }
        else if (s[i] == "*") {
            b = int(St.top()); St.pop();
            a = int(St.top()); St.pop();
            St.push(a*b);
        }
        else if (s[i] == "/") {
            b = int(St.top()); St.pop();
            a = St.top(); St.pop();
            St.push(a/b);
        }
        else {
            St.push(atoi(s[i].c_str()));
        }
    }
    return int(St.top());
}

int main() {
    int n;
    string A[100], B[100];
    string in;

    cin >> n;

    while (n--) {
        cin >> in;
        str2arr(in, A);
        Generate_RPN(A, B);
        cout << Calculate_RPN(B) << endl;
    }

    return 0;
}

• Pythonによる解答例

# coding: utf-8

# Convert String to List
def String2List(s):
    L = []; tmp = ""
    for i in s:
        if i.isdigit():
            tmp += i
        else:
            if tmp != "":
                L.append(tmp)
                tmp = ""
            L.append(i)
    if tmp != "":
        L.append(tmp)

    return L

# generate Reverse Polish Notation
def Generate_RPN(L):
    S, L2 = [], []
    table = {"*": 1, "/": 1, "+": 0, "-": 0, "(": -1, ")": -1}
    for i in L:
        if i.isdigit():
            L2.append(i)
        elif i == "(":
            S.append(i)
        elif i == ")":
            while S[-1] != "(":
                L2.append(S.pop())
            S.pop()
        else:
            while len(S) != 0 and (table[S[-1]] >= table[i]):
                L2.append(S.pop())
            S.append(i)

    while len(S) != 0:
        L2.append(S.pop())

    return L2

def Calculate_RPN(L):
    St = []
 
    for i in L:
        if i == '+':
            St.append(int(St.pop()) + int(St.pop()))
        elif i == '-':
            St.append(-int(St.pop()) + int(St.pop()))
        elif i == '*':
            St.append(int(St.pop()) * int(St.pop()))
        elif i == '/':
            a = int(St.pop())
            b = float(St.pop())
            St.append(b/a)
        else:
            St.append(i)
 
    return St[0]


n = int(raw_input())

for _ in xrange(n):
    s = raw_input()
    print int(Calculate_RPN(Generate_RPN(String2List(s[:-1]))))

感想

やるだけなのにバグを埋め込みまくってコードを書くのにすごい時間がかかって辛かったです。あと一応AOJのシステムテストは通りましたが間違ってる可能性も大いにあるのでご注意ください。

AOJ0109: Smart Calculatorの他の人の解答を見てみたらみんな全然違う解き方をしていたのでみんなの解き方での実装もそのうちやりたいと思いました。

これ(https://gist.github.com/draftcode/1357281)とかめっちゃ参考になりそう。

参考文献

• https://ja.wikipedia.org/wiki/逆ポーランド記法

• http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=ALDS1_3_A

• http://knowledge.sakura.ad.jp/etc/220/

• http://7ujm.net/etc/calcstart.html