【C#】逆ポーランドコンバータを改良する①

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

今回は、こないだの変換器で括弧に対応させていきたいと思います。やること自体は少ないですが、記事を書くのがめんどくさくなったわけではありません。たまたまです。

実装

てことで早速いじっていきたいと思います。

トークン解析

まずは、数式を分解するときに括弧に対応させる必要があります。変更箇所は2箇所です。

var regex = new System.Text.RegularExpressions.Regex(@"([+\-*/()])");

if(Regex.IsMatch(t, regex_.ToString())) {
  var priority = 0;
  if(t.Equals("(") | t.Equals(")")) {
    priority = 4;
  } else 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<List<Token>>();
opStack.Add(new List<Token>());
 
var quoted = 0;
 
foreach(var t in _token) {
  if(t.kind_ == Token.Kind.Number) {
    rpn.Add(t);
  } else {
    if(t.value_.Equals("(")) {
      quoted++;
      opStack.Add(new List<Token>());
    } else if(t.value_.Equals(")")) {
      opStack[quoted].Reverse();
      rpn.AddRange(opStack[quoted]);
      quoted--;
    } else {
      while(opStack[quoted].Count() != 0 &amp;&amp; t.priority_ <= opStack[quoted].Last().priority_) {
        rpn.Add(opStack[quoted].Last());
        opStack[quoted].RemoveAt(opStack[quoted].Count() - 1);
      }
 
      opStack[quoted].Add(t);
    }
  }
}
 
opStack[0].Reverse();
rpn.AddRange(opStack[0]);

基本的なアルゴリズム自体は昨日紹介した手法と何ら変わりません。違いとしては、(を見つけたら新しくスタックを用意し、)を見つけたらスタックを反転して取り出すようにしています。quortedが括弧の深度を現しています。

ということで、今回は少し内容が薄いですが括弧が入った数式をRPNへと変換することができました。明日の記事ではsinやcosなどの特定の数式に対応させて、RPNコンバータを完成とします。