読者です 読者をやめる 読者になる 読者になる

四則演算がしたかった

さて、文字列として与えられた数式を計算して、その結果を得たい。

まず思い浮かんだのは逆ポーランド記法である。

逆ポーランド記法ならば簡単に数式を解釈出来る。

数値が現れればスタックにプッシュ、演算子が現れれば数値をスタックからポップして計算結果をプッシュするだけだ。

以下のコードはD言語によって記述されている。また、コードを単純にするために入力された式の誤りは考えない。

import std.stdio;
import std.string;
import std.ascii:isDigit;
import std.conv:to;

T popBack(T)(ref T[] arr) {
	T back = arr[$-1];
	arr = arr[0..$-1];
	return back;
}

double npl(string[] tokens) {
	double[] stack;

	foreach(token; tokens) {
		if(token[0].isDigit) {
			//	数値はプッシュ
			stack ~= token.to!double;
		}
		else  {
			//	演算子ならポップ
			double b = stack.popBack();
			double a = stack.popBack();

			switch(token) {
			case "+": stack ~= a+b; break;
			case "-": stack ~= a-b; break;
			case "*": stack ~= a*b; break;
			case "/": stack ~= a/b; break;
			default : assert(0);
			}
		}
	}

	//	スタックの一番上が計算結果
	return stack[$-1];
}


double eval(string src) {
	return src.split(" ").npl();
}

void main() {
	readln().chomp.eval().writeln();
}
>dmd -run a.d
3 1 5 + 2 3 + * - 9 /
-3

逆ポーランド記法の数式

3 1 5 + 2 3 + * - 9 /

中置記法で表すと

(3-(1+5)*(2+3))/9 == -3

であるため、出力は正しい。

数式を文字列で受け取り、計算結果を返す関数eval()は、トークン列を受け取り計算結果を返す関数npl()にほとんどの処理を丸投げしている。

では、中置記法の数式を解析したい。調べてみるとおあつらえ向きのものが存在した。「操車場アルゴリズム」である。

これは、ようは中置記法から逆ポーランド記法の数式を生成するためのアルゴリズムと言える。

ひとまず括弧のことは考えずに数値と +-*/ の4つの演算子のみで構成された中置記法の数式を解析しようと思う。

import std.conv:to, parse;

double eval(string src) {
	string[] nplTokens;
	string[] opStack;

	while(src.length) {
		if(src[0].isDigit) {
			//	数値ならば読み進める
			nplTokens ~= src.parse!double().to!string;
		}
		else {
			//	演算子
			if(src[0] == '+' || src[0] == '-') {
				//	空になるまで取り出す
				while(opStack.length)
					nplTokens ~= opStack.popBack();
			}

			//	スタックにプッシュ
			opStack ~= src[0..1];
			src = src[1..$];
		}
	}

	//	残った演算子を全部取り出す
	foreach_reverse(op; opStack)
		nplTokens ~= op;

	//	変換結果を出力
	nplTokens.writeln();

	return nplTokens.npl();
}
>dmd -run b.d
3-1+5*2+3/9
["3", "1", "-", "5", "2", "*", "+", "3", "9", "/", "+"]
12.3333

mainとnplには手を加えていないため省略した。

いろいろと無駄は多いが、気にしないことにする。

次に、括弧の処理を加える。

コードの変更は少しだ。

double eval(string src) {
	string[] nplTokens;
	string[] opStack;

	while(src.length) {
		if(src[0].isDigit) {
			//	数値ならば読み進める
			nplTokens ~= src.parse!double().to!string;
		}
		else {
			//	演算子
			if(src[0] == '+' || src[0] == '-') {
				//	空になるか、左括弧まで取り出す
				while(opStack.length && opStack[$-1] != "(")
					nplTokens ~= opStack.popBack();
			}
			else if(src[0] == ')') {
				//	右括弧の時は左括弧まで取り出す
				while(opStack[$-1] != "(")
					nplTokens ~= opStack.popBack();

				//	左括弧は捨てる
				opStack.popBack();
			}

			//	右括弧でないならばスタックにプッシュ
			if(src[0] != ')')
				opStack ~= src[0..1];
		
			src = src[1..$];
		}
	}

	//	残った演算子を全部取り出す
	foreach_reverse(op; opStack)
		nplTokens ~= op;

	//	変換結果を出力
	nplTokens.writeln();

	return nplTokens.npl();
}
>dmd -run c.d
(3-(1+5)*(2+3))/9
["3", "1", "5", "+", "2", "3", "+", "*", "-", "9", "/"]
-3

効率もいいとは言えないし、現状柔軟性もなにもない。更にはエラーチェックもろくにしていないため妙なものを渡せば即落ちる危ういものではあるが、一応文字列として与えられた数式から計算結果を得られた。

今回はD言語でプログラムを記述したが、配列を柔軟に扱えるのはありがたい。

それから、個人的にD言語のUFCS(Uniform Function Call Syntax)は好きだ。

やり過ぎは良くないとはわかっているのだがついつい関数をぽんぽんと後ろに繋げていってしまう。