四則演算
加減乗除（と剰余）の計算式が与えられてそれを解釈、計算するプログラム。聞こえは簡単そうに思えますが、いくつか課題点があります。
- 文字列を適切に分割して、数値と演算子の部品に分けなければならない。
- 乗算や除算を、加算や減算より優先して行わなければならない。
- カッコの中を先に計算しなければならない。
この問題に向き合いながら、いくつかの手法で計算プログラムを書いてみます。このページでは逆ポーランド記法を用います。
逆ポーランド記法
考え方
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