UnityでC#で数式パーサーを自作してみた

概要

数式パーサーを自作しようと思った背景について
Unityで文字の数式を計算させたい
-> C#がよさそう
-> 外部ライブラリ使わずに計算させてみたい
-> 作ってみよう

というわけでゼロから数式パーサーを作ってみました.

作ったものについて

Formulaに数式を入力してParseボタンを押すと計算結果がConsoleに出力されます

数式パーサー実装のおおまかな流れ

この記事では以下のような流れで数式を計算させています. もっとスマートな方法があるかもしれません.
構文解析　→　字句解析　→　計算

※四則演算と()と整数のみに対応しています. (小数点には対応していません)

§1. 構文解析　～数式から木構造を作る～

まず、数式を計算させる準備として以下の手順で文字列の数式から木構造を作っていきます
手順1. 数式の中の()で囲われた部分を特殊な文字に置き換える
手順2. ()の中をノードにして子ノードとして追加
手順3. 全ての()が消えるまで 手順1.～手順2. を繰り返す

文章だけではわかりづらいと思うので、1+2*(3+4)+5*(6*(7+8)+(9+10)) を例に図を交えて説明します.

1) 最初の状態

2) 1+2*(3+4)+5*(6*(7+8)+(9+10))の(...)を#に置き換えて(...)の中身を子ノードにして下へ追加

3) 6*(7+8)+(9+10)の(...)を#に置き換えて(...)の中身を子ノードにして下へ追加

()が全て消えたので木構造の完成です.

ソースコード

以上の処理をソースコードにすると以下のようになると思います

private const string Replaced = "#";

// 数式を構文解析して木構造を作る
private static void Parse(char[] c)
{
  Node root = new Node(); // 最上位ノード
  Node target = root; // 現在見ているノード
  string text = "";
  for (int i = 0; i < c.Length; i++)
  {
    switch (c[i])
    {
      case '(':
        {
          target.formula += Replaced;

          // 子ノードを追加
          Node node = new Node();
          target.Add(node);
          target = node;
        }
        break;
      case ')':
        target = target.parent;
        break;
      default:
        target.formula += c[i];
        break;
    }
  }

  // Consoleへ木構造の中身を表示
  root.Log();
}

// ノード
public class Node
{
  // 数式
  public string formula = "";

  // 子ノード
  public List<Node> childs = new List<Node>();

  // 親ノード
  public Node parent { get; private set; }

  public void Add(Node node)
  {
    node.parent = this;
    this.childs.Add(node);
  }

  public void Log()
  {
    Debug.Log(this.formula);
    foreach(var child in this.childs)
    {
      child.Log();
    }
  }
}

実行してみる

Parse() に"1+2*(3+4)+5*(6*(7+8)+(9+10))"を渡すと以下のような出力になります

以下のような木構造になっていることが確認できました.

§2. 木構造の計算

以下のような手順で木構造化された数式を計算させていきます.
　ノードを計算させる.
　計算途中で"#"を見つけた場合, 計算を中断して子ノードを計算させる。　
　計算が完了したら親ノードへ計算結果を返す.

これも文章だけではわかりづらいと思うので、図を交えつつ説明します。

初期状態

3+4を計算し、計算結果を親ノードへ返す. (左側の#に7を入れる)

次に6*#+#の計算に移動。ここにも#があるので更に下のノードへ移り、7+8を計算。
計算結果を親ノードへ返す.(左側の#に15を入れる)

9+10も計算して結果を親ノードへ返す.(#に19を入れる)

6*15+19の計算結果を親ノードへ返す(#に109を入れる)

1+2*7+5*109 = 560

計算完了。

ソースコード

以上の処理をソースコードにすると以下のようになります.

// 数式を計算
private static void Eval(string formula)
{
  List<char> list = new List<char>(formula);

  // 空白全消去
  list.RemoveAll(x => x == ' ');

  char[] c = list.ToArray();

  // 構文解析
  Node node = Parse(c);

  // 計算
  double result = Eval(node);

  // 計算結果をConsoleへ出力
  Debug.Log(formula + " = " + result);
}

// cが数かどうかの判定
private static bool IsNumber(char c)
{
  return char.IsDigit(c) || c == 'x' || c == 'X' || c == '#';
}

// ノードの数式を計算
private static double Eval(Node node)
{
  List<string> ns; // 数
  List<char> os; // 演算子

  // 字句解析
  LexicalAnalysis(node.formula, out ns, out os);

  // nsを元に数字を決定
  var numbers = new List<double>();
  {
    int child = 0;
    for (int i = 0; i < ns.Count; i++)
    {
      double num = 0.0;

      switch (ns[i])
      {
        case "#":
          num = Eval(node.childs[child++]);
          break;
        default:
          double.TryParse(ns[i], out num);
          break;
      }
      numbers.Add(num);
    }
  }

  // かけ算・わり算を行なう
  {
    for (int i = 0; i < os.Count;)
    {
      switch (os[i])
      {
        case '*':
          {
            double left = numbers[i];
            double right = numbers[i + 1];
            numbers[i] = left * right;
            numbers.RemoveAt(i + 1);
            os.RemoveAt(i);
          }
          break;
        case '/':
          {
            double left = numbers[i];
            double right = numbers[i + 1];
            numbers[i] = left / right;
            numbers.RemoveAt(i + 1);
            os.RemoveAt(i);
          }
          break;
        default:
          i++;
          break;
      }
    }
  }

  // 足し算・引き算を行なう    
  double total = numbers[0];
  {
    for (int i = 0; i < os.Count; i++)
    {
      switch (os[i])
      {
        case '+':
          total += numbers[i + 1];
          break;
        case '-':
          total -= numbers[i + 1];
          break;
      }
    }
  }

  return total;
}

// 字句解析
private static void LexicalAnalysis(string str, out List<string> ns, out List<char> os)
{
  ns = new List<string>();
  os = new List<char>();

  string text = "";
  for (int i = 0; i < str.Length; i++)
  {
    switch (str[i])
    {
      case '+':
      case '-':
      case '*':
      case '/':
        ns.Add(text);
        os.Add(str[i]);
        text = "";
        break;
      default:
        if (IsNumber(str[i]))
        {
          text += str[i];
          if (i == str.Length - 1)
          {
            ns.Add(text);
            text = "";
          }
        }
        break;
    }
  }

  // 字句解析結果をConsoleへ出力
  // string nt = "";
  // string ot = "";
  // foreach (var n in ns) { nt += n + ", "; }
  // foreach (var o in os) { ot += o + ", "; }
  // Debug.Log("数 : { " + nt + " }");
  // Debug.Log("演算子 : { " + ot + " }");
}

実行してみる

正しく計算されていることが分かりました.

ソースコード全体 (エディター拡張で木構造を表示させるおまけつき)

Formula.cs

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

#if UNITY_EDITOR
using UnityEditor;
[CustomEditor(typeof(Formula))]
public class FormulaInspector : Editor
{
  // Unity インスペクター拡張
  public override void OnInspectorGUI()
  {
    // ボタンを押したら数式パーサー実行
    if (GUILayout.Button("Parse", GUILayout.Width(100)))
    {
      Formula g = target as Formula;
      Eval(g.formula);
    }
    base.OnInspectorGUI();
  }

  // 数式を計算
  private static void Eval(string formula)
  {
    List<char> list = new List<char>(formula);

    // 空白全消去
    list.RemoveAll(x => x == ' ');

    char[] c = list.ToArray();

    // 構文解析
    Node node = Parse(c);

    // 計算
    double result = Eval(node);

    Debug.Log(formula + " = " + result);

    // 木構造を表示
    FormulaNodeWindow.RootNode = node;
    EditorWindow.GetWindow<FormulaNodeWindow>();
  }

  // cが数かどうかの判定
  private static bool IsNumber(char c)
  {
    return char.IsDigit(c) || c == 'x' || c == 'X' || c == '#';
  }

  // 数式を計算
  private static double Eval(Node node)
  {
    List<string> ns; // 数
    List<char> os; // 演算子

    // 字句解析
    LexicalAnalysis(node.formula, out ns, out os);

    // nsを元に数字を決定
    var numbers = new List<double>();
    {
      int child = 0;
      for (int i = 0; i < ns.Count; i++)
      {
        double num = 0.0;

        switch (ns[i])
        {
          case "#":
            num = Eval(node.childs[child++]);
            break;
          default:
            double.TryParse(ns[i], out num);
            break;
        }
        numbers.Add(num);
      }
    }

    // かけ算・わり算を行なう
    {
      for (int i = 0; i < os.Count;)
      {
        switch (os[i])
        {
          case '*':
            {
              double left = numbers[i];
              double right = numbers[i + 1];
              numbers[i] = left * right;
              numbers.RemoveAt(i + 1);
              os.RemoveAt(i);
            }
            break;
          case '/':
            {
              double left = numbers[i];
              double right = numbers[i + 1];
              numbers[i] = left / right;
              numbers.RemoveAt(i + 1);
              os.RemoveAt(i);
            }
            break;
          default:
            i++;
            break;
        }
      }
    }

    // 足し算・引き算を行なう    
    double total = numbers[0];
    {
      for (int i = 0; i < os.Count; i++)
      {
        switch (os[i])
        {
          case '+':
            total += numbers[i + 1];
            break;
          case '-':
            total -= numbers[i + 1];
            break;
        }
      }
    }

    return total;
  }

  // 字句解析
  private static void LexicalAnalysis(string str, out List<string> ns, out List<char> os)
  {
    ns = new List<string>();
    os = new List<char>();

    string text = "";
    for (int i = 0; i < str.Length; i++)
    {
      switch (str[i])
      {
        case '+':
        case '-':
        case '*':
        case '/':
          ns.Add(text);
          os.Add(str[i]);
          text = "";
          break;
        default:
          if (IsNumber(str[i]))
          {
            text += str[i];
            if (i == str.Length - 1)
            {
              ns.Add(text);
              text = "";
            }
          }
          break;
      }
    }

    // 字句解析結果をConsoleへ出力
    //string nt = "";
    //string ot = "";
    //foreach (var n in ns) { nt += n + ", "; }
    //foreach (var o in os) { ot += o + ", "; }
    //Debug.Log("数 : { " + nt + " }");
    //Debug.Log("演算子 : { " + ot + " }");
  }

  // 数式の構文解析
  private static Node Parse(char[] c)
  {
    Node root = new Node();
    Node target = root;
    string text = "";
    for (int i = 0; i < c.Length; i++)
    {
      switch (c[i])
      {
        case '(':
          {
            target.formula += "#";

            // 子ノードを追加
            Node node = new Node();
            target.Add(node);
            target = node;
          }
          break;
        case ')':
          {
            target = target.parent;
          }
          break;
        default:
          target.formula += c[i];
          break;
      }
    }

    // 構文解析結果表示
    //root.Log();

    return root;
  }

  public class Node
  {
    // 数式
    public string formula = "";

    // 子ノード
    public List<Node> childs = new List<Node>();

    // 親ノード
    public Node parent { get; private set; }

    public void Add(Node node)
    {
      node.parent = this;
      this.childs.Add(node);
    }

    public void Log()
    {
      Debug.Log(this.formula);
      foreach (var child in this.childs)
      {
        child.Log();
      }
    }
  }
}
#endif // UNITY_EDITOR

public class Formula : MonoBehaviour
{
  public string formula = "1+2*(3+4)+5*(6*(7+8)+(9+10))";
}

// 木構造をウィンドウで表示させるエディター拡張
public class FormulaNodeWindow : EditorWindow
{
  public static FormulaInspector.Node RootNode;

  protected void OnGUI()
  {
    BeginWindows();
    if (RootNode != null)
    {
      id = 0;
      this.Draw(RootNode, new Vector2(200, 200));
    }
    EndWindows();
  }

  static int id = 0;
  static Rect GetWindowRect(Vector2 pos)
  {
    const int SizeX = 120;
    const int SizeY = 45;
    Rect window = new Rect(pos, new Vector2(SizeX, SizeY));
    return window;
  }
  public void Draw(FormulaInspector.Node node, Vector2 position)
  {
    Rect window = GetWindowRect(position);
    GUI.Window(id++, window, DrawNodeWindow, node.formula);   // Updates the Rect's when these are dragged

    Vector2 left = position + new Vector2(-100, 100);
    Vector2 right = position + new Vector2(100, 100);
    Vector2 center = position + new Vector2(0, 100);
    int n = node.childs.Count;

    if (n == 1)
    {
      Vector2 childPos = center;
      Rect childWindow = GetWindowRect(childPos);

      DrawNodeLine(window, childWindow); // Here the curve is drawn under the windows
      Draw(node.childs[0], childPos);
    }
    else
    if (n > 1)
    {
      for (int i = 0; i < n; i++)
      {
        float t = i / (n - 1);
        Vector2 childPos = Vector2.Lerp(left, right, t);
        Rect childWindow = GetWindowRect(childPos);

        DrawNodeLine(window, childWindow); // Here the curve is drawn under the windows
        Draw(node.childs[i], childPos);
      }
    }
  }

  void DrawNodeWindow(int id)
  {
    GUI.DragWindow();
    //GUI.Label(new Rect(30, 22, 100, 100), "id = " + id, EditorStyles.label);
  }

  static void DrawNodeLine(Rect start, Rect end)
  {
    Vector3 startPos = new Vector3(start.x + start.width / 2, start.y + start.height / 2, 0);
    Vector3 endPos = new Vector3(end.x + end.width / 2, end.y + end.height / 2, 0);
    Color shadowCol = new Color(0, 0, 0, 0.06f);

    Handles.DrawLine(startPos, endPos);
  }
}

【Unity】エディター拡張で木構造を表示させる
http://qiita.com/r-ngtm/items/9df4629a27cb080bfc70