いよいよ、最大の難関である「数式を解析する機能」を作成していきます。
今回は、BNF（バッカス・ナウア記法：Backus-Naur form）を定義し、そのBNFの定義に沿ってGoFのインタプリタ・パターン(Interpreter pattern)を使って機械的にコーディングすることで、数式を解析しようと思います。
記事一覧
逆ポーランド記法を利用した数式の計算(1) 逆ポーランド記法の計算
逆ポーランド記法を利用した数式の計算(2) 数式をトークンに分割する
逆ポーランド記法を利用した数式の計算(3) ReversePolishNotationクラスを改良する
逆ポーランド記法を利用した数式の計算(4) Contextクラスを定義する
逆ポーランド記法を利用した数式の計算(5) Interpreterパターンで数式を解析する ← 当記事
逆ポーランド記法を利用した数式の計算(6) 最後の仕上げ
BNFを定義する
まずは、加減乗除を扱える数式を BNF（バッカス・ナウア記法）で定義します。
BNFは、こんな感じ。
<exp> ::= <term> {("+"|"-") <term>}
<term> ::= <divterm> {"*" <divterm>}
<divterm> ::= <factor> { "/" <factor>}
<factor> ::= <snumber> | "(" <exp> ")"
<snumber> ::= ["+"|"-"] {<digit>}[.{<digit>}]
<digit> ::= "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
BNFの正式な記法は良くわかってないですが、まああたらずとも遠からずかな。/ と * の優先順位が明確になるように BNFを定義しています。
{} は繰り返し、| は選択、[] はオプション といったことがわかれば、読み解けるのではと思います。BNFの詳細は、どこかのサイトを見てください。
数式を表す BNFとしては "-(2 + 4) / 2" のように、先頭に符号があり、その直後に()が続くような数式に対応していませんが、そこはご容赦を。
たぶん、このBNFをちょっと変更すれば対応できると思いますので、興味のある方は、チャレンジしてみてください。
数式解析方法の方針
最初に触れたように、上記のBNFをInterpreterパターンを使って、機械的にコーディングすることで、数式を解析しようと思います。
逆ポーランド記法への変換は、この解析処理の中で一緒にやってしまおうと思います。
Node抽象クラス
前述のBNFをInterpreterパターンで実装する訳ですが、<> で囲まれた<exp> <factor> などを、Interpreterパターンで言うところのノードクラスとして定義します。
まずは、各クラスの継承元となるNodeクラスの実装です。
using System;
using System.Collections.Generic;
using System.Linq;
namespace Rpn.App {
public abstract class Node {
public abstract void Parse(Context context);
public static bool IsOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
}
public static bool IsParenthesis(char c) {
return (c == '(' || c == ')');
}
public static bool IsSign(char c) {
return (c == '-' || c == '+');
}
public static int GetSign(string s) {
if (s[0] == '-')
return -1;
return 1;
}
}
}
Parseメソッドが、継承したクラスで実装するメソッドです。それ以外のメソッドは、式を解析する際に利用するユーティリティメソッドとなっています。
Nodeの具象クラス
最初に、<exp>に対応した、ExpressionNodeクラスを定義します。先ほどのNodeクラスを継承します。
Parseメソッドは、BNFの右辺部分をそのままコード化することになります。
ExpressionNodeクラス
public class ExpressionNode : Node {
public override void Parse(Context context) {
Node node1 = new TermNode();
node1.Parse(context);
var token = context.CurrentToken;
while (token == "+" || token == "-") {
context.MoveNext();
Node node2 = new TermNode();
node2.Parse(context);
token = context.CurrentToken;
}
}
}
Parseメソッドは、前回示したContextオブジェクトを受け取ります。最初に、ExpressionNodeのParseメソッドが呼ばれたときには、Contextには計算する数式が設定されています。
上のコードを見ていただければ、BNFの定義と対応しているのがわかると思います。
これで解析はできるのですが、問題は、逆ポーランド記法を表すReversePolishNotationオブジェクトの組み立てです。
例えば、3 + 5 という式の場合は、3 5 + という順番にしないといけません。
Parseメソッドの中で、この3 + 5という式がどう対応しているかを見てみると、最初のTermNodeのParse()で、3が処理され、whileのところで、+ が処理され、while文の中のTermNodeのParse()で5が処理されることになります。
この時、3と5をReversePolishNotationオブジェクトにセットするのは、それぞれのTermNode.Parse()の中で行うことにし、このExpressionNodeのParse()では、+ だけをReversePolishNotationに追加することとします。
どこでやるか、それは、2つめのTermNodeのParseが終わった後ですね。
で、そのコードを追加したのが、以下のコードとなります。
public override void Parse(Context context) {
Node node1 = new TermNode();
node1.Parse(context);
var token = context.CurrentToken;
while (token == "+" || token == "-") {
context.MoveNext();
Node node2 = new TermNode();
node2.Parse(context);
context.Notation.Add(token); // これを追加
token = context.CurrentToken;
}
}
ExpressionNodeをどんな風に使うかですが、以下のようなコードになります。
var context = new Context("2 * (3 + 9)");
var node = new ExpressionNode();
node.Parse(context);
Parseメソッドの呼び出しから戻ってくると、context.Notationプロパティには、逆ポーランド記法オブジェクトであるReversePolishNotationオブジェクトが設定されています。
TermNode,DivTermNode,FactorNodeクラス
同じような要領で、TermNode, DivTermNode, FactorNodeの３つのクラスを実装します。
public class TermNode : Node {
public override void Parse(Context context) {
Node node1 = new DivTermNode();
node1.Parse(context);
string token = context.CurrentToken;
while (token == "*") {
context.MoveNext();
Node node2 = new DivTermNode();
node2.Parse(context);
context.Notation.Add(token);
token = context.CurrentToken;
}
}
}
public class DivTermNode : Node {
public override void Parse(Context context) {
Node node1 = new FactorNode();
node1.Parse(context);
string token = context.CurrentToken;
while (token == "/") {
context.MoveNext();
Node node2 = new FactorNode();
node2.Parse(context);
context.Notation.Add(token);
token = context.CurrentToken;
}
}
}
public class FactorNode : Node {
public override void Parse(Context context) {
var token = context.CurrentToken;
if (token == "(") {
context.MoveNext();
Node node = new ExpressionNode();
node.Parse(context);
context.MoveNext();
} else {
Node node = new SignedNumberNode();
node.Parse(context);
}
}
}
FactorNodeを他のクラスと比べてください。context.Notation.Add(token);がありません。これは、BNFの <factor>の定義において、演算子が現れていないからです。ここでもBNFの定義と対応づいているのがわかります。
SignedNumberNodeクラス
BNFの定義で、まだ実装していないのは、<snumber>と<digit> ですが、これをそのまま実装するのは、あまりにも馬鹿正直なので、C#のTryParseメソッドなどの力を借りて、SignedNumberNodeというクラスで<snumber>と<digit>の２つを賄ってしまいます。
public class SignedNumberNode : Node {
public override void Parse(Context context) {
var token = context.CurrentToken;
int sign = 1;
IEnumerable<char> nstr = token;
if (IsSign(token[0])) {
sign = GetSign(token);
context.MoveNext();
token += context.CurrentToken;
}
if (decimal.TryParse(token, out var num)) {
context.Notation.Add(token);
} else {
throw new ArithmeticException("正しい式ではありません");
}
context.MoveNext();
}
}
decimal.TryParse()で得た数値をcontext.Notation.Add(token);で、ReversePolishNotationオブジェクトに追加しています。
なお、数値をReversePolishNotationオブジェクトに追加しているのは、このクラスだけとなっています。他のクラスでは、演算記号だけをReversePolishNotationオブジェクトに追加しています。
これで、RpnCalculatorクラス, Tokenizerクラス, ReversePolishNotationクラス, Contextクラス, Nodeクラスとその具象クラスの定義が終わりました。
数式（加減乗除の式）を入力して計算するためのすべてのピースが整ったことになります。
いよいよ、次回は、Expressionクラスと、それを利用するMainメソッドを実装します。
(続く)...
この記事は、Gushwell's C# Programming Pageで公開したものを大幅に加筆・修正したものです。