いよいよ、最大の難関である「数式を解析する機能」を作成していきます。
今回は、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で公開したものを大幅に加筆・修正したものです。