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