操車場(Shunting Yard)アルゴリズムとは
中置記法(infix notation)の数式を、逆ポーランド記法(Reverse Polish notation、後置記法)に変換するアルゴリズム。
1 + 2を1 2 +に置き換える。
仕様
サポートするもの
- 一桁の自然数の入力
- 四則演算(+-*/)
- 括弧による優先順位変更
サポートしないもの
- 2桁以上の自然数の入力
- 演算子の結合規則
- 括弧の非対応に対するエラー処理
実装
入出力がはっきりしているので、テスト駆動開発で進めるとやりやすいです。
まずは以下のようなテストケースを用意します。
<?php namespace ryo511;
class ShuntingYardTest extends \PHPUnit_Framework_TestCase
{
/**
* @test
* @dataProvider provideTestData
*/
public function infixToPrefix($data, $expected)
{
$this->assertSame($expected, (new ShuntingYard())->infixToPrefix($data));
}
public function provideTestData()
{
return [
['1 + 2', '1 2 +'],
['0 - 0', '0 0 -'],
['3 + 4 * 2', '3 4 2 * +'],
['3 * 4 + 2', '3 4 * 2 +'],
['3 + 4 * 2 + 1', '3 4 2 * + 1 +'],
['(3 + 4) * 2', '3 4 + 2 *'],
['(((((1+1)))))', '1 1 +'],
];
}
}
下に行くほど複雑なテストケースなので、簡単なケースから一つずつ実装していくといいと思います。
PHPによる実装例は以下です。
<?php namespace ryo511;
/**
* @see https://en.wikipedia.org/wiki/Shunting-yard_algorithm
*/
class ShuntingYard
{
// operator => priority(larger is higher)
const OPERATORS_TO_PRIORITY = [
'+' => 1,
'-' => 1,
'*' => 2,
'/' => 2,
'(' => -1, // should not output
')' => -1, // should not output
];
/** @var \SplQueue */
private $outputQueue;
/** @var \SplStack */
private $operatorStack;
public function __construct()
{
$this->outputQueue = new \SplQueue();
$this->operatorStack = new \SplStack();
}
/**
* @param string $statement
* @return string
*/
public function infixToPrefix($statement)
{
for ($i = 0, $len = strlen($statement); $i < $len; $i++) {
$char = $statement[$i];
if ($this->isOperator($char)) {
$this->computeOperator($char);
} elseif ($this->isNumber($char)) {
$this->addOutput($char);
}
}
foreach ($this->operatorStack as $operation) {
$this->addOutput($operation);
}
return implode(' ', $this->queueToArray($this->outputQueue));
}
/**
* @param \SplQueue $queue
* @return array
*/
private function queueToArray(\SplQueue $queue)
{
$result = [];
foreach ($queue as $value) {
$result[] = $value;
}
return $result;
}
/**
* @param string $char
*/
private function addOutput($char)
{
if ($this->shouldOutput($char)) {
$this->outputQueue->enqueue($char);
}
}
/**
* @param string $char
* @return bool
*/
private function isNumber($char)
{
return ctype_digit((string)$char);
}
/**
* @param string $char
* @return bool
*/
private function isOperator($char)
{
return in_array($char, array_keys(self::OPERATORS_TO_PRIORITY));
}
/**
* @param string $char
* @return bool
*/
private function shouldOutput($char)
{
return $this->isNumber($char) ||
($this->isOperator($char) && self::OPERATORS_TO_PRIORITY[$char] > 0);
}
/**
* @param string $o1
*/
private function computeOperator($o1)
{
if ($this->operatorStack->isEmpty()) {
$this->operatorStack->push($o1);
} elseif (')' === $o1) {
while (!$this->operatorStack->isEmpty() && '(' !== ($o2 = $this->operatorStack->pop())) {
$this->addOutput($o2);
}
} else {
$o2 = $this->operatorStack->top();
if ($this->priorityDiff($o1, $o2) > 0) {
$this->operatorStack->push($o1);
} else {
$this->addOutput($this->operatorStack->pop());
$this->computeOperator($o1);
}
}
}
/**
* @param string $o1
* @param string $o2
* @return int
*/
private function priorityDiff($o1, $o2)
{
return self::OPERATORS_TO_PRIORITY[$o1] - self::OPERATORS_TO_PRIORITY[$o2];
}
}
GitHubでも公開してるので、テストを動かしてみたい方はこちらをダウンロードしてください。
https://github.com/ryo-utsunomiya/PhpShuntingYard
ポイントがいくつかあるので解説します。
1. SplQueue/SplStackの活用
SPL(Standard PHP Library)と呼ばれるPHPのライブラリ群の中には、汎用的なデータ構造を実装したものがあります(PHPマニュアル)。
- SplDoublyLinkedList
- SplStack
- SplQueue
- SplHeap
- SplMaxHeap
- SplMinHeap
- SplPriorityQueue
- SplFixedArray
- SplObjectStorage
本プログラムでは、SplStackとSplQueueを使用しています。実装自体は配列でも可能ですが、適切なデータ構造を採用するとプログラムの意図がわかりやすくなります（パフォーマンスも良くなるかもしれません）。
2. バイトの配列としての文字列
PHPの文字列は配列のように扱うことができるので、1文字ずつ処理したい場合は以下のようなfor文で回すことができます。
for ($i = 0, $len = strlen($line); $i < $len; $i++) {
$char = $line[$i];
// do something
}
マルチバイト文字を処理したい場合は以下のようにすればOKです。
for ($i = 0, $len = mb_strlen($line); $i < $len; $i++) {
$char = mb_substr($line, $i, 1);
// do something
}
3. 演算子の取り扱い
操車場アルゴリズムの実装で、厄介なのが演算子の優先度の取り扱いです。
新しく追加される演算子が、既存の演算子スタックの一番上のものよりも優先度が低い場合、演算子を出力キューに移す必要があります。
$o2 = $this->operatorStack->top();
if ($this->priorityDiff($o1, $o2) > 0) {
$this->operatorStack->push($o1);
} else {
$this->addOutput($this->operatorStack->pop());
$this->computeOperator($o1);
}
もう1つ注意が必要なのが括弧の取り扱いで、右括弧が来たら左括弧までを全てスタックから取り出して出力キューに入れる必要があります。
} elseif (')' === $o1) {
while (!$this->operatorStack->isEmpty() &&
'(' !== ($o2 = $this->operatorStack->pop())) {
$this->addOutput($o2);
}
現状のcomputeOperator()メソッドも結構複雑になってきているので、演算子の結合規則まで含めて実装しようとすると、クラスの分割をして見通しを良くする必要が出てくるかなー、という感じがします。