54829


中間記法「3 + 4」は逆ポーランド記法だと「3 4 +」のように書けます。  
では、被演算子が3個以上、たとえば中間記法「3 + 4 + 5」は逆ポーランド記法ではどのように書けばよいのでしょうか？  
「3 4 + 5 + 」と書けばよさそうですが、「3 4 5 +」のように書くことはできないのでしょうか？  
（乗算でも同様にできそうですが引き算だとどうなるのかちょっとよくわからないですね）


CC BY-SA 4.0
2019-05-08T12:06:39.667
54826
2019-05-08T15:30:35.243
32428
question
アルゴリズム データ構造 スタック
逆ポーランド記法で被演算子が3個以上の演算はありうるのか？


**_中間記法「3 + 4 + 5」は逆ポーランド記法ではどのように書けばよいのでしょうか？_**

ご質問中にあるように、`3 4 + 5 +`でも構いませんし、`3 4 5 + +`でも構いません。

**_「3 4 5 +」のように書くことはできないのでしょうか？_**

`+`がどのような演算として定義されているかによるわけですが、他の箇所に合わせて2数の加算と考えると、`3 4 5 +`だと、最後の`4
5`だけが加算されて、`3 9`と書いたのと同じ状態になってしまいます。

もし「スタック上から3つの数を取り出して全部を足し合わせる演算」、なんてものが定義できれば、`3 4 5 add3`なんて書き方もありになります。

* * *

逆ポーランド記法を基礎に置いた言語(と言うよりスタック操作を基礎、と言った方が良いかもしれませんが)Forthだとこんな感じ。(`\`以降は行コメントです。)

[code]

    : add3 + + ;   \ スタックを3個読み取る演算子(ワード)`add3`の定義
    3 4 5 add3     \ `add3`を演算として使う
    
[/code]

(結果)=>12


CC BY-SA 4.0
2019-05-08T12:43:16.797
54829
2019-05-08T12:56:08.033
2019-05-08T12:56:08.033
13972
13972
54826
answer


まずはじめに、一般的な言語で大抵の場合は四則演算子`+`, `-`, `*`, `÷`は二項演算子です。  
これは、二つの数字を引数に取り、結果を返すというのが素直な理解だと思います。  
なので、`3 4 5 +`の様に書けない理由は逆ポーランド記法が原因では無く、演算子が必要とする引数の個数の問題です。

なので、パーサーを自作するなどして、（式として見た場合）自分より左に異なる演算子が見つかるか、式の開始までの数字をすべて足す演算子を例えば`sum`などと定義することは可能かと思います。

ですが、偶然にも逆ポーランド記法は非常に日本語と相性がいい事を理解しておられますでしょうか？  
たとえば、  
`1 2 + 3 4 + ×`  
という`RPN`式は、素直に  
「`1`に`2`を足した(`+`)ものと`3`に`4`を足した(`+`)ものを掛け合わせ(`×`)る」  
と、式がそのまま日本語で読めます。  
逆も同様で、日本語で頭の中で考えた計算方法を`RPN`式にするのも中間記法より、行いたい計算を式に表記しやすいのです。

これを曲げてまで省略記法を作るメリットはあまりないように僕は感じています。


CC BY-SA 4.0
2019-05-08T13:15:43.317
54831
2019-05-08T13:15:43.317
14745
54826
answer


もし質問の意図が、`+`演算子が、不定個数の被演算子を取れるようにできるか、ということだったら無理です。スタックから`+`演算子を取り出した時にどんな処理をすればいいのか、決定できないからです。

たとえば、乗算も加算も不定個数の被演算子を取れるようにしてみたとします。つまり`2 * 3 * 4`なら`2 3 4 *`、`5 + 3`なら`5 3
+`と書けるようにします。

ここで普通の式`2 + 3 + 4 * 5`を、逆ボーランドで記述してみます。とりあえず乗算は後回しにして

[code]

    2 3 (4 * 5) +
    
[/code]

さらに乗算も変換すると最終的に

[code]

    2 3 4 5 * +
    
[/code]

になります。

では次は`2 + 3 * 4 * 5`を変換してみます。上と同じ手順で

[code]

    2 (3 * 4 * 5) +
    2 3 4 5 * +
    
[/code]

この通り、`2 + 3 + 4 * 5`と`2 + 3 * 4 *
5`が同じ記述になってしまいます。これは`*`や`+`を扱うときに、何個、被演算子を取ってくればいいのか、分からないからです。

実際上は、引数の終わりを示すマーカーを使えばできますが、そうすると`3 + 4 + 5`も`| 3 4 5 +` (`|`は引数の終わりのマーカー)
と書かなければならなくなり、結局`3 4 5 +`と書けないことには変わりがありません。それどころか、`3 + 4`ですら`| 3 4
+`と書かなければならなくなります。

* * *

もし、いつでも必ず3つの被演算子を取る演算子を作りたいのであれば、OOPerさんの回答の通り、何の問題もなく作れます。


CC BY-SA 4.0
2019-05-08T15:30:35.243
54832
2019-05-08T15:30:35.243
3605
54826
answer