Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@Takuto168(Takutooo 168)

[C#] 逆ポーランド演算器をジェネリック化して遊ぶ

Last updated at Posted at 2020-07-30

##謝辞

  • 本稿は、【逆ポーランド記法を利用した数式の計算】で紹介されている逆ポーランド記法（= Reverse Polish Notation, RPN）の計算を、【C# のジェネリック演算】で紹介されている手法を用いて「なんちゃってジェネリック化」して遊ぼうというテーマでお送りする。
  • クラス設計や実装方法においては、上記記事を存分に参考にさせて頂いた。逆ポーランド記法の定義や計算方法については前者、数値型のジェネリッククラスの作成方法は後者の記事リンクを参照されたい。

##ジェネリッククラスの実装

クラスのの全容は GitHub へ公開した．
https://github.com/Takuto168/Takuto168park/blob/master/RpnCalculator.cs

以下に，その実装方法と検証結果を示す．

###クラスの作成

  • 演算クラスは、静的ジェネリッククラスとした。
  • 四則演算の式木を組み立てるためにSystem.Linq.Expressions名前空間を、また文字列から数値への変換を行うTryParseメソッドを利用するためにSystem.Reflection名前空間を追加しておく。
  • 数値型でのクラス制約はできないため、仕方なく構造体での制約とした。代わりに、コンストラクタ内で型判定を行う。
RpnCalculator.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;

namespace RpnCalculator
{
    /// <summary>
    /// 逆ポーランド記法を計算する機能を提供します。
    /// </summary>
    public static class RpnCalculator<N> where N : struct
    {
        /// <summary>
        /// 逆ポーランド記法の演算に対応し得る型のリスト。
        /// </summary>
        private static Type[] _availableTypes => new[] { typeof(int),
                                                         typeof(uint),
                                                         typeof(short),
                                                         typeof(ushort),
                                                         typeof(long),
                                                         typeof(ulong),
                                                         typeof(decimal),
                                                         typeof(double),
                                                         typeof(float)};

        /// <summary>
        /// 静的クラスの生成時に、指定した数値型が演算に対応しているか判定します。
        /// </summary>
        static RpnCalculator()
        {
            if (!_availableTypes.Contains(typeof(N))) throw new NotSupportedException();
        }
    }
}

###数値型ジェネリッククラスの作成

  • 数値型の四則演算と文字列変換をサポートする静的ジェネリッククラスNumericalGenericを作成する。今回はRpnCalculatorの内部クラスとした。
  • 内部メンバには、各四則演算のデリゲートと、文字列変換メソッドのリフレクション実行を用意する。
RpnCalculator.cs
/// <summary>
/// 算術四則演算と文字列からの変換を行うためのジェネリック数値型クラスです。
/// </summary>
private static class NumericalGeneric
{
    /// <summary>
    /// 算術加算演算を行います。
    /// </summary>
    public static Func<N, N, N> Add { get; }

    /// <summary>
    /// 算術減算演算を行います。
    /// </summary>
    public static Func<N, N, N> Subtract { get; }

    /// <summary>
    /// 算術乗算演算を行います。
    /// </summary>
    public static Func<N, N, N> Multiply { get; }

    /// <summary>
    /// 算術除算演算を行います。
    /// </summary>
    public static Func<N, N, N> Divide { get; }

    /// <summary>
    /// 指定したジェネリック型を取得します。
    /// </summary>
    private static Type _type => typeof(N);

    /// <summary>
    /// 指定した数値型における文字列からの変換メソッドを取得します。
    /// </summary>
    private static MethodInfo _tryParseInvoker => _type.GetMethod("TryParse", new[] { typeof(string), _type.MakeByRefType() });

    /// <summary>
    /// 静的クラスの生成時に、算術四則演算デリゲートを作成します。
    /// </summary>
    static NumericalGeneric()
    {
        var p1 = Expression.Parameter(typeof(N));
        var p2 = Expression.Parameter(typeof(N));
        Add = Expression.Lambda<Func<N, N, N>>(Expression.Add(p1, p2), p1, p2).Compile();
        Subtract = Expression.Lambda<Func<N, N, N>>(Expression.Subtract(p1, p2), p1, p2).Compile();
        Multiply = Expression.Lambda<Func<N, N, N>>(Expression.Multiply(p1, p2), p1, p2).Compile();
        Divide = Expression.Lambda<Func<N, N, N>>(Expression.Divide(p1, p2), p1, p2).Compile();
    }

    /// <summary>
    /// 数値の文字列形式を、それと等価なジェネリック数値型に変換します。 戻り値は、変換が成功したかどうかを示します。
    /// </summary>
    /// <param name="s">変換する数値を格納する文字列。</param>
    /// <param name="result">変換が成功した場合、このメソッドが返されるときに、s に格納された数値と等価のジェネリック数値を格納します。変換に失敗した場合は 0 を格納します。</param>
    /// <returns>s が正常に変換された場合は true。それ以外の場合は false。</returns>
    public static bool TryParse(string s, out N result)
    {
        if (_tryParseInvoker == null)
        {
            // Reflection で N.TryParse メソッドを取得できなかった場合
            result = default(N);
            return false;
        }
        var args = new object[] { s, null };
        if (!(bool)_tryParseInvoker.Invoke(null, args))
        {
            // 変換失敗
            result = default(N);
            return false;
        }
        result = (N)args[1];
        return true;
    }
}

###トークン構造体の作成

  • トークンは、演算子または数値を示す。
  • 構造体メンバには、演算子とその実行処理のマッピングを実装し、与えられた演算を実行できるようにした。
  • 補助機能として、指定したトークン文字列を数値に置き換えるためのマッピングを与えることで、数値への代入を可能にした。
RpnCalculator.cs
/// <summary>
/// 逆ポーランド記法における1つのトークンを表す構造体です。
/// </summary>
private struct Token
{
    /// <summary>
    /// 演算子を表す文字列とその実行処理のマッピング。
    /// </summary>
    private static readonly Dictionary<string, Func<N, N, N>> _operaters
        = new Dictionary<string, Func<N, N, N>>() {
                                                      { "+", (d1, d2) => NumericalGeneric.Add(d1, d2) },
                                                      { "-", (d1, d2) => NumericalGeneric.Subtract(d1, d2) },
                                                      { "*", (d1, d2) => NumericalGeneric.Multiply(d1, d2) },
                                                      { "/", (d1, d2) => NumericalGeneric.Divide(d1, d2) }
                                                  };

    /// <summary>
    /// トークンが演算子であるかどうかを取得します。
    /// </summary>
    public bool IsOperater => !string.IsNullOrEmpty(this.Operater);

    /// <summary>
    /// トークンが演算子であるとき、その文字列を取得します。
    /// </summary>
    public string Operater { get; }

    /// <summary>
    /// トークンが数値であるとき、その値を取得します。
    /// </summary>
    public N Value { get; }

    /// <summary>
    /// 逆ポーランド記法の文字列からトークンを生成します。
    /// </summary>
    /// <param name="s">逆ポーランド記法のトークンを表す文字列。</param>
    /// <param name="replacePrams">指定したトークン文字列を数値に置き換えるためのマッピング。</param>
    public Token(string s, Dictionary<string, N> replacePrams)
    {
        if (_operaters.ContainsKey(s))
        {
            // 演算子の場合
            this.Value = default(N);
            this.Operater = s;
        }
        else
        {
            // 数値の場合
            if (replacePrams?.ContainsKey(s) ?? false)
                this.Value = replacePrams[s];  // 指定したトークン文字列を数値に置き換え
            else if (NumericalGeneric.TryParse(s, out var t))
                this.Value = t;                // N.TryParse によって変換に成功
            else
                throw new FormatException();   // 認識できない文字列
            this.Operater = null;
        }
    }

    /// <summary>
    /// 2つのトークンに対してトークンの示す算術演算を行い、その結果から新たなトークンを作成します。
    /// 引数は、Stack<T>から取り出されることを想定して順序が判定していることに留意してください。
    /// </summary>
    /// <param name="d2">2つ目の数値。</param>
    /// <param name="d1">1つ目の数値。</param>
    /// <returns></returns>
    public Token Operate(N d2, N d1) => new Token(_operaters[this.Operater](d1, d2));

    /// <summary>
    /// 数値型のトークンを生成します。
    /// </summary>
    /// <param name="value">数値。</param>
    private Token(N value) => (this.Value, this.Operater) = (value, null);
}

###演算処理の実装

  • 逆ポーランド記法ではstackを用いて演算を行う。
  • 数値の場合はその値をstackにpushし、演算子の場合はstackから値を２つ取り出し計算を行い、その結果をstackにpushする。
RpnCalculator.cs
/// <summary>
/// 逆ポーランド記法の演算を行います。
/// </summary>
/// <param name="exp">式。</param>
/// <param name="replaceParams">指定したトークン文字列を数値に置き換えるためのマッピング。</param>
/// <returns>結果値。</returns>
private static N CalculateInvoker(string exp, Dictionary<string, N> replaceParams)
{
    var stack = new Stack<Token>();
    foreach (var s in exp.Split(' ').Where(s => !string.IsNullOrEmpty(s)))
    {
        var token = new Token(s, replaceParams);
        stack.Push(token.IsOperater ? token.Operate(stack.Pop().Value, stack.Pop().Value) : token);
    }

    return stack.Pop().Value;
}

###外部公開用メソッドの実装

  • 指定したトークン文字列を数値に置き換えるためのマッピングを与えるために、いくつかのpublicな静的メソッドをオーバーロードした。
RpnCalculator.cs
/// <summary>
/// 逆ポーランド記法の演算を行います。
/// </summary>
/// <param name="exp">式。</param>
/// <returns>結果値。</returns>
public static N Calculate(string exp) => CalculateInvoker(exp, null);

/// <summary>
/// 逆ポーランド記法の演算を行います。
/// </summary>
/// <param name="exp">式。</param>
/// <param name="replaceParam">指定したトークン文字列を数値に置き換えるためのマッピング。</param>
/// <param name="replaceParams">指定したトークン文字列を数値に置き換えるためのマッピング。</param>
/// <returns>結果値。</returns>
public static N Calculate(string exp, (string Key, N Value) replaceParam, params (string Key, N Value)[] replaceParams)
{
    var valueList = new Dictionary<string, N>(replaceParams.Length + 1);
    valueList.Add(replaceParam.Key, replaceParam.Value);
    valueList.AddRange(replaceParams);
    return CalculateInvoker(exp, valueList);
}

/// <summary>
/// 逆ポーランド記法の演算を行います。
/// </summary>
/// <param name="exp">式。</param>
/// <param name="replaceParams">指定したトークン文字列を数値に置き換えるためのマッピング。</param>
/// <returns>結果値。</returns>
public static N Calculate(string exp, IEnumerable<(string Key, N Value)> replaceParams)
    => CalculateInvoker(exp, replaceParams.ToDictionary(t => t.Key, t => t.Value));

/// <summary>
/// 逆ポーランド記法の演算を行います。
/// </summary>
/// <param name="exp">式。</param>
/// <param name="replaceParam">指定したトークン文字列を数値に置き換えるためのマッピング。</param>
/// <param name="replaceParams">指定したトークン文字列を数値に置き換えるためのマッピング。</param>
/// <returns>結果値。</returns>
public static N Calculate(string exp, N replaceParam, params N[] replaceParams)
{
    var valueList = new List<N>(replaceParams.Length + 1);
    valueList.Add(replaceParam);
    foreach (var item in replaceParams) valueList.Add(item.Key, item.Value);
    return Calculate(exp, valueList);
}

/// <summary>
/// 逆ポーランド記法の演算を行います。
/// </summary>
/// <param name="exp">式。</param>
/// <param name="replaceParams">指定したトークン文字列を数値に置き換えるためのマッピング。</param>
/// <returns>結果値。</returns>
public static N Calculate(string exp, IEnumerable<N> replaceParams)
    => CalculateInvoker(exp, replaceParams.Select((Item, Index) => new { Item, Index }).ToDictionary(v => v.Index.ToString("{0}"), v => v.Item));

##検証

せっかくジェネリック化したので、様々な型で計算を行ってみる。

###整数演算

  • 単純な整数の計算を行ってみる。パラメータは以下のように代入可能。
Console.WriteLine(RpnCalculator<int>.Calculate("1 2 + 3 4 + *"));   // 21
Console.WriteLine(RpnCalculator<int>.Calculate("{0} {1} + {2} {3} + *", 1, 2, 3, 4));   // 21
Console.WriteLine(RpnCalculator<int>.Calculate("A B + C D + *", ("A", 1), ("B", 2), ("C", 3), ("D", 4)));   // 21

###オーバーフローとアンダーフロー

エラーは起きないが、オーバーフローとアンダーフローはしっかり起きていることが分かる。

Console.WriteLine(RpnCalculator<int>.Calculate("{0} 1 +", int.MaxValue, 1));     // -2147483648
Console.WriteLine(RpnCalculator<long>.Calculate("{0} 1 +", int.MaxValue, 1));    // 2147483648
Console.WriteLine(RpnCalculator<int>.Calculate("{0} 1 -", int.MinValue, 1));     // 2147483647
Console.WriteLine(RpnCalculator<long>.Calculate("{0} 1 -", int.MinValue, 1));    // -2147483649

###型による演算結果の相違

  • 浮動小数型によって桁差が発生している。また、小数文字列から整数型への変換は失敗している。
Console.WriteLine(RpnCalculator<int>.Calculate("1 3 /"));       // 0
Console.WriteLine(RpnCalculator<float>.Calculate("1 3 /"));     // 0.3333333
Console.WriteLine(RpnCalculator<double>.Calculate("1 3 /"));    // 0.333333333333333
Console.WriteLine(RpnCalculator<decimal>.Calculate("1 3 /"));   // 0.3333333333333333333333333333
Console.WriteLine(RpnCalculator<int>.Calculate("3.14 3.14 +"));   // FormatException
Console.WriteLine(RpnCalculator<int>.Calculate("pi pi +", ("pi", (int)Math.PI)));   // 6
Console.WriteLine(RpnCalculator<float>.Calculate("pi pi +", ("pi", (float)Math.PI)));   // 6.283185
Console.WriteLine(RpnCalculator<double>.Calculate("pi pi +", ("pi", Math.PI)));   // 6.28318530717959
Console.WriteLine(RpnCalculator<decimal>.Calculate("pi pi +", ("pi", (decimal)Math.PI)));   // 6.28318530717958

###0除算

  • 当然エラーになるが、double型では非数を実装しているため、表示が下記の3パターンとなった。
Console.WriteLine(RpnCalculator<int>.Calculate("1 0 /"));       // DivideByZeroException
Console.WriteLine(RpnCalculator<double>.Calculate("0 0 /"));    // NaN
Console.WriteLine(RpnCalculator<double>.Calculate("1 0 /"));    // ∞
Console.WriteLine(RpnCalculator<double>.Calculate("-1 0 /"));   // -∞
0
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?