Help us understand the problem. What is going on with this article?

意外と手間のかかる四則演算プログラム:1. 逆ポーランド記法

四則演算

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

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

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

逆ポーランド記法

考え方

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 は、先頭へつける、先頭から取り出すという操作を簡単にできるため、数値を保管する操作を簡単に記述できる。
  • 上記で作成した、値が入るか入らないかわからないデータ OptionIntMaybe 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
tfull_tf
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away