Reverse Polish Notation

この記事について

テンパズルの解を求めるプログラムを書いてみる。テンパズルとは、4つの数字が与えられたときにそれらに関して四則演算を適用し10を作れるか確かめるもの。今回は、タイトル通り、逆ポーランド記法を適用して求めてみる。

逆ポーランド記法とは

計算式を後方に記述していくもの。

ex.)

1 + 2 → 1 2 +

9 / (7 + 8) - 6 → 9 7 8 + / 6 -

演算の単位で数をまとめ、演算子を後ろにつけていく。
この数式はスタックを使って計算できる。

package main

import (
    "fmt"
    "strconv"
    "strings"
)

// v を順番に見ていく
//   数が登場したら stack に push
//   演算子が登場したら
//     stack から pop して取り出した値を a
//     続けて stack から pop して取り出した値を b
//     b, a の計算結果をスタックに push する (b が計算の最初にくる。下記プログラム参照)
// stack に残っている数を返す
func RPolishCalc(v []string) float64 {
    stack := []float64{}
    for _, item := range v {
        i, ok := strconv.Atoi(item)
        if ok == nil {
            stack = append(stack, float64(i))
        } else {
            poppedVal_a := stack[len(stack)-1]
            stack = stack[:len(stack)-1]

            poppedVal_b := stack[len(stack)-1]
            stack = stack[:len(stack)-1]

            switch item {
            case "+":
                stack = append(stack, poppedVal_b+poppedVal_a)
            case "-":
                stack = append(stack, poppedVal_b-poppedVal_a)
            case "*":
                stack = append(stack, poppedVal_b*poppedVal_a)
            case "/":
                stack = append(stack, poppedVal_b/poppedVal_a)
            }
        }
    }
    return stack[0]
}

func Decode(v []string) string {
    result := []string{}
    for _, item := range v {
        _, ok := strconv.Atoi(item)
        if ok == nil {
            result = append(result, item)
        } else {
            poppedVal_a := result[len(result)-1]
            result = result[:len(result)-1]

            poppedVal_b := result[len(result)-1]
            result = result[:len(result)-1]

            switch item {
            case "+":
                result = append(result, fmt.Sprintf("%v + %v", poppedVal_b, poppedVal_a))
            case "-":
                result = append(result, fmt.Sprintf("%v - %v", poppedVal_b, poppedVal_a))
            case "*":
                if 1 < len(poppedVal_a) {
                    poppedVal_a = fmt.Sprintf("( %v )", poppedVal_a)
                }
                result = append(result, fmt.Sprintf("%v * %v", poppedVal_b, poppedVal_a))
            case "/":
                if 1 < len(poppedVal_a) {
                    poppedVal_a = fmt.Sprintf("( %v )", poppedVal_a)
                }
                result = append(result, fmt.Sprintf("%v / %v", poppedVal_b, poppedVal_a))
            }
        }
    }
    return strings.Join(result, " ")
}

func main() {
    v := "6 1 2 + * 8 -"
    fmt.Printf("%v = %#v\n", Decode(strings.Split(v, " ")), RPolishCalc(strings.Split(v, " ")))
}

出力

6 * ( 1 + 2 ) - 8 = 10

逆ポーランド記法に変換すると数字と記号の組み合わせ
X が数字
□ が演算子
並びのパターンは 5通り

• X X X X □ □ □ = ans
• X X X □ X □ □ = ans
• X X X □ □ X □ = ans
• X X □ X X □　 □ = ans
• X X □ X □ X □ = ans

数字の並びは 4!
記号がとりうるのは四則演算記号が3箇所で 4^3
そのため、5 * 4! * 4^3 = 7680 通りが全探索に必要な計算量になる

Todo 与えられた数字4つで全探索して 10 になる式をすべて列挙する