October 2015
Volume 30 Number 10
C# - C# の分割結合式パーサー
Vassili Kaplan | October 2015 | サンプル コードのダウンロード: C# VB
CVu Journal 2015 年 5 月号と 6 月号に掲載された私の記事では、C++ で数式を解析する新しいアルゴリズムを発表しました (「参考資料」の資料 1 および資料 2 参照)。2 回にわたって記事を執筆した理由は、Silas S. Brown という鋭い観察眼を持った読者が最初のアルゴリズムの実装にバグを見つけた結果、実装を変更する必要が生じたためです。この指摘のおかげで、アルゴリズムの完成度が高まりました。その後も、小規模なバグをいくつか修正しています。今回の記事では、修正版の C# アルゴリズムの実装を紹介します。
コードを記述して数式を解析する必要に迫られた経験をお持ちの方は多くないでしょうが、このアルゴリズムで使用する手法は、非標準の文字列を解析するなどの他のシナリオにも適用できます。このアルゴリズムを使用すると、望みどおりの処理 (たとえば、Web 要求を実行してピザを注文する処理) を実行する新しい関数を簡単に定義することもできます。少し調整すれば、新しいカスタム スクリプト言語用に独自の C# コンパイラを作成することも可能です。また、アルゴリズム自体を興味深いものと思っていただけるはずです。
エドガー ダイクストラのアルゴリズムは、50 年以上さかのぼる 1961 年に発表され、数式の解析によく使用されます (「参考資料」の資料 3 参照)。ただし、代替アルゴリズムがあってもよいでしょう。新しいアルゴリズムは時間計算量が同じでも、個人的な見解では実装と拡張が簡単になります。
この記事では、関数ファクトリの実装で "仮想コンストラクター" という手法を使用することに注意してください。この手法は、James Coplien が C++ で導入しました (「参考資料」の資料 4 参照)。C# の世界でも仮想コンストラクターの使用を興味深く思っていただければさいわいです。
分割結合アルゴリズム
図 1 のデモ プログラムに、数式を解析する分割結合アルゴリズムを示します。
.png "分割結合アルゴリズムのデモ実行")
図 1 分割結合アルゴリズムのデモ実行
アルゴリズムは 2 段階で構成されています。第 1 段階では、式が含まれた文字列を Cell オブジェクトのリストに分割します。それぞれの Cell オブジェクトの定義は以下のとおりです。
class Cell
{
internal Cell(double value, char action)
{
Value = value;
Action = action;
}
internal double Value { get; set; }
internal char Action { get; set; }
}
アクションは単一の文字で、'*' (乗算)、'/' (除算)、'+' (加算)、'-' (減算)、または '^' (累乗) のいずれかの算術演算子、あるいは式の終了を示す特殊文字を指定できます。今回はこの特殊文字を')' とハード コードしています。結合するセル リストの最後の要素には、アクションではないという意味で特別なアクション ')' を必ず指定することになります。ただし、他の記号やかっこを代わりに使用することもできます。
第 1 段階では、式をトークンに分割してから、トークンをセルに変換します。すべてのトークンは、いずれかの数式またはかっこで区切られています。トークンは、実数の場合も、関数名が含まれた文字列の場合もあります。後ほど定義する ParserFunction クラスは、解析対象の文字列に含まれているすべての関数を処理するか、文字列を解析して数値に変換します。また、ParserFunction クラスは、文字列解析アルゴリズム全体を再帰的に呼び出します。解析対象の文字列に関数もかっこもない場合、再帰処理は発生しません。
第 2 段階では、すべてのセルを 1 つに結合します。第 2 段階の方が第 1 段階よりも少し簡単なので、まずは第 2 段階について説明しましょう。
セルのリストを結合する
セルのリストを、アクションの優先順位、つまり算術演算子の優先順位に従って、1 つずつ結合します。アクションの優先順位は、以下のように計算します。
static int GetPriority(char action)
{
switch (action) {
case '^': return 4;
case '*':
case '/': return 3;
case '+':
case '-': return 2;
}
return 0;
}
2 つのセルを結合できるのは、左側のセルのアクションの優先順位がその右側にあるセルのアクションの優先順位以上の場合だけです。
static bool CanMergeCells(Cell leftCell, Cell rightCell)
{
return GetPriority(leftCell.Action) >= GetPriority(rightCell.Action);
}
セルの結合とは、左側のセルのアクションを左側と右側のセルの値に適用することです。結合した新しいセルには、右側のセルと同じアクションが設定されます (図 2 参照)。
図 2 MergeCells メソッド
static void MergeCells(Cell leftCell, Cell rightCell)
{
switch (leftCell.Action)
{
case '^': leftCell.Value = Math.Pow(leftCell.Value, rightCell.Value);
break;
case '*': leftCell.Value *= rightCell.Value;
break;
case '/': leftCell.Value /= rightCell.Value;
break;
case '+': leftCell.Value += rightCell.Value;
break;
case '-': leftCell.Value -= rightCell.Value;
break;
}
leftCell.Action = rightCell.Action;
}
たとえば、Cell(8, '-') と Cell(5, '+') を結合すると、Cell(8 – 5, '+') = Cell(3, '+') という新しいセルになります。
しかし、左側のセルの優先順位が右側のセルの優先順位よりも低いために 2 つのセルを結合できない場合は、どうなるでしょうか。その場合は、次のセル (右側のセル) にいったん移動して、このセルとさらに次のセルとの結合を試みます。今度もセルを結合できない場合は、再帰的にその先のセルに移動します。右側のセルとその次のセルを結合ししだい、元の左側のセルに戻り、このセルと新しく作成した右側とのセルの結合を試みます (図 3 参照)。
図 3 セルのリストの結合
static double Merge(Cell current, ref int index, List<Cell> listToMerge,
bool mergeOneOnly = false)
{
while (index < listToMerge.Count)
{
Cell next = listToMerge[index++];
while (!CanMergeCells(current, next))
{
Merge(next, ref index, listToMerge, true /* mergeOneOnly */);
}
MergeCells(current, next);
if (mergeOneOnly)
{
return current.Value;
}
}
return current.Value;
}
Merge メソッドの外部から見ると、mergeOneOnly パラメーターを false に設定して Merge メソッドを呼び出しているため、結合処理全体が完了するまではメソッドの結果が返されません。一方、Merge メソッドを再帰的に呼び出す場合 (優先順位が原因で左右のセルを結合できない場合) は、実際の結合を MergeCells メソッドで完了ししだい元の場所に戻る必要があるので、mergeOneOnly プロパティを true に設定します。
また、Merge メソッドから返される値が式の実際の結果であることにも注目してください。
式をセルのリストに分割する
アルゴリズムの前半では、式をセルのリストに分割します。この段階では、算術演算子の優先順位を考慮しません。まず、式をトークンのリストに分割します。すべてのトークンは、いずれかの算術演算子、左かっこ、または右かっこで分割します。必須ではありませんが、かっこには関数が関連付けられている場合があります。たとえば、"1- sin(1-2)" には関数が関連付けられていますが、"1- (1-2)" には関連付けられていません。
まず、関数もかっこもない場合の処理について説明しましょう。つまり、実数とその間の算術演算子で構成された式の場合です。この場合は、実数とその後のアクションで構成されたセルを作成します。たとえば、"3-2*4" を分割すると、以下の 3 つのセルで構成されたリストができあがります。
Split (“3-2*4”) = { Cell(3, ‘-’), Cell(2, ‘*‘), Cell(3, ‘)’) }
最後のセルのアクションは必ず、特別な END_ARG アクションです。END_ARG アクションの定義は以下のとおりです。
const char END_ARG = ')';
END_ARG アクションの定義を任意の定義に変更することもできますが、その場合は、対応する左かっこの START_ARG アクションも考慮してください。START_ARG アクションの定義は以下のとおりです。
const char START_ARG = '(';
いずれかのトークンが、関数の場合またはかっこで囲まれた式の場合は、再帰処理を使用して、そのトークンに分割結合アルゴリズム全体を適用します。たとえば、式が "(3-1)-1" の場合は、先にかっこ内のアルゴリズム全体が式に適用されます。
Split(“(3-1)-1”) = Split( “[SplitAndMerge(“3-1”)] - 1”) = { Cell(2, ‘-’), Cell(1, ‘)’) }
分割を実行する関数は、図 4 に示す LoadAndCalculate 関数です。
図 4 LoadAndCalculate メソッド
public static double LoadAndCalculate(string data, ref int from, char to = END_LINE)
{
if (from >= data.Length || data[from] == to)
{
throw new ArgumentException("Loaded invalid data: " + data);
}
List<Cell> listToMerge = new List<Cell>(16);
StringBuilder item = new StringBuilder();
do // Main processing cycle of the first part.
{
char ch = data[from++];
if (StillCollecting(item.ToString(), ch, to))
{ // The char still belongs to the previous operand.
item.Append(ch);
if (from < data.Length && data[from] != to)
{
continue;
}
}
// I am done getting the next token. The getValue() call below may
// recursively call loadAndCalculate(). This will happen if extracted
// item is a function or if the next item is starting with a START_ARG '(.'
ParserFunction func = new ParserFunction(data, ref from, item.ToString(), ch);
double value = func.GetValue(data, ref from);
char action = ValidAction(ch) ? ch
: UpdateAction(data, ref from, ch, to);
listToMerge.Add(new Cell(value, action));
item.Clear();
} while (from < data.Length && data[from] != to);
if (from < data.Length && (data[from] == END_ARG || data[from] == to))
{ // This happens when called recursively: move one char forward.
from++;
}
Cell baseCell = listToMerge[0];
int index = 1;
return Merge(baseCell, ref index, listToMerge);
}
LoadAndCalculate メソッドは、すべてのセルを listToMerge リストに追加してから、解析アルゴリズムの第 2 段階である結合関数を呼び出します。StringBuilder クラスの item オブジェクトには現在のトークンを格納し、式文字列から文字を 1 文字ずつ読み取っては item オブジェクトに追加します。
StillCollecting メソッドは、現在のトークンの文字がまだ収集中かどうかを確認します。現在の文字が END_ARG またはその他の特別な "to" 文字の場合は、収集中ではありません ("to" 文字とは、解析の引数がコンマで区切られている場合のコンマなどです。累乗関数を使用した例を後ほど紹介します)。また、現在の文字が有効なアクションまたは START_ARG の場合も、トークンの収集は完了しています。
static bool StillCollecting(string item, char ch, char to)
{
char stopCollecting = (to == END_ARG || to == END_LINE) ?
END_ARG : to;
return (item.Length == 0 && (ch == '-' || ch == END_ARG)) ||
!(ValidAction(ch) || ch == START_ARG || ch == stopCollecting);
}
static bool ValidAction(char ch)
{
return ch == '*' || ch == '/' || ch == '+' || ch == '-' || ch == '^';
}
ValidAction メソッドで指定した算術演算子、あるいは START_ARG 定数または END_ARG 定数で定義したかっこを取得した場合はすぐに、現在のトークンの収集が完了していることがわかります。また、"-" トークンに関連する特殊な状況もあります。"-" トークンは、負の符号で始まる数値を示すために使用します。
この分割段階の最後では、アルゴリズム全体の評価に対する再帰呼び出しを使用して、かっこ内のすべての部分式と、すべての関数呼び出しを削除します。ただし、このような再帰呼び出しから返されるアクションには必ず END_ARG アクションが指定されています。計算した式が評価対象の式の最後にない場合、このアクションはグローバルな式スコープに照らして正しくありません。そのため、以下のように、再帰呼び出しの後で毎回アクションを更新する必要があります。
char action = ValidAction(ch) ? ch
: UpdateAction(data, ref from, ch);
UpdateAction メソッドのコードを図 5 に示します。
図 5 UpdateAction メソッド
static char UpdateAction(string item, ref int from, char ch, char to)
{
if (from >= item.Length || item[from] == END_ARG || item[from] == to)
{
return END_ARG;
}
int index = from;
char res = ch;
while (!ValidAction(res) && index < item.Length)
{ // Look to the next character in string until finding a valid action.
res = item[index++];
}
from = ValidAction(res) ? index
: index > from ? index - 1
: from;
return res;
}
抽出したトークンの実際の解析は、図 4 のうち以下のコードで実行します。
ParserFunction func = new ParserFunction(data, ref from, item.ToString(), ch);
double value = func.GetValue(data, ref from);
抽出したトークンが関数ではない場合、このコードでは倍精度浮動小数点型への変換を試みます。それ以外の場合は、登録済みの適切な関数を呼び出し、その結果として LoadAndCalculate メソッドを再帰的に呼び出すことができます。
ユーザー定義関数と標準関数
今回は、James Coplien が最初に発表した仮想コンストラクターという手法を使用して (「参考資料」の資料 4 参照)、関数ファクトリを実装することにしました。C# では一般に、関数ファクトリの実装には、必要なオブジェクトを追加のファクトリ クラスで作成するファクトリ メソッドを使用します (「参考資料」の資料 5 参照)。ただし、Coplien が提唱した従来のデザイン パターンには、追加のファクトリ ファサード クラスが必要ありません。代わりに、同じクラスから派生した m_impl という実装メンバーを使用して、その場で新しいオブジェクトを作成します。
private ParserFunction m_impl;
特別な内部コンストラクターが、該当するクラスでこのメンバーを初期化します。作成する m_impl 実装オブジェクトの実際のクラスは、入力パラメーターによって異なります (図 6 参照)。
図 6 仮想コンストラクター
internal ParserFunction(string data, ref int from, string item, char ch)
{
if (item.Length == 0 && ch == Parser.START_ARG)
{
// There is no function, just an expression in parentheses.
m_impl = s_idFunction;
return;
}
if (m_functions.TryGetValue(item, out m_impl))
{
// Function exists and is registered (e.g. pi, exp, etc.).
return;
}
// Function not found, will try to parse this as a number.
s_strtodFunction.Item = item;
m_impl = s_strtodFunction;
}
ディクショナリを使用して、すべてのパーサー関数を保持します。このディクショナリは、関数の文字列名 (sin など) を、この関数を実装している実際のオブジェクトにマップします。
private static Dictionary<string, ParserFunction> m_functions =
new Dictionary<string, ParserFunction>();
パーサーを使用するときは、ParserFunction 基底クラスで以下のメソッドを呼び出すことで、必要なだけ関数を追加できます。
public static void AddFunction(string name, ParserFunction function)
{
m_functions[name] = function;
}
GetValue メソッドについては作成した ParserFunction 基底クラスで呼び出していますが、実際の処理は実装関数で実行します。実装関数は、次のような基底クラスの Evaluate メソッドをオーバーライドします。
public double GetValue(string data, ref int from)
{
return m_impl.Evaluate(data, ref from);
}
protected virtual double Evaluate(string data, ref int from)
{
// The real implementation will be in the derived classes.
return 0;
}
ParserFunction クラスから派生した関数実装クラスでは、図 6 の内部コンストラクターを使用しません。代わりに、以下のような基底クラスのコンストラクターを使用します。
public ParserFunction()
{
m_impl = this;
}
図 6 の ParserFunction コンストラクターでは、以下の 2 つの特別な "標準" 関数を使用しています。
private static IdentityFunction s_idFunction = new IdentityFunction();
private static StrtodFunction s_strtodFunction = new StrtodFunction();
1 つ目の標準関数は ID 関数です。この関数は、関数が関連付けられていないかっこ内の式を解析するために呼び出します。
class IdentityFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
return Parser.LoadAndCalculate(data, ref from, Parser.END_ARG);
}
}
2 つ目の標準関数は、"汎用" 関数です。この関数は、最後に抽出したトークンに対応する関数が 1 つも見つからない場合に呼び出します。このような状況は、抽出したトークンが実数でも実装済みの関数でもない場合に発生します。実装済みの関数ではない場合は、例外がスローされます。
class StrtodFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
double num;
if (!Double.TryParse(Item, out num)) {
throw new ArgumentException("Could not parse token [" + Item + "]");
}
return num;
}
public string Item { private get; set; }
}
その他すべての関数は、ユーザーが実装できます。最もシンプルな関数は、以下の円周率関数です。
class PiFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
return 3.141592653589793;
}
}
さらに典型的な実装は、指数関数です。
class ExpFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
double arg = Parser.LoadAndCalculate(data, ref from, Parser.END_ARG);
return Math.Exp(arg);
}
}
先ほど予告したように、コンマで区切られた 2 つの引数を必要とする、累乗関数を使用した例を紹介しましょう。カスタムの区切り文字で区切られた複数の引数を必要とする関数の記述方法は、以下のとおりです。
class PowFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
double arg1 = Parser.LoadAndCalculate(data, ref from, ',');
double arg2 = Parser.LoadAndCalculate(data, ref from, Parser.END_ARG);
return Math.Pow(arg1, arg2);
}
}
以下のように、任意の数の関数をユーザー コードからアルゴリズムに追加できます。
ParserFunction.AddFunction("pi", new PiFunction());
ParserFunction.AddFunction("exp", new ExpFunction());
ParserFunction.AddFunction("pow", new PowFunction());
まとめ
ここで紹介した分割結合アルゴリズムの計算量は、式文字列に含まれている文字数を n とすると、O(n) となります。その理由は、各トークンが分割段階で一度だけ呼び出されるためです。第 1 段階で作成されるセルの数を m とすると、最悪の場合でも、結合段階で実行する比較は最大 2(m - 1) – 1 回です。
したがって、このアルゴリズムの時間計算量はダイクストラのアルゴリズムと同じです (「参考資料」の資料 3 参照)。分割結合アルゴリズムでは再帰処理を使用するため、ダイクストラのアルゴリズムと比べて少しデメリットが生じるおそれがあります。一方、個人的な見解としては、再帰処理を使用しているからこそ、分割結合アルゴリズムは実装が簡単です。同時に、カスタムの構文、関数、および演算子を使用して拡張するのも簡単です。
参考資料
- V. Kaplan 著「数式を解析する分割結合アルゴリズム」(CVu 第 27 巻 2 号、2015 年 5 月、bit.ly/1Jb470l、英語)
- V. Kaplan 著「分割結合を再検討する」(CVu 第 27 巻 3 号、2015 年 6 月、bit.ly/1UYHmE9、英語)
- E. ダイクストラ考案 "操車場アルゴリズム" (https://ja.wikipedia.org/wiki/%E6%93%8D%E8%BB%8A%E5%A0%B4%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)
- J. Coplien 著『Advanced C++ Programming Styles and Idioms』(Addison-Wesley、1992 年) の 140 ページ
- E. Gamma、R. Helm、R. Johnson、および J. Vlissides 著『オブジェクト指向における再利用のためのデザイン パターン』(ソフトバンククリエイティブ、1999 年)
Vassili Kaplanは、以前は Microsoft Lync 開発者でした。C# と C++ を使用したプログラミングに熱心に取り組んでいます。現在はスイスのチューリッヒに住み、さまざまな銀行でフリーランス開発者として活動しています。連絡先は iLanguage.ch (英語) です。
この記事のレビューに協力してくれたマイクロソフト技術スタッフの James McCaffrey に心より感謝いたします。