はじめに
ずいぶん時間が空いてしまいましたがデザインパターンの記事投稿です。
前回はTemplateMethodパターンとFactoryMethodパターンを紹介しました。
今回はCompositeパターンについてまとめていきたいと思います。
Compositeパターン
ソフト開発においてフォルダ構造を扱うことは非常に多くありますよね。
フォルダ構造を操作する際、例えばファイル、フォルダを削除したい場合を考えます。それらは同じように削除したいですよね。
フォルダ構造をはじめとする木構造の操作を行うのに便利なのがこのCompositeパターンです。
Compositeパターンには異なる役割を持つ要素が3つ存在します。
Leaf
子要素を持たないオブジェクト。
Component
子要素を持つことができるオブジェクト。ここで再帰処理を行います。
Composite
共通の操作を定義するインターフェース。Leaf、Componentはこのインターフェースを実装します。
上のように実装することでフォルダ、同一の処理を行うことができるようになります。
Compositeパターンを用いて逆ポーランド記法の計算を行う
今回はCompositeパターンを用いて逆ポーランド記法の計算を行うプログラムを作成してみました。
クラス図は以下になります。
2分木を用いて逆ポーランド記法の計算を行う際、数字(Number)は子要素を持ちえません。そのためCompositeパターンでいうLeafとなります。逆に演算子(Operator)は子要素を持ち得るのでCompositeとなります。
また、「計算する」という処理を行わせたいためComponentとしてCalculatableインターフェースを定義します。
public interface Calculatable
{
/// <summary>
/// 計算を行う
/// </summary>
int Calculate();
}
/// <summary>
/// 逆ポーランド記法で計算するための数値を表すクラス
/// </summary>
public class Number : Calculatable
{
private int value;
public Number(int value)
{
this.value = value;
}
public int Value => value;
///<inheritdoc />
public int Calculate()
{
return value;
}
}
/// <summary>
/// 逆ポーランド記法で計算するための演算子を表すクラス
/// </summary>
public class Operator : Calculatable
{
private char operand;
private Calculatable leftChild;
private Calculatable rightChild;
public Operator(char operand, Calculatable leftChild, Calculatable rightChild)
{
this.operand = operand;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
///<inheritdoc />
public int Calculate()
{
switch (operand)
{
case '+':
return leftChild.Calculate() + rightChild.Calculate();
case '-':
return leftChild.Calculate() - rightChild.Calculate();
case '*':
return leftChild.Calculate() * rightChild.Calculate();
case '/':
return leftChild.Calculate() / rightChild.Calculate();
default:
throw new InvalidOperationException("誤まった演算子です");
}
}
public class Program
{
/// <summary>
/// コンソールから入力した式を逆ポーランド記法で計算し答えを表示する
/// </summary>
public static void Main()
{
//コンソールから入力した式を逆ポーランド記法で計算し答えを表示する
Console.WriteLine("式を入力してください");
var input = Console.ReadLine();
var expression = (Operator)RPNParse(input);
Console.WriteLine(expression.Calculate());
}
/// <summary>
/// 文字列を逆ポーランド記法で解析し、計算可能なオブジェクトを返す
/// </summary>
/// <param name="input">入力文字列</param>
public static Calculatable RPNParse(string input)
{
string[] tokens = Regex.Split(input,@"\s");
//木を作る
var stack = new Stack<Calculatable>();
foreach (var token in tokens)
{
if (int.TryParse(token, out int value))
{
stack.Push(new Number(value));
}
else
{
var right = stack.Pop();
var left = stack.Pop();
stack.Push(new Operator(token[0], left, right));
}
}
return stack.Pop();
}
}
再帰処理のパフォーマンス低下と危険性
上のOperator.csのCalculate()では再帰処理を用いて子の計算を行っています。
逆ポーランド記法を二分木で計算する際、大きな式になればなるほど二分木の深さは深くなっていきます。再帰処理で葉の部分まで参照しに行くとき、関数のローカル変数や戻りアドレスなどの多くの履歴を保持することになります。履歴を保存しておくスタックメモリには限度があるため言語によってはStackOverFlowの例外を出す恐れがあります。
また余計なメモリの確保のためにパフォーマンスが低下することもあります。
このような時は再帰処理ではなくStackなどのフラットなコレクションとハイブリッドな設計をするのが良いです。
Stackを用いて実装しなおしたものは以下となります。
/// <summary>
/// Calculate()を再帰処理を用いずにStackを用いて計算する
/// </summary>
public int CalculateWithStack()
{
//調査しようとしているもの
var stack1 = new Stack<Calculatable>();
//逆ポーランド記法の並びに変換後
var stack2 = new Stack<Calculatable>();
stack1.Push(this);
while (stack1.Count > 0)
{
var current = stack1.Pop();
if (current is Operator op)
{
stack1.Push(op.leftChild);
stack1.Push(op.rightChild);
}
stack2.Push(current);
}
var stack3 = new Stack<int>();
while (stack2.Count > 0)
{
var current = stack2.Pop();
if (current is Number num)
{
stack3.Push(num.Value);
}
else if (current is Operator op)
{
var right = stack3.Pop();
var left = stack3.Pop();
switch (op.operand)
{
case '+':
stack3.Push(left + right);
break;
case '-':
stack3.Push(left - right);
break;
case '*':
stack3.Push(left * right);
break;
case '/':
stack3.Push(left / right);
break;
default:
throw new InvalidOperationException("誤まった演算子です");
}
}
}
return stack3.Pop();
}
おわりに
今回はデザインパターンの一つであるCompositeパターンについて紹介しました。
Compositeパターンのメリットとして木構造を扱うことができること、中身を同一視できることを挙げました。またCompositeパターンを用いて逆ポーランド記法の計算を行うプログラムを記述しました。
今後も引き続きはりきってデザインパターンを学習していきたいと思います！！
ありがとうございました！