数式のパース:操車場アルゴリズム

ちょっとした思いつきで数式をパースする必要が出てきたので、練習がてらC#で実装してみたいと思います。
とりあえずは「操車場アルゴリズム」をやっつけます。

操車場アルゴリズム

ja.wikipedia.org

Wikipediaによると

操車場アルゴリズム(そうしゃじょうアルゴリズム)は、なんらかの中置記法に属する構文に従った順序で記号(トークン)が並んでいる、数式等の記号列を解析(構文解析)する、スタックベースのアルゴリズムである。

と言うことです。スタックに積んだり戻したりする様子を操車場の動きに見立てたんですね。
解析結果が逆ポーランド記法になるので便利そうです。

Wikipediaに詳細なアルゴリズムが記載されているので思いっきり参考にします。

仕様

pythonライクに下記の演算子に対応します。

~, **, *, /, %, +, -,

また、できれば組み込みの関数にも対応できるといいなと思います。

トークン分割

本編に入る前に入力文字列をトークンに分割してしまいます。
string.Split(' ') で簡単に済ませたいところですが、ちょっと真面目に実装します。

一文字ずつ先読みし、読み込み中の文字列(token)と足した文字列がoperatorの配列と合致するものが なければトークンとしてreturnします。

IEnumerable<string> Split(string formula) {
    var operators = new string[] {
      "~", "**", "*", "/", "%", "+", "-", "(", ")", ","
    };
    string? token = null;
    foreach (var c in formula) {
        if (c == ' ') {
            if (token != null) {
                yield return token;
                token = null;
            }
        }
        else {
            if (token == null ||
                operators.Any(o => o.StartsWith(token + c))) {
                token += c;
            }
            else {
                if (operators.Any(o => o.StartsWith(token)) ||
                    operators.Any(o => o.StartsWith(c))) {
                    yield return token;
                    token = null;
                }
                token += c;
            }
        }
    }
    if (token != null) yield return token;
}

解析

Wikipediaを読むと、トークンの解析ために

  • 数値、関数、演算子、括弧、セパレータ の区別
  • 演算子の場合は優先順位と結合性

の情報が必要みたいです。

優先順位は定数で記載してもいいですが、将来追加する場合も考慮してリストから生成するようにしたいと思います。

List<List<(string op, bool leftAssoc)>> Operators = new()
{
  new() { ("~", false) },
  new() { ("**", false) },
  new() { ("*", true), ("/", true), ("%", true) },
  new() { ("+", true), ("-", true) },
};

優先度が高い順にリストが並んでいるので、LINQ演算子の文字列をキーとした優先度と結合性のタプルをDictionaryに変換しましょう。

var operators = Operators
    .Select((o, i) => (o, i))
    .SelectMany(e => e.o.Select(o => (o.op, e.i, o.leftAssoc)))
    .ToDictionary(i => i.op, i => (priority: i.i, i.leftAssoc));

これで文字列 t が演算子かは operators.ContainsKey(t) で判断できますし、演算子の情報は operators[t] で取り出せます。

関数に関しては文字列の配列で事足りるので特に処理は必要ないですね。

準備は整ったのでWikipediaアルゴリズムを実装してみました。
コメントは「アルゴリズムの詳細」で記述されている項目に対応しているので参考にしてください。

IEnumerable<string> Analyze(IEnumerable<string> tokens) {
    var operators = Operators
        .Select((o, i) => (o, i))
        .SelectMany(e => e.o.Select(o => (o.op, e.i, o.leftAssoc)))
        .ToDictionary(i => i.op, i => (priority: i.i, i.leftAssoc));

    bool? isOperator(string t) => operators?.ContainsKey(t);
    bool? isFunction(string t) => Functions.Contains(t);

    var queue = new Queue<string>();
    var stack = new Stack<string>();

    foreach (var t in tokens) {
        // トークンを1つ読み込む。
        if (isFunction(t) == true) {
            // トークンが関数の場合、それをスタックにプッシュする。
            stack.Push(t);
        } else if (t == ",") {
            // トークンが関数の引数セパレータ(カンマなど)の場合
            if (!stack.Contains("("))
                throw new Exception();

            while (stack.First() != "(") {
                queue.Enqueue(stack.Pop());
            }
        } else if (isOperator(t) == true) {
            // トークンが演算子 o1 の場合
            while (stack.Count > 0) {
                var top = stack.First();
                if (isOperator(top) != true) break;

                var op1 = operators[t];
                var op2 = operators[top];

                if (op1.leftAssoc) {
                    if (op1.priority < op2.priority) break;
                } else {
                    if (op1.priority <= op2.priority) break;
                }
                queue.Enqueue(stack.Pop());
            }
            stack.Push(t);
        } else if (t == "(") {
            // トークンが左括弧の場合、スタックにプッシュする。
            stack.Push(t);
        } else if (t == ")") {
            // トークンが右括弧の場合
            if (!stack.Contains("("))
                throw new Exception();

            while (true) {
                var o = stack.Pop();
                if (o == "(") break;
                queue.Enqueue(o);
            }
        } else {
            // トークンが数値の場合、それを出力キューに追加する。
            queue.Enqueue(t);
        }
    }

    // トークンが右括弧の場合
    foreach (var o in stack)
        queue.Enqueue(o);

    return queue;
}

入力した数式が正しく解析されるか動作させてみます。

void test(string formula) {
  Console.WriteLine($"INPUT: {formula}");
  var tokens = Split(formula);
  var rpn = Analyze(tokens);
  Console.WriteLine(string.Join(' ', rpn));
}

test("3+4*2/(1-5)**2**3");
test("D(1 - 2 * 3 + 4, ~5, 6)");
test("1.5*2.22");
test("sqrt(2*3)*2");

結果は・・

INPUT: 3+4*2/(1-5)**2**3
3 4 2 * 1 5 - 2 3 ** ** / +

INPUT: D(1 - 2 * 3 + 4, ~5, 6)
1 2 3 * - 4 + 5 ~ 6 D

INPUT: 1.5*2.22
1.5 2.22 *

INPUT: sqrt(2*3)*2
2 3 * 2 * sqrt

最後の sqrt(2*3)*2 がおかしいようです。
本来は 2 3 * sqrt 2 * になって欲しいです。

関数の後には括弧が来るので、関数がある場合は右括弧の処理が完了した時にスタックの先頭にいるはずです。
ですので、右括弧の処理後、キューに入れてあげましょう。

        : 
        } else if (t == ")") {
            // トークンが右括弧の場合
            if (!stack.Contains("("))
                throw new Exception();

            while (true) {
                var o = stack.Pop();
                if (o == "(") break;
                queue.Enqueue(o);
            }
            // ここを追加!
            if (isFunction(stack.First()) == true) {
                queue.Enqueue(stack.Pop());
            }
        } else {
        :

変更後の結果です。デグレードもしてないしいい感じです!

INPUT: 3+4*2/(1-5)**2**3
3 4 2 * 1 5 - 2 3 ** ** / +

INPUT: D(1 - 2 * 3 + 4, ~5, 6)
1 2 3 * - 4 + 5 ~ 6 D

INPUT: 1.5*2.22
1.5 2.22 *

INPUT: sqrt(2*3)*2
2 3 * sqrt 2 *

式の評価

ここまでで逆ポーランド記法で並び替えられたので順番に処理していけば簡単に式を評価できます。
式を評価するにあたって、要求するオペランドの数と演算子の処理を定義する必要があります。

例の如くDictionaryで定義します。演算子の処理は引数が不定なのでIEnumerableで貰います。

Dictionary<string, (int arguments, Func<IEnumerable<decimal>, decimal> eval)> operators = new()
{
    { "~", (1, (a) => ~(int)a.First()) },
    { "**", (2, (a) => (decimal)Math.Pow((double)a.First(), (double)a.Last())) },
    { "*", (2, (a) => a.First() * a.Last()) },
    { "/", (2, (a) => a.First() / a.Last()) },
    { "%", (2, (a) => a.First() % a.Last()) },
    { "+", (2, (a) => a.First() + a.Last()) },
    { "-", (2, (a) => a.First() - a.Last()) },
    { "sqrt", (1, (a) => (decimal)Math.Sqrt((double)a.First())) },
    { "D", (3, (a) => a.First() + a.Skip(1).Take(1).First() + a.Last()) },
    // Wikipediaで例示されている関数'D'は引数の総和でとりあえず実装
};

あとは逆ポーランド記法で並べられたトークンを順に処理していきます。

  • 数値の場合はスタックに移す
  • 関数を含む演算子の場合は必要な数だけスタックから取り出して評価し、結果をスタックに積む

トークンを処理し終わってスタックの先頭にいる数値が評価結果になります。

decimal Evaluate(IEnumerable<string> rpn) {
    var stack = new Stack<string>();
    foreach (var i in rpn) {
        if (operators.ContainsKey(i)) {
            var op = operators[i];
            if (stack.Count < op.arguments) {
                throw new Exception();
            }
            var args = Enumerable.Range(0, op.arguments)
                .Select(_ => decimal.Parse(stack.Pop()))
                .Reverse()
                .ToArray();
            var v = op.eval?.Invoke(args);
            stack.Push($"{v}");
        } else {
            stack.Push(i);
        }
    }
    return decimal.Parse(stack.Pop());
}

早速先程の結果を評価してみましょう。

void test(string formula) {
  Console.WriteLine($"INPUT: {formula}");
  var tokens = Split(formula);
  var rpn = Analyze(tokens);
  Console.WriteLine(string.Join(' ', rpn));
  var v = Evaluate(rpn);
  Console.WriteLine($"value = {v}");
}

test("3+4*2/(1-5)**2**3");
test("D(1 - 2 * 3 + 4, ~5, 6)");
test("1.5*2.22");
test("sqrt(2*3)*2");

結果も正しそうです。

INPUT: 3+4*2/(1-5)**2**3
3 4 2 * 1 5 - 2 3 ** ** / +
value = 3.0001220703125

INPUT: D(1 - 2 * 3 + 4, ~5, 6)
1 2 3 * - 4 + 5 ~ 6 D
value = -1

INPUT: 1.5*2.22
1.5 2.22 *
value = 3.330

INPUT: sqrt(2*3)*2
2 3 * sqrt 2 *
value = 4.89897948556636

定数、変数の利用

πなどの定数や、計算結果を変数に格納して利用できると良さそうなので機能追加します。

定数名や変数名はバッティングすることがないのでDictionaryを用意すれば良さそうです。

Dictionary<string, decimal> Variables = new()
{
    { "pi", (decimal)Math.PI }
};

前項でオペランドdecimal.Parse(***)で処理していた部分をこんな感じの関数で置き換えます。

decimal ToDecimal(string s)
  => Variables.ContainsKey(s) ? Variables[s] : decimal.Parse(s);

変数の代入はEvaluate()の中で処理する方法もありますが、構文解析開始する前に 等号(=)を含む式の場合を判定して事前に処理します。

void test(string formula) {
  var part = formula.Split('=');
  var tokens = part.Length switch {
    1 => Split(part[0]),
    2 => Split(part[1]),
    _ => throw new Exception()  // x = y= 100 みたいなのは非対応
  };
  var rpn = Analyze(tokens);
  var v = Evaluate(rpn);
  Console.WriteLine($"value = {v}");

  if (part.Length == 2) {
    Variables[part[0].Trim()] = v;
    Console.WriteLine($"store {v} to {part[0]}");
  }
}

test("pi * 5 ** 2");
test("x = 1 + 2");
test("y = 2 * x + 1");
test("x + y");
test("x = 1 - 2");
test("x + y");

定数の利用も変数の代入も問題なさそうです。
変数の上書きもできています。

INPUT: pi * 5 ** 2
value = 78.53981633974475

INPUT: x = 1 + 2
value = 3
store 3 to x 

INPUT: y = 2 * x + 1
value = 7
store 7 to y 

INPUT: x + y
value = 10

INPUT: x = 1 - 2
value = -1
store -1 to x 

INPUT: x + y
value = 6

問題点

大体いい感じでしたが、符号付きの項がある式で問題が出ました。

test("-sqrt(2)");
test("-1 - 1");
test("-1 - -1");
INPUT: -sqrt(2)
error

INPUT: -1 - 1
error

INPUT: -1 - -1
error

結果はことごとくエラーです。
減算の符号と認識されるのでオペランドの数が足りなくてエラーになっていますね。

Splitあたりで符号と演算子の区別をつける必要がありそうですね。。

もう一工夫するか、全然違う手法を検討するか、再挑戦したいと思います。

ソースコード

ソースコードGithubで公開していますのでよければどうぞ。
演算子の定義など重複するものは共通で使うようにリファクタリングしてます)

github.com