【C#】逆ポーランドコンバータを実装する

この記事はひとりアドベントカレンダー2020の1日目の記事だったものです。

さて唐突ですが、逆ポーランド記法(以降、RPN : Reverse Polish Notation)というものをご存知でしょうか？おそらく、電卓プログラムを作ろうとした人は一度は耳にしたことがあるのではないでしょうか。日本語では後置記法と呼ばれる記法になります。対して、私達が通常使う記法のことを中置記法と呼びます。RPNでの最大のメリットは、括弧を必要としないという点です(？)

先に上げた2つの記法を例に挙げると、それぞれ↓のような感じになります。

中置記法
1 + 2 * 3 - 4
後置記法
1 2 3 * + 4 -

RPNへの変換 / 計算

先程、RPNのメリットは括弧が要らない点と言いましたが、括弧がある式をいきなり変換アルゴリズムとして挙げるのはめんどくさいので、今回は単純な四則演算のみを例にとってアルゴリズムを組み上げていきます。また、「負数」と「減算」を区別するのがややこしいのでそれも今回は扱わないことにします。

アルゴリズムのイメージはこの記事が参考になると思います。

トークン解析

まずは数式を数値と演算子に分解します。この処理は正規表現を使って一気にやってしまいます。Regex.Split()を使用すると、正規表現に従って分割された文字列のリストを取得することができます。

// 各トークンを表現するためのクラス
public class Token{
  // トークンの種類を示す列挙体
  public enum Kind {
    Number,
    Operator
  }
 
  public int priority_;　　// そのトークンの優先度
  public Kind kind_;       // トークンの種類 
  public string value_;    // トークンの値
}  
  
var regex = new System.Text.RegularExpressions.Regex(@"([+\-*/])");
var token = System.Text.RegularExpressions.Regex.Split("<解析対象の数式>", regex.ToString());
var tokenized = new List<Token>();
// 分割されたものを優先度付きでTokenオブジェクトに変換する
foreach(var t in token) {
  if(Regex.IsMatch(t, regex_.ToString())) {
    // イテレート中のものが演算子の場合
    var priority = 0;
    if(t.Equals("/")) {
      // 除算の優先度が最高
      priority = 3;
    } else if(t.Equals("*")) {
      // 乗算の優先度が次点
      priority = 2;
    } else {
      // 加減算の優先度は最低
      priority = 1;
    }
    tokenized.Add(new Token() { kind_ = Token.Kind.Operator, value_ = t, priority_ = priority });
  } else {
    // イテレート中の要素が数値の場合
    tokenized.Add(new Token() { kind_ = Token.Kind.Number, value_ = t, priority_ = 0 });
  }
}

トークン優先度による置換

トークン優先度による置換と難しく書いてますが、実際には演算子の優先順位に応じてスタックに詰めていく作業です。

var rpn = new List<Token>();
var opStack = new List<Token>();
 
foreach(var t in tokenized) {
  if(t.kind_ == Token.Kind.Number) {
    // イテレート中の要素が数値の場合、スタックにそのまま乗せる
    rpn.Add(t);
  } else {
    // イテレート中の要素が演算子の場合
    while(opStack.Count() != 0 &amp;&amp; t.priority_ <= opStack.Last().priority_) {
      // 演算子スタックの末尾要素の優先度がイテレート中の演算子よりも低くなるまでポップする
      rpn.Add(opStack.Last());
      opStack.RemoveAt(opStack.Count() - 1);
    }
    // 演算子スタックに乗せる
    opStack.Add(t);
  }
}
// 最終的にスタックに残った演算子を取り出さなければいけないが、ひっくり返っているためReverse()する
opStack.Reverse();
rpn.AddRange(opStack);

計算

トークン解析を終え、スタックに詰めたらあとは計算をしていくだけです。基本的な手順としては、スタックから取り出してそれが数値だったらバッファに乗せ、演算子だったらバッファから2要素取り出して演算し、バッファに戻します。

var stack = new List<double>();
 
foreach(var t in _token) {
  if(t.kind_ == Token.Kind.Number) {
    // 数値の場合、バッファに乗せる
    stack.Add(double.Parse(t.value_));
  } else {
    // 演算子の場合
    var lhs = 0.0;
    var rhs = 0.0;
    if(stack.Count() >= 2) {
      rhs = stack.Last();
      stack.RemoveAt(stack.Count() - 1);
      lhs = stack.Last();
      stack.RemoveAt(stack.Count() - 1);
    } else {
      // バッファの要素が2に満たない場合、数式が破綻している(今回はUnaryMinusを考慮しないため)
      throw new Exception("この計算はできません．");
    }
 
 
    if(t.value_.Equals("+")) {
      stack.Add(lhs + rhs);
    } else if(t.value_.Equals("-")) {
      stack.Add(lhs - rhs);
    } else if(t.value_.Equals("*")) {
      stack.Add(lhs * rhs);
    } else if(t.value_.Equals("/")) {
      if(rhs == 0) {
        // ゼロ除算
        throw new Exception("この計算はできません．");
      }
      stack.Add(lhs / rhs);
    }
  }
}
// 最終的にバッファに残っているものが計算結果になるはず
stack.Last().ToString("#############0.##############");

とまぁこんな感じで中置記法から後置記法への変換を行いました。明日の記事では括弧に対応したコンバータを作ります(アドカレ、そもそもひとりで書くものじゃないけど、ひとりで書くならシリーズ物になってもいいのか？？？)