すべての RPN 式は、すべての演算子が左側に表示され、すべてのオペランドが右側に表示されるように表現できますか?

Question

私はそれができないと自分自身に納得させました。

たとえば次のとおりです。

4 4 + 4 /

スタック：4スタック：4 4 4 + 4 = 8スタック：8スタック：8 4 8/4 = 2スタック：2

オペランドがすべて最初に来るように、同じ演算子とオペランドで上記の式を書くことができる2つの方法があります。「4 4 4 + /」および「4 4 4 4 / +」。どちらも2に評価されません。

"4 4 4 + /"スタック：4スタック：4 4スタック：4 4 4 4 + 4 = 8スタック：4 8 4/8 = 0.5スタック：0.5

「4 4 4 / +」スタック：4スタック：4 4スタック：4 4 4 4/4 = 1スタック：4 1 4 + 1 = 5スタック：5

スタック上のアイテムを交換できる場合は可能ですが、そうでない場合は「いいえ」です。

考えは？

Answer 1

次の代数式を考えてみましょう。

(a + b) * (c + d)

RPN への明白な翻訳は次のようになります。

a b + c d + *

スワップ操作が利用可能な場合でも、右側のすべての演算子を収集する方法はないと思います。

a b c d +
a b S

ここで、S は c と d の合計です。この時点では、単一のスワップ操作を使用して、a と b の両方を + 操作の所定の位置に配置することはできませんでした。代わりに、a と b を正しい位置に取得するには、より高度なスタック操作 (ロールなど) が必要になります。すべての場合にロール操作で十分かどうかもわかりません。

Answer 2

実際、あなたは答えを与えただけでなく、タイトルに暗示された仮定を反証するのに十分な反例を調べることによって、決定的な証明も示しました。

Answer 3

これが非常に古いスレッドであることは承知していますが、今日見つけたばかりなので、元の質問に対する答えは「YES」であると信じていると言いたいと思います。通常の算術演算に加えて、表現に 3 つの追加の「ナビゲーション」演算子を含めることができる場合、すべての RPN 式は、すべての演算子が左側に表示され、すべてのオペランドが右側に表示されるように表現できると確信しています。

あらゆる算術式は、リーフ ノードに変数と定数、ツリーのフォークにバイナリ算術演算、分岐に沿った否定、逆数、平方根などの単項演算を備えたバイナリ ツリーとして表すことができます。私が提案する 3 つの追加操作は、二分木の左枝の構築、右枝の構築、または葉ノードへの到達を表します。ここで、ツリー内のそれぞれの葉の位置に従って、入力文字列の左側にすべてのオペランドを配置すると、メモリ内で適切なバイナリ ツリーを再構築し、オペランドと数学演算を正しいポイントに追加します。最後に、深さ優先のツリー トラバーサル アルゴリズムが適用されて結果が計算されます。

これが実際に応用できるかどうかはわかりません。おそらく、式をエンコードおよびデコードする方法としては非効率すぎます。しかし、学術的な演習としては、有効であると確信しています。

Answer 4

これに対する答えを伝えるためには、できないものを示すだけで十分です。

スタックの内容を並べ替えることができない場合、式 (2+4)*(7+8) を並べ替えることはできません。

2 4 + 7 8 + *

これをどのように並べ替えても、先に進む前に合計する必要があるものが出てきます。

少なくとも私はそう信じています。