[Swift] 数式を評価する lexer/parser を作る (1.0 + 1.0 * 1.0 を計算する) (5)

Swift

前回、3項以上の数式を lexer で処理できるようにしたので 今回は、優先度の異なる演算子を扱えるようにします。

環境&対象

以下の環境で動作確認を行なっています。

  • macOS Monterery beta 5
  • Xcode 13 beta5

前回までにやったこと

数式として、当初は、"1 + 1" という 項+演算子+項 という形から始まり、"1.0 + 2.0 + 3.0" という 複数項(3項以上)の項を持つ数式を、その Token を理解する lexer まで作りました。

Swift[Swift] 数式を評価する lexer/parser を作る (1.0 + 1.0 + 1.0 を計算する) (4)

ここまでの実装では 演算子の順番を考慮していないため、1 + 2 * 3 は、 (1 + 2) * 3 となり、9 となってしまいます。

*、/ を、+、- よりも優先して計算する仕組みを入れていきます。

2項+演算子な数式

2項+演算子な数式を表す AST(Abstract Syntax Tree)

+やーは、2項演算子であることから、2分木をつかった AST を使っています。

(項+演算子+項)を AST で表す時は、シンプルでした。AST は、以下のようなツリーです。

flowchart TD 演算子 --> 左項 演算子 --> 右項

2項+演算子な数式を表す AST をつかった 数式計算

今回の実装では、AST を上から評価していく実装をしています。

AST の各ノードには、演算子か、数値が記録されています。

AST の最上位ノードは、演算子。最下位ノード(複数あります)は、数値を持っています。

1+2を表すと 最上位ノードは + となり、+ の左側子ノードに 1、右側子ノードには 2 が記録されます。

flowchart TD + --> 1 + --> 2

数式の値を計算するときには、最上位のノードに着目し、左側子ノードの値を右側子ノードの値を、演算子を使って処理します。

1+2 の AST に対しては、以下のように計算することになります。

AST を使った評価値計算(1+1)
  1. + のノードに着目します。
  2. 左側の子ノードを確認すると 値 1 を持っています。
  3. 右側の子ノードを確認すると 値 2 を持っています。
  4. ノードの演算子は、+ だったので、1+2 を計算して、3 を ノードの値とします。
  5. 最上位ノードなので、全体の値(式の値)は、3 となり 計算は終了です。

複数項(3項以上)対応

複数項(3項以上)を表す AST

3項以上の項がある数式では、以下のように 木の高さを増やして 表現します。

1 + 2 - 3 は、以下のような AST になります。

1+2-3

複数項(3項以上)を表す ASTを使った評価値計算

AST を使った評価値計算(1+2-3)
  1. 最上位の - のノードに着目します
  2. 左側の子ノードを確認すると + のノードだとわかります
  3. +ノードに着目します
  4. (+ノードの)左側子ノードは、1 という値を持っています。
  5. (+ノードの)右側子ノードは、2 という値を持っています。
  6. 1 + 2 = 3 という値が +ノードの値となります。
  7. -ノードの着目に戻ります。左側子ノードの値がわかったので、右側子ノードを確認すると 3 を持っています。
  8. ーノードの 左側子ノードの値 3 と 右側子ノードの値 3 がわかったので、演算子 ー を使用して、 3 - 3 = 0 と計算します
  9. ーノードは、最上位ノードなので ーノードの値が式の値となります

優先度のある演算子への対応

演算子が+と-だけであれば良いのですが、*と/に対応しようとするとその順番を考慮することが必要となります。

1 + 2 * 3 は (1 + 2) * 3 = 9 ではなく、1 + (2 * 3) = 7 という結果が期待されます。

先の AST をつかった計算方法を考慮すると 1 + 2 * 3 は、以下のような AST になる必要があります。

flowchart TD + --> 1 + --> * * --> 2 * --> 3

計算してみましょう

AST を使った評価値計算(1+2*3)
  1. 最上位の + のノードに着目します
  2. 左側の子ノードを確認すると 1 という値を持っています
  3. 右側の子ノードを確認すると * のノードだとわかります
  4. * のノードに着目します
  5. (*ノードの)左側子ノードは、2 という値を持っています。
  6. (*ノードの)右側子ノードは、3 という値を持っています。
  7. 2 * 3 = 6 という値が *ノードの値となります。
  8. +ノードの着目に戻ります。右側子ノードの値がわかりました(つまり、左側・右側の両方わかりました)
  9. +ノードの左側子ノードの値 1 と 右側子ノードの値 6 がわかったので、演算子 + を使用して、1 + 6 = 7 と計算します
  10. +ノードは、最上位ノードなので、+ノードの値が式の値となります

実装

作りたい AST が見えてきたので、テストから書いていきます。

parser テスト

1 + 2 * 3 をテストケースとしています。生成された AST の構成詳細を確認しています。


    func test_parse_5TokensPlusTimes_successToParse() throws {
        let tokens = [Token.Numeric(1.0), Token.Operator("+"), Token.Numeric(2.0), Token.Operator("*"), Token.Numeric(3.0)]

        let sut = MathExpressionParser()
        let expression = try XCTUnwrap(sut.parse(tokens))
        
        try XCTAssertTokenEqual(expression.token, .Operator("+"))
        let left = try XCTUnwrap(expression.left)
        try XCTAssertTokenEqual(left.token, .Numeric(1.0))
        let right = try XCTUnwrap(expression.right)
        try XCTAssertTokenEqual(right.token, .Operator("*"))
        let rightLeft = try XCTUnwrap(right.left)
        try XCTAssertTokenEqual(rightLeft.token, .Numeric(2.0))
        let rightRight = try XCTUnwrap(right.right)
        try XCTAssertTokenEqual(rightRight.token, .Numeric(3.0))
                                
        let result = try XCTUnwrap(expression.calc())
        XCTAssertEqual(result, 7.0, accuracy: 0.001) // 1.0 + 2.0 * 3.0 = 7.0
    }

parser 実装

2分木に対して 新しい演算子と新しい項を追加する関数を 以下の2種類作りました。

新しい演算子を2分木の最上位ノードにする(addTermWithLowPriorityOperator)

これまでの2分木を左側子ノード、新しい項を右側子ノードとした2分木を返す関数

flowchart TD + --> 1 + --> 2
- 3 を追加する
1+2-3

新しい演算子を2分木の右側子ノードとする(addTermWithHighPriorityOperator)

これまでの2分木の右側子ノードは、新しい演算子の左側子ノードとし、新しい項は、新しい演算子の右側子ノードとした2分木を返す関数

flowchart TD + --> 1 + --> 2
* 3 を追加する
flowchart TD + --> 1 + --> * * --> 2 * --> 3

上記のような関数を使用することで、parse 関数は以下のようになります。


class MathExpressionParser {
    typealias Error = MathExpressionParserError

    func parse(_ tokens:[Token]) throws -> MathExpression {
        guard tokens.count > 0 else { throw Error.InvalidExpression  }
        var index:Int = 0

        // get 1st token, confirm it is numeric
        let firstToken = tokens[index]
        guard firstToken.isNumeric else { throw Error.InvalidExpression }
        index += 1

        var mathExpression = MathExpression(firstToken)
        while (index < tokens.count) {
            guard (tokens.count - index) >= 2 else { throw Error.InvalidExpression }
            
            // should see operator first, then numeric
            let opeToken = tokens[index]
            index += 1
            let rightToken = tokens[index]
            index += 1
            var nextExpression: MathExpression
            if mathExpression.token.isNumeric {
                nextExpression = try mathExpression.addTermWithLowPriorityOperator(ope: opeToken, right: rightToken)
            } else if mathExpression.topTokenPriority < opeToken.priority { // new ope is "*" or "/"
                nextExpression = try mathExpression.addTermWithHighPriorityOperator(ope: opeToken, right: rightToken)
            } else {
                nextExpression = try mathExpression.addTermWithLowPriorityOperator(ope: opeToken, right: rightToken)
            }
            mathExpression = nextExpression
        }
        return mathExpression
    }
}

上記コードで作成したテストコードをパスすることが確認できます。

パースだけでなく、値計算(Calc) のテストも行っています

できたこと:数式を評価する lexer/parser を作る(5)

数式を評価する lexer/parser を作る(5)
  • 優先度に差異のある演算子を扱うためには、優先度に合わせた AST を作成して計算する

説明は以上です。
不明な点やおかしな点ありましたら、こちらまで。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です