四則演算

加減乗除（と剰余）の計算式が与えられてそれを解釈、計算するプログラム。聞こえは簡単そうに思えますが、いくつか課題点があります。

文字列を適切に分割して、数値と演算子の部品に分けなければならない。
乗算や除算を、加算や減算より優先して行わなければならない。
カッコの中を先に計算しなければならない。

この問題に向き合いながら、いくつかの手法で計算プログラムを書いてみます。このページでは逆ポーランド記法を用います。

逆ポーランド記法

考え方

1 つめは、入力の形式を変えて計算する方法です。上記に挙げた問題を解決するというより、問題から逃げるといったほうが適切かもしれないものです。

逆ポーランド記法というもので計算式を書き、それを読み込ませるようにします。

例えば 3 - 2 を表現するとき、逆ポーランド記法では次のように書きます。

3 2 -

数字を順番に保存していき、演算子が出たら、直近 1, 2 番目で計算を行い、計算結果をまた保存する、を繰り返します。

詳しくは Wikipedia で。
https://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95

入力が形式的で自由が無い分、コンピューターにとっては解析しやすくなります。

計算時は直近に入れた数値を取り出すという操作になるため、数値を保存していくのは stack です。

コード

main.cpp

#include <iostream>
#include <string>
#include <sstream>
#include <stack>

using namespace std;

// result = true のとき計算成功 value に数値が入る
// result = false のとき計算失敗
struct OptionInt {
    bool result;
    int value;
};

// 文字列の中の文字が全部数字か
bool isDigit(string& s) {
    for (int i = 0; i < s.size(); i++) {
        if (s[i] < '0' || s[i] > '9') {
            return false;
        }
    }

    return true;
}

// 文字列を計算して数値を出す
OptionInt evaluate(string& line) {
    string s;
    stringstream ss(line);
    stack<int> st;

    while (! ss.eof()) {
        ss >> s;

        // 演算子の場合
        if (s == "+" || s == "-" || s == "*" || s == "/" || s == "%") {
            if (st.size() < 2) {
                cerr << "parse error" << endl;
                return OptionInt{ false, 0 };
            }

            // 直近の数値を取り出して
            int a = st.top();
            st.pop();
            int b = st.top();
            st.pop();

            // 計算
            if (s == "+") {
                st.push(b + a);
            } else if (s == "-") {
                st.push(b - a);
            } else if (s == "*") {
                st.push(b * a);
            } else if (s == "/") {
                // ゼロ除算
                if (a == 0) {
                    cerr << "zero division" << endl;
                    return OptionInt{ false, 0 };
                }
                st.push(b / a);
            } else if (s == "%") {
                // ゼロ除算
                if (a == 0) {
                    cerr << "zero division" << endl;
                    return OptionInt{ false, 0 };
                }
                st.push(b % a);
            }
        // 数値の場合は保存
        } else if (isDigit(s)) {
            st.push(stoi(s));
        // 例外
        } else {
            cerr << "illegal argument " << s << endl;
            return OptionInt{false, 0 };
        }
    }

    // 数値と演算子の数があっていない場合エラー
    if (st.size() != 1) {
        cerr << "parse error" << endl;
        return OptionInt{ false, 0 };
    }

    return OptionInt{ true, st.top() };
}

int main() {
    string line;

    getline(cin, line);
    OptionInt opt_value = evaluate(line);

    if (opt_value.result) {
        cout << opt_value.value << endl;
    }

    return 0;
}

実行

shell

$ g++ main.cpp
$ ./a.out <<< "3 2 4 - * 15 6 / +"

3 * (2 - 4) + (15 / 6) = -4 を計算しました。

関数型言語で実装

Haskell でも実装してみました。

逆ポーランド記法では演算子と数値がくっついていることがないので、 words で簡単に数値や演算子を分割できる。
List は、先頭へつける、先頭から取り出すという操作を簡単にできるため、数値を保管する操作を簡単に記述できる。
上記で作成した、値が入るか入らないかわからないデータ OptionInt は Maybe Int で代用できる。

このような理由で簡潔に記述できます。

module Main where

import Data.Char

main :: IO ()
main = do
    line <- getLine
    let es = words line
    case evaluate [] es of
        Just v -> putStrLn . show $ v
        Nothing -> putStrLn "error"

evaluate :: [Integer] -> [String] -> Maybe Integer
evaluate [value] [] = Just value
evaluate _ [] = Nothing
evaluate (a : b : stack) ("+" : es) = evaluate (b + a : stack) es
evaluate (a : b : stack) ("-" : es) = evaluate (b - a : stack) es
evaluate (a : b : stack) ("*" : es) = evaluate (b * a : stack) es
evaluate (a : b : stack) ("/" : es) = if a == 0 then Nothing else evaluate (b `div` a : stack) es
evaluate (a : b : stack) ("%" : es) = if a == 0 then Nothing else evaluate (b `mod` a : stack) es
evaluate stack (e : es) = if all Data.Char.isDigit e then evaluate ((read e :: Integer) : stack) es else Nothing