計算順序を考慮した電卓を書く

PHPエンジニアの方々はコンピューターサイエンスのバックグランドを持たない人が多いとおもいます。単なるWebアプリケーションを描くだけなら専門的な知識はいりません。

もっと深く勉強する意味

技術の進歩は早く、すぐに新しい技術が出てきてしまいます。Cookpadエンジニアブログでも書かれていましたが、今役に立つものはすぐに役に立たなくなってしまいます。エンジニアである以上生涯勉強を続けなくてはなりません。そんな時に、コンピューターサイエンスの基礎がしっかりしていれば未知の問題への対応、新技術の理解がより簡単になります。

電卓

1 + 2 * 3 - 4という文字列があった時に、どのようにして計算順序を考慮して処理するのかを考えます。おそらくPHPしか触ったことのない人はif文やfor文を大量に書き始めると思いますが、コンピューターサイエンスのバックグランドがある人は方針がすぐに浮かんできます。このトピックは単純な木構造の理解と一部の問題を解決する際にとても有効であることがわかるのでとてもいいと思いました。

木構造

数式は木構造で表すことができます。1 + 2 * 3 - 4は

    - 
   / \
  +   4
 / \
1   *
   / \
  2   3

という感じになります。各ノードが演算子になっていて、各葉が数値になっています。

実際のコード

class Value
{
	protected $value;
	public function __construct($value)
	{
		$this->value = $value;
	}

	public function evaluate()
	{
		return intval($this->value);
	}
}

abstract class Operation
{
	protected $first;
	protected $second;

	public function __construct($first, $second)
	{
		$this->first = $first;
		$this->second = $second;
	}

	abstract public function evaluate();
}

class Add extends Operation
{
	public function evaluate()
	{
		return $this->first->evaluate() + $this->second->evaluate();
	}
}

class Sub extends Operation
{
	public function evaluate()
	{
		return $this->first->evaluate() - $this->second->evaluate();
	}
}

class Mul extends Operation
{
	public function evaluate()
	{
		return $this->first->evaluate() * $this->second->evaluate();
	}
}

class Div extends Operation
{
	public function evaluate()
	{
		return $this->first->evaluate() / $this->second->evaluate();
	}
}

function parse($equation) {
	$addPos = strrpos($equation, '+');
	$subPos = strrpos($equation, '-');
	if ($addPos === false && $subPos === false) {
		$mulPos = strrpos($equation, '*');
		$divPos = strrpos($equation, '/');
		if ($mulPos === false && $divPos === false) {
			return new Value($equation);
		} elseif ($mulPos !== false && ($divPos === false || $mulPos > $divPos)) {
			return new Mul(parse(substr($equation, 0, $mulPos)), parse(substr($equation, $mulPos + 1)));
		} else {
			return new Div(parse(substr($equation, 0, $divPos)), parse(substr($equation, $divPos + 1)));
		}
	} elseif ($addPos !== false && ($subPos === false || $addPos > $subPos)) {
		return new Add(parse(substr($equation, 0, $addPos)), parse(substr($equation, $addPos + 1)));
	} else {
		return new Sub(parse(substr($equation, 0, $subPos)), parse(substr($equation, $subPos + 1)));
	}
}

$tree = parse('1+2*3-4');
echo $tree->evaluate(); // 3

解説

Valueが木構造でいう葉となっていて、Add、Sub、Mul、Divはノードに成っています。parse関数では後ろから探して行って+、-がない場合に*、/を探しに行っています。parse関数はもう少し綺麗になりそうですね。一見すぐに役立つものではありませんが、実際にコンパイラが式を評価するときにコードを木構造に落として評価していきます。プログラミング言語そのものの理解とその裏側で一体何が行われているのか考えることはエンジニアとしてとても意義のあることです。

コンピューターサイエンスのバックグラウンドがないがより深く勉強を続けたい方はUnderstanding Computationという本がとてもわかりやすく日本語版も出ているので是非オススメです。