読者です 読者をやめる 読者になる 読者になる

SQL で逆ポーランド記法の電卓

まだ未完成ですけど、もうほとんど完成してるのでさらしておきますね。
完成しました!
文字列でスタックを実現しています。

WITH
  Input(id, str) AS (
    -- 1 + 3 / -8
    SELECT 1, '1 3 + -8 /'
    -- 2*3*4*5+99
    UNION ALL SELECT 2, '2 3 * 4 * 5 * 99 +'
    -- 4 * (9 - 4) / (2 * 6 - 2) + 8
    UNION ALL SELECT 3, '9 4 - 4 * 2 6 * 2 - / 8 +'
    -- 1 + ((123 * 3 - 69) / 100)
    UNION ALL SELECT 4, '1 123 3 * 69 - 100 / +'
    -- 2.45/8.5*9.27+(5*0.0023)
    UNION ALL SELECT 5, '2.45 8.5 / 9.27 * 5 0.0023 * +'
  )
, Input_(id, str) AS (
    SELECT id, str + ' ' FROM Input
  )
, Calc(id, stack, input_str) AS (
    -- スタックの初期状態
    SELECT
        id
      , CAST(' ' + RTRIM(
          LEFT(str, CHARINDEX(' ', str, 1)) -- 最初の要素をスタックに積む
        ) AS varchar(max))
      , SUBSTRING(str, CHARINDEX(' ', str, 1) + 1, LEN(str))    -- 入力から消費した要素を取り除く
    FROM
        Input_
    UNION ALL
    -- 再帰SQLを使って入力の先頭から一要素毎計算していく
    SELECT
        id
        -- 入力の先頭要素を元にスタックを更新
      , CASE
        WHEN RTRIM(
               LEFT(input_str, CHARINDEX(' ', input_str, 1))
             ) IN ('+', '-', '*', '/')
        -- 演算子ならスタックから2つの要素を取り出して、演算して、また戻す
          THEN ' '
                 + CASE LEFT(
                          stack,
                          LEN(stack)
                              -- topの要素の長さ
                            - LEN(REVERSE(LEFT(REVERSE(stack), CHARINDEX(' ', REVERSE(stack), 1))))
                              -- topの次の要素の長さ
                            - LEN(REVERSE(SUBSTRING(
                                REVERSE(stack),
                                CHARINDEX(' ', REVERSE(stack), 1) + 1,
                                CHARINDEX(
                                  ' ',
                                  REVERSE(stack),
                                  CHARINDEX(' ', REVERSE(stack), 1) + 1
                                ) - CHARINDEX(' ', REVERSE(stack), 1)
                                  - 1
                              )))
                        )
                   WHEN '' THEN ''
                           -- 2つの要素を取り出した後のスタックが空じゃないならスタックの内容と空白を一つスタックに戻す
                           ELSE RTRIM(LTRIM(LEFT(
                                  stack,
                                  LEN(stack)
                                    - LEN(REVERSE(LEFT(REVERSE(stack), CHARINDEX(' ', REVERSE(stack), 1))))
                                    - LEN(REVERSE(SUBSTRING(
                                        REVERSE(stack),
                                        CHARINDEX(' ', REVERSE(stack), 1) + 1,
                                        CHARINDEX(
                                          ' ',
                                          REVERSE(stack),
                                          CHARINDEX(' ', REVERSE(stack), 1) + 1
                                        ) - CHARINDEX(' ', REVERSE(stack), 1)
                                          - 1
                                      )))
                                ))) + ' '
                   END
                 + CAST(
                     -- topから2番目の要素とtopの要素を取り出して演算後、スタックに戻す
                     CASE RTRIM(
                            LEFT(input_str, CHARINDEX(' ', input_str, 1))
                          )
                     WHEN '+' THEN CAST(REVERSE(SUBSTRING(
                                     REVERSE(stack),
                                     CHARINDEX(' ', REVERSE(stack), 1) + 1,
                                     CHARINDEX(
                                       ' ',
                                       REVERSE(stack),
                                       CHARINDEX(' ', REVERSE(stack), 1) + 1
                                     ) - CHARINDEX(' ', REVERSE(stack), 1) - 1
                                   )) AS real)
                                     + CAST(REVERSE(LEFT(REVERSE(stack), CHARINDEX(' ', REVERSE(stack), 1))) AS real)
                     WHEN '-' THEN CAST(REVERSE(SUBSTRING(
                                     REVERSE(stack),
                                     CHARINDEX(' ', REVERSE(stack), 1) + 1,
                                     CHARINDEX(
                                       ' ',
                                       REVERSE(stack),
                                       CHARINDEX(' ', REVERSE(stack), 1) + 1
                                     ) - CHARINDEX(' ', REVERSE(stack), 1) - 1
                                   )) AS real)
                                     - CAST(REVERSE(LEFT(REVERSE(stack), CHARINDEX(' ', REVERSE(stack), 1))) AS real)
                     WHEN '*' THEN CAST(REVERSE(SUBSTRING(
                                     REVERSE(stack),
                                     CHARINDEX(' ', REVERSE(stack), 1) + 1,
                                     CHARINDEX(
                                       ' ',
                                       REVERSE(stack),
                                       CHARINDEX(' ', REVERSE(stack), 1) + 1
                                     ) - CHARINDEX(' ', REVERSE(stack), 1) - 1
                                   )) AS real)
                                     * CAST(REVERSE(LEFT(REVERSE(stack), CHARINDEX(' ', REVERSE(stack), 1))) AS real)
                     WHEN '/' THEN CAST(REVERSE(SUBSTRING(
                                     REVERSE(stack),
                                     CHARINDEX(' ', REVERSE(stack), 1) + 1,
                                     CHARINDEX(
                                       ' ',
                                       REVERSE(stack),
                                       CHARINDEX(' ', REVERSE(stack), 1) + 1
                                     ) - CHARINDEX(' ', REVERSE(stack), 1) - 1
                                   )) AS real)
                                     / CAST(REVERSE(LEFT(REVERSE(stack), CHARINDEX(' ', REVERSE(stack), 1))) AS real)
                     END
                   AS varchar(max))
          ELSE stack
                 + ' '
                 + RTRIM(
                     SUBSTRING(input_str, 1, CHARINDEX(' ', input_str, 1))
                   )
        END
      , SUBSTRING(input_str, CHARINDEX(' ', input_str, 1) + 1, LEN(input_str))
    FROM
        Calc
    WHERE
        input_str <> ''
  )
, Result(id, val) AS (
    SELECT
        id
      , stack
    FROM
        Calc
    WHERE
        input_str = ''
  )
SELECT
    id
  , val
FROM
    Result
ORDER BY
    id

実行結果

id val
1 -0.5
2 219
3 10
4 4
5 2.68344


最後の SELECT を、

SELECT * FROM Calc ORDER BY id, LEN(input_str) DESC

に置き換えると計算の途中結果を確認することができる。

id stack input_str
1 1 3 + -8 /
1 1 3 + -8 /
1 4 -8 /
1 4 -8 /
1 -0.5  
2 2 3 * 4 * 5 * 99 +
2 2 3 * 4 * 5 * 99 +
2 6 4 * 5 * 99 +
2 6 4 * 5 * 99 +
2 24 5 * 99 +
2 24 5 * 99 +
2 120 99 +
2 120 99 +
2 219  
3 9 4 - 4 * 2 6 * 2 - / 8 +
3 9 4 - 4 * 2 6 * 2 - / 8 +
3 5 4 * 2 6 * 2 - / 8 +
3 5 4 * 2 6 * 2 - / 8 +
3 20 2 6 * 2 - / 8 +
3 20 2 6 * 2 - / 8 +
3 20 2 6 * 2 - / 8 +
3 20 12 2 - / 8 +
3 20 12 2 - / 8 +
3 20 10 / 8 +
3 2 8 +
3 2 8 +
3 10  
4 1 123 3 * 69 - 100 / +
4 1 123 3 * 69 - 100 / +
4 1 123 3 * 69 - 100 / +
4 1 369 69 - 100 / +
4 1 369 69 - 100 / +
4 1 300 100 / +
4 1 300 100 / +
4 1 3 +
4 4  
5 2.45 8.5 / 9.27 * 5 0.0023 * +
5 2.45 8.5 / 9.27 * 5 0.0023 * +
5 0.288235 9.27 * 5 0.0023 * +
5 0.288235 9.27 * 5 0.0023 * +
5 2.67194 5 0.0023 * +
5 2.67194 5 0.0023 * +
5 2.67194 5 0.0023 * +
5 2.67194 0.0115 +
5 2.68344  

こんな入力はどうでしょ?

-- 1 + (2 + (3 + (4 + (5 + (6 + (7 + (8 + (9 + 10))))))))
SELECT 1, '1 2 3 4 5 6 7 8 9 10 + + + + + + + + +'

途中結果を確認すると、

id stack input_str
1 1 2 3 4 5 6 7 8 9 10 + + + + + + + + +
1 1 2 3 4 5 6 7 8 9 10 + + + + + + + + +
1 1 2 3 4 5 6 7 8 9 10 + + + + + + + + +
1 1 2 3 4 5 6 7 8 9 10 + + + + + + + + +
1 1 2 3 4 5 6 7 8 9 10 + + + + + + + + +
1 1 2 3 4 5 6 7 8 9 10 + + + + + + + + +
1 1 2 3 4 5 6 7 8 9 10 + + + + + + + + +
1 1 2 3 4 5 6 7 8 9 10 + + + + + + + + +
1 1 2 3 4 5 6 7 8 9 10 + + + + + + + + +
1 1 2 3 4 5 6 7 8 9 10 + + + + + + + + +
1 1 2 3 4 5 6 7 8 19 + + + + + + + +
1 1 2 3 4 5 6 7 27 + + + + + + +
1 1 2 3 4 5 6 34 + + + + + +
1 1 2 3 4 5 40 + + + + +
1 1 2 3 4 45 + + + +
1 1 2 3 49 + + +
1 1 2 52 + +
1 1 54 +
1 55  

楽しい!


追記:
最初の実装以降に身につけたテクニックを使って書き直した。
短く読みやすくなってる・・・はず!

WITH
  Input(id, str) AS (
    -- 1 + 3 / -8
    SELECT 1, '1 3 + -8 /'
    -- 2*3*4*5+99
    UNION ALL SELECT 2, '2 3 * 4 * 5 * 99 +'
    -- 4 * (9 - 4) / (2 * 6 - 2) + 8
    UNION ALL SELECT 3, '9 4 - 4 * 2 6 * 2 - / 8 +'
    -- 1 + ((123 * 3 - 69) / 100)
    UNION ALL SELECT 4, '1 123 3 * 69 - 100 / +'
    -- 2.45/8.5*9.27+(5*0.0023)
    UNION ALL SELECT 5, '2.45 8.5 / 9.27 * 5 0.0023 * +'
  )
, Input_(id, str) AS (
    SELECT id, str + ' ' FROM Input
  )
, Calc(id, stack, top1, top2, input_str) AS (
    -- スタックの初期状態
    SELECT
        id
      , CAST(
          LEFT(str, CHARINDEX(' ', str))    -- 最初の要素をスタックに積む
        AS varchar(max))
      , CAST(LEFT(str, CHARINDEX(' ', str) - 1) AS real)    -- スタックに積んだものと同じもの
      , CAST(NULL AS real)                                  -- 最初は使わないのでなんでもいい
      , SUBSTRING(str, CHARINDEX(' ', str) + 1, LEN(str))   -- 入力から消費した要素を取り除く
    FROM
        Input_
    UNION ALL
    -- 再帰SQLを使って入力の先頭から一要素毎計算していく
    SELECT
        id
        -- 入力の先頭要素を元にスタックを更新
      , CASE
        WHEN LEFT(input_str, 2) IN ('+', '-', '*', '/')
          THEN CAST(
                 -- 演算結果に
                 CASE LEFT(input_str, 1)
                 WHEN '+' THEN top2 + top1
                 WHEN '-' THEN top2 - top1
                 WHEN '*' THEN top2 * top1
                 WHEN '/' THEN top2 / top1
                 END
               AS varchar(max))
                   -- スタックから先頭要素を2つ取り除いたものを連結したものが新しいスタック
                 + CASE LEN(stack)
                          - LEN(CAST(top1 AS varchar(max)))
                          - LEN(CAST(top2 AS varchar(max))) - 1
                   WHEN 0 THEN ' '
                          ELSE SUBSTRING(
                                 stack,
                                 LEN(CAST(top1 AS varchar(max)))
                                   + LEN(CAST(top2 AS varchar(max))) + 2,
                                 len(stack)
                               )
                   END
          ELSE LEFT(input_str, CHARINDEX(' ', input_str)) + stack
        END
        -- 次のtop1は入力が演算子なら演算結果、そうでなければ入力の先頭
      , CAST(CASE LEFT(input_str, CHARINDEX(' ', input_str))
             WHEN '+' THEN top2 + top1
             WHEN '-' THEN top2 - top1
             WHEN '*' THEN top2 * top1
             WHEN '/' THEN top2 / top1
                      ELSE LEFT(input_str, CHARINDEX(' ', input_str))
             END AS real)
        -- 次のtop2は入力が演算子ならスタックの3番目の要素、そうでなければtop1
      , CAST(CASE
             WHEN LEFT(input_str, CHARINDEX(' ', input_str)) IN ('+', '-', '*', '/')
                    AND CHARINDEX(' ', stack, CHARINDEX(' ', stack, CHARINDEX(' ', stack) + 1) + 1) <> 0
               THEN SUBSTRING(
                      stack,
                      LEN(CAST(top1 AS varchar(max))) + LEN(CAST(top2 AS varchar(max))) + 2,
                      CHARINDEX(' ', stack, CHARINDEX(' ', stack, CHARINDEX(' ', stack) + 1) + 1)
                        - CHARINDEX(' ', stack, CHARINDEX(' ', stack) + 1)
                    )
               ELSE top1
             END AS real)
      , SUBSTRING(input_str, CHARINDEX(' ', input_str) + 1, LEN(input_str))
    FROM
        Calc
    WHERE
        input_str <> ''
  )
, Result(id, val) AS (
    SELECT
        id
      , stack
    FROM
        Calc
    WHERE
        input_str = ''
  )
SELECT
    id
  , val
FROM
    Result
ORDER BY
    id

途中結果も載せときますね。

id stack top1 top2 input_str
1 1 1 NULL 3 + -8 /
1 3 1 3 1 + -8 /
1 4 4 3 -8 /
1 -8 4 -8 4 /
1 -0.5 -0.5 -8  
2 2 2 NULL 3 * 4 * 5 * 99 +
2 3 2 3 2 * 4 * 5 * 99 +
2 6 6 3 4 * 5 * 99 +
2 4 6 4 6 * 5 * 99 +
2 24 24 4 5 * 99 +
2 5 24 5 24 * 99 +
2 120 120 5 99 +
2 99 120 99 120 +
2 219 219 99  
3 9 9 NULL 4 - 4 * 2 6 * 2 - / 8 +
3 4 9 4 9 - 4 * 2 6 * 2 - / 8 +
3 5 5 4 4 * 2 6 * 2 - / 8 +
3 4 5 4 5 * 2 6 * 2 - / 8 +
3 20 20 4 2 6 * 2 - / 8 +
3 2 20 2 20 6 * 2 - / 8 +
3 6 2 20 6 2 * 2 - / 8 +
3 12 20 12 20 2 - / 8 +
3 2 12 20 2 12 - / 8 +
3 10 20 10 20 / 8 +
3 2 2 10 8 +
3 8 2 8 2 +
3 10 10 8  
4 1 1 NULL 123 3 * 69 - 100 / +
4 123 1 123 1 3 * 69 - 100 / +
4 3 123 1 3 123 * 69 - 100 / +
4 369 1 369 1 69 - 100 / +
4 69 369 1 69 369 - 100 / +
4 300 1 300 1 100 / +
4 100 300 1 100 300 / +
4 3 1 3 1 +
4 4 4 3  
5 2.45 2.45 NULL 8.5 / 9.27 * 5 0.0023 * +
5 8.5 2.45 8.5 2.45 / 9.27 * 5 0.0023 * +
5 0.288235 0.2882353 8.5 9.27 * 5 0.0023 * +
5 9.27 0.288235 9.27 0.2882353 * 5 0.0023 * +
5 2.67194 2.671942 9.27 5 0.0023 * +
5 5 2.67194 5 2.671942 0.0023 * +
5 0.0023 5 2.67194 0.0023 5 * +
5 0.0115 2.67194 0.0115 2.67194 +
5 2.68344 2.68344 0.0115