逆ポーランド記法

質問

電卓もどきのアルゴリズムを教えて下さい

指定された数式を解読して、演算結果を求める処理を作成したいのですが・・・・

今考えている手順は
(1) 数式を解析して　逆ポーランド記法の中間言語にして於いておく
(2) 逆ポーランド記法の中間言語を演算して答えを求める
と考えているのですが・・・

<< 例 >>
　演算式　１＋２×３＝　　　　答え　７
　演算式　（１＋２）×３＝　　答え　９

大昔の知識ですのでもっとシンプルな方法が有りましたらアドバイス頂けませんでしょうか？

回答No.2

Tacosan

お手軽に作りたいなら #1 の再帰下降解析がお勧め. 「入力された式をすぐに計算してそれでおしまい」のときには関数から return するときに「自分が担当した部分式の結果」を返せばいいし, 「入力した式を一度記憶して, あとで計算する」という形であっても入力された式を簡単に「構文木」に変換できます. いずれにしても, 「基本パターン」はできあがっているので, パターンに従う限り間違いようがないはずです.
問題点は複雑な構文になると「再帰がとても深くなる」ことで, これがいやだと LR系 (式の解析なら演算子順位解析あたり) を使うことになります. 演算子順位解析は「スタックを使って式を RPN に変換する標準的な方法」とほぼ同じで, バックエンド (あとで計算するところ) に RPN を使うなら扱いやすいかと思います. ただし, スタックの管理を自分でやらないといけないので変なところを間違える可能性はあります.
ちなみに最近のコンパイラでは RPN を使うことはほとんどないはずです. 普通は構文木を作って, その上で最適化とかかけていくんじゃないかな.
念の為指摘しておきますが「RPN」は表現方法, 「再帰下降解析」は解析方法であってこの 2つは相反するものではありません＞#1. 普通はしないけど「再帰下降解析で解析して RPN で記憶する」ことも可能です... ま, しないけど.

お礼

色々とアドバイスありがとうございます。
やはり「逆ポーランド記法」なんて時代遅れのようですね。
日進月歩のこの分野で３０年以上も前の手法をいつまでも使ってる分けないですね・・・・・
昔人間なので「演算子順位解析」、「構文木」、「再帰下降解析」等よく判っていません、若い人にもう少し調べてから最適な方法を検討してみます。
アドバイス有りがとうございました。

回答No.1

Oh-Orange

★再帰下降構文解析
・逆ポーランド記法以外にも『再帰下降構文解析』という方法もあります。
　これは再帰関数を使って数式を計算します。
　例えば
　(1)Factor()…数値、変数、括弧
　(2)MulDiv()…乗算、除算、剰余
　(3)AddSub()…加算、減算
　(4)Compare()…比較
　(5)Express()…数式評価
　このような関数を用意して
　Express()→Compare()→AddSub()→MulDiv()→Factor()→Express()
　と再帰呼び出しを行うだけで加減算よりも乗除算を優先して計算してくれます。
　下に参考になりそうなリンクを貼って置きます。

参考URL：

http://ruffnex.oc.to/kenji/src/dentaku2.c