Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
3
Help us understand the problem. What is going on with this article?
@gushwell

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

More than 1 year has passed since last update.

逆ポーランド記法を利用した数式の計算(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で公開したものを加筆・修正したものです。

3
Help us understand the problem. What is going on with this article?
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
gushwell
株式会社ジード / Microsoft MVP for Developer Technologies 2005-2020 / 著書『実戦で役立つ C#プログラミングのイディオム/定石&パターン』『新・標準プログラマーズライブラリ なるほどなっとく C#入門』『C#プログラミング入門―オブジェクト指向のプログラミング手法を基礎から解説』

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
3
Help us understand the problem. What is going on with this article?