C#:逆ポーランド記法を利用した数式の計算(5) Interpreterパターンで数式を解析する



いよいよ、最大の難関である「数式を解析する機能」を作成していきます。
今回は、BNF（バッカス・ナウア記法：Backus-Naur form）を定義し、そのBNFの定義に沿ってGoFのインタプリタ・パターン([Interpreter pattern](https://ja.wikipedia.org/wiki/Interpreter_パターン))を使って機械的にコーディングすることで、数式を解析しようと思います。


## 記事一覧

[逆ポーランド記法を利用した数式の計算(1) 逆ポーランド記法の計算](https://qiita.com/gushwell/items/a40f4119a35a1e6d7622)
[逆ポーランド記法を利用した数式の計算(2) 数式をトークンに分割する](https://qiita.com/gushwell/items/58572bcff11315d77738)
[逆ポーランド記法を利用した数式の計算(3) ReversePolishNotationクラスを改良する](https://qiita.com/gushwell/items/1f58e270a5430bcc5dba)
[逆ポーランド記法を利用した数式の計算(4) Contextクラスを定義する](https://qiita.com/gushwell/items/03ed3063e9eacef84695)
[逆ポーランド記法を利用した数式の計算(5) Interpreterパターンで数式を解析する](https://qiita.com/gushwell/items/f598ee4c3e3f1a22604b) ← 当記事
[逆ポーランド記法を利用した数式の計算(6) 最後の仕上げ](https://qiita.com/gushwell/items/b2649335392fd366a691)


## 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クラスの実装です。

```csharp
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クラス

```csharp
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オブジェクト](https://qiita.com/gushwell/items/03ed3063e9eacef84695)を受け取ります。最初に、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が終わった後ですね。

で、そのコードを追加したのが、以下のコードとなります。

```csharp
    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をどんな風に使うかですが、以下のようなコードになります。

```csharp
var context = new Context("2 * (3 + 9)");
var node = new ExpressionNode();
node.Parse(context);
```


Parseメソッドの呼び出しから戻ってくると、context.Notationプロパティには、逆ポーランド記法オブジェクトであるReversePolishNotationオブジェクトが設定されています。


### TermNode,DivTermNode,FactorNodeクラス

同じような要領で、TermNode, DivTermNode, FactorNodeの３つのクラスを実装します。

```csharp
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>`の２つを賄ってしまいます。


```csharp
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オブジェクトに追加しています。

<br>
<br>

---

これで、RpnCalculatorクラス,　Tokenizerクラス, ReversePolishNotationクラス, Contextクラス, Nodeクラスとその具象クラスの定義が終わりました。

数式（加減乗除の式）を入力して計算するためのすべてのピースが整ったことになります。

いよいよ、次回は、Expressionクラスと、それを利用するMainメソッドを実装します。


([続く](https://qiita.com/gushwell/items/b2649335392fd366a691))...

---

この記事は、Gushwell's C# Programming Pageで公開したものを大幅に加筆・修正したものです。