Edited at

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で公開したものを加筆・修正したものです。