C#:逆ポーランド記法を利用した数式の計算(2) 数式をトークンに分割する

逆ポーランド記法を利用した数式の計算(1) 逆ポーランド記法の計算
逆ポーランド記法を利用した数式の計算(2) 数式をトークンに分割する ← 当記事
逆ポーランド記法を利用した数式の計算(3) ReversePolishNotationクラスを改良する
逆ポーランド記法を利用した数式の計算(4) Contextクラスを定義する
逆ポーランド記法を利用した数式の計算(5) Interpreterパターンで数式を解析する
逆ポーランド記法を利用した数式の計算(6) 最後の仕上げ

第１回目の逆ポーランド記法の計算では、1 5 + 2 3 + *といった逆ポーランド記法の式を計算するプログラムを紹介しました。その記事の続きです。

どんなプログラムを作るか

逆ポーランド記法で表現された式を計算することができましたので、一般的な書式で書かれた数式(加減乗除を行う式)を逆ポーランド記法に変換できれば、数式の計算をするプログラムを作成できます。

つまり、(2 + 4) * (8 - 6) といった式（文字列）を逆ポーランド記法に変換し、それを計算するプログラムを作成しようということです。

ということで、以下のような感じで利用できるクラスを作成したいと思います。

    var ans = Expression.Calculate("3 * (4 + 2)");

Expression.Calculateメソッドの中は、こんな感じ

    public static decimal Calculate(string exp) {
        // 数式を逆ポーランド記法へ変換
        ReversePolishNotation rpn = ConvertToRpn(exp);
        // 逆ポーランド記法の式を計算する
        return RpnCalculator.Calculate(rpn);
    }

以下のような、インスタンスメソッドにしても良いかなとも思ったのですが、前回、RpnCalculatorクラス定義して、そこにstaticメソッドとして定義してしまったので、変更せずに、このまま行こうと思います。

return rpn.Calculate();

式をトークンに分解

ということで、上記のRpnCalculator.Calculateメソッドは、前回のコードをそのまま利用します。shiracamusさんにコメントで提示していただいた、よりスマートなコードを使っても良いですね。

また、ReversePolishNotationクラスも少し変更すれば大丈夫そうです。

問題は、ConvertToRpnメソッドです。いきなりConvertToRpnメソッドのコードを書き始めるのは、さすがに無謀です。

ということで、まずは、"(2 + 34) * (28 - 6)" といった文字列を 以下に示すようなトークンに分割するクラスを作成しようと思います。

"("
"2"
"+"
"34"
")"
"*"
"("
"28"
"-"
"6"
")"

クラス名はTokenizerとしました。公開メンバーは、MoveNextメソッドと、Currentプロパティのみです。
コンストラクタで、式(string型)を受け取ります。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Rpn.App {

    // Tokenに分解する
    public class Tokenizer {
        private string _expression;

        IEnumerator<string> _ite;

        public Tokenizer(string exp) {
            _expression = exp;
            _ite = GetTokens().GetEnumerator();
        }

        public bool MoveNext() {
            return _ite.MoveNext();
        }

        public string Current {
            get { return _ite.Current; }
        }

        private IEnumerable<string> GetTokens() {
            char c = NextChar();
            var token = "";
            while (c != (char)0) {
                if (char.IsDigit(c)) {
                    token += c;
                } else if (c == '.' && token.All(x => x != '.')) {
                    token += c;
                } else {
                    if (token != "")
                        yield return token;
                    token = "";
                    if (IsSymbol(c))
                        yield return c.ToString();
                    else if (c != ' ')
                        throw new ArithmeticException("正しい式ではありません");
                }
                c = NextChar();
            }
            if (token != "")
                yield return token;
        }

        private static bool IsSymbol(char c) {
            return "+-*/()".Any(x => x == c);
        }

        private int _currentIndex = 0;

        private char NextChar() {
            if (_currentIndex < _expression.Length)
                return _expression[_currentIndex++];
            return (char)0;
        }
    }
}

GetTokenの中がちょっと汚いですが、ご容赦を。

Tokenizerクラスの動きを確認してみる

本来は、単体テストを書くべきなのですが、今回は、動作を確認するテストプログラムを書いて、動作を確認します。
Tokenizerクラスの使い方も、これで分かると思います。

    class Program {
        static void Main(string[] args) {
            TestTokenizer();
        }

        private static void TestTokenizer() {
            while (true) {
                var line = Console.ReadLine();
                var tok = new Tokenizer(line);
                while (tok.MoveNext()) {
                    var token = tok.Current;
                    Console.WriteLine($" '{token}'");
                }
            }
        }
    }

テストプログラムの実行例

実行例です。

((2+4) * (10 + -5)) / 10
 '('
 '('
 '2'
 '+'
 '4'
 ')'
 '*'
 '('
 '10'
 '+'
 '-'
 '5'
 ')'
 ')'
 '/'
 '10'

正しく動いているようです。

次回は、ReversePolishNotationクラスをすこし手直ししたいと思います。

(続く)...

---

この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。