以前に簡単な四則計算を再帰下降構文解析でしてみた1ものの、もっと単純で面白い感じのアルゴリズムがあった気がしていた。調べたら「操車場アルゴリズム」(shunting-yard algorithm)と思い出したので、これをRubyで実装してみる。 概要 詳しい説明や図解はWikipedia参照。 中置記法で書かれたよく見る数式を、後置記法(逆ポーランド記法)に変換できる。記号列を入力から出力へ送る際にスタックを用いて並べ替える様子を、列車を並べ替える様子で説明したため、操車場アルゴリズムと呼ばれる。 コード 以前と同様に「1桁の整数・加算・乗算・括弧のみの数式を解釈して計算結果を返す」パーサを作ってみる。各文字がそのままトークンになるので、字句解析を省いて簡略化する2。 エラー処理は不完全なので、前提に合わない数式(例えば2桁の数字)を入力してもエラーにならず変な結果を返すことがある。 cl
![操車場アルゴリズムで四則計算の数式をパース - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/80481ff1d04bc10fc9f9c079cfc52b8e13c4ab96/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-412672c5f0600ab9a64263b751f1bc81.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk3MiZoPTM3OCZ0eHQ9JUU2JTkzJThEJUU4JUJCJThBJUU1JUEwJUI0JUUzJTgyJUEyJUUzJTgzJUFCJUUzJTgyJUI0JUUzJTgzJUFBJUUzJTgyJUJBJUUzJTgzJUEwJUUzJTgxJUE3JUU1JTlCJTlCJUU1JTg5JTg3JUU4JUE4JTg4JUU3JUFFJTk3JUUzJTgxJUFFJUU2JTk1JUIwJUU1JUJDJThGJUUzJTgyJTkyJUUzJTgzJTkxJUUzJTgzJUJDJUUzJTgyJUI5JnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9NTYmdHh0LWFsaWduPWxlZnQlMkN0b3Amcz03MDEwY2U0MDFmYTZmYWRkNWUxOWMyMTcwMDAwYWExMA%26mark-x%3D142%26mark-y%3D57%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZoPTc2Jnc9NzcwJnR4dD0lNDBITU1OUlNUJnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9MzYmdHh0LWFsaWduPWxlZnQlMkN0b3Amcz1jOGM5MzcyMDRlYzEwM2MzNjBkY2E1MDRiOWIyMGMyYQ%26blend-x%3D142%26blend-y%3D486%26blend-mode%3Dnormal%26s%3Dd95f6e8ccf7ee37b25eb43c93b488a33)