Help us understand the problem. What is going on with this article?

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

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

第1回目の逆ポーランド記法の計算では、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で公開したものを加筆・修正したものです。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした