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 |
