1

私は彼らができないと確信しました。

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

4 4 + 4 /

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

オペランドがすべて最初になるように、同じ演算子とオペランドを使用して上記の式を記述する方法は 2 つあります。"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

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

考え？

4

4 に答える 4

2

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

(a + b) * (c + d)

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

a b + c d + *

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

a b c d +
a b S

where S is the sum of c and d. At this point, you couldn't use a single swap operation to get both a and b in place for a + operation. Instead, you would need a more sophisticated stack operation (such as roll) to get a and b in the right spot. I don't know whether a roll operation would be sufficient for all cases, either.

于 2008-09-02T09:08:08.793 に答える
1

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

于 2008-09-02T09:06:25.897 に答える
1

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

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

これが実用的なアプリケーションを持っているかどうかはわかりません。式をエンコードおよびデコードする方法としては、おそらく非効率的です。しかし、アカデミックな演習として、私はそれが実行可能であると確信しています.

于 2012-12-13T04:27:28.473 に答える
0

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

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

2 4 + 7 8 + *

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

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

于 2008-09-02T09:05:53.183 に答える