簡単に言えば、私の講師はくだらないもので、オーバーヘッド プロジェクターを介してスタックをプレフィックスするためのインフィックスを見せていましたが、彼の大きな影がすべてをブロックしていたので、重要なことを見逃していました
彼はプッシュとポップ、プッシュ = 0 ポップ = x について言及していました。
彼は例を挙げましたが、彼がどのように答えを導き出すのかまったくわかりません。
2*3/(2-1)+5*(4-1)
ステップ 1 逆: )1-4(*5+)1-2(/3*2わかりました
その後、彼は x と o の操作を書き続け、私は完全に道に迷いました
答え14-5*12-32*/+てから、もう一度逆にして取得します+/*23-21*5-41
誰かが私にプッシュ ポップを説明してくれたら、私はとても素晴らしいと思います。私はオンラインで見ましたが、見つけた多くのものはこれよりも一歩進んでいるように見えるので、最初にここで理解する必要があります。
これがスタックとその仕組みを視覚化するのに役立つことを願っています。
空のスタック:
| |
| |
| |
-------
を押すAと、次のようになります。
| |
| |
| A |
-------
を押すBと、次のようになります。
| |
| B |
| A |
-------
ポッピング後、次のようになります。
| |
| |
| A |
-------
を押すCと、次のようになります。
| |
| C |
| A |
-------
ポッピング後、次のようになります。
| |
| |
| A |
-------
ポッピング後、次のようになります。
| |
| |
| |
-------
Oren Aによって投稿されたライフル クリップの例えはかなり良いですが、別の例を試して、教官が伝えようとしていたことを予測しようとします.
スタックは、その名前が示すように、次のような「もの」の配置です。
(文字通り、机の上に積み上げられた本と考えてください。上からしか取ることができません)
スタックに何かをプッシュするということは、「それを一番上に置く」ことを意味します。スタックから何かをポップするということは、スタックから「一番上の「もの」を取り出す」ことを意味します。
簡単な使い方は、単語の順序を逆にすることです。「ポップコーン」という単語を逆にしたいとします。各文字を左から右 (7 文字すべて) にプッシュしてから、7 文字をポップすると逆順になります。こういう表情でやっていたようです。
プッシュ(p) プッシュ(o) プッシュ(p) プッシュ(c) プッシュ(o) プッシュ(r) プッシュ(n)
単語全体をプッシュした後、スタックは次のようになります。
| n | <- top
| r |
| o |
| c |
| p |
| o |
| p | <- bottom (first "thing" pushed on an empty stack)
======
pop() を 7 回実行すると、次の順序で文字が表示されます。
n,r,o,c,p,o,p
infix/postfix/prefix の変換は、スタックを教える際のコンピューター サイエンスの病理学的例です。
中置式への事後修正変換は非常に簡単です。
(式を左から右にスキャン)
したがって、53+2* がある場合、次の手順でそれを infix に変換できます。
*式の最後に到達したとき、それが正しく形成されていれば、スタックには 1 つのアイテムのみが含まれているはずです。
'x' と 'o' を導入することで、彼はそれらを中置式の左オペランドと右オペランドの一時的なホルダーとして使用していた可能性があります: x + o、x - o など (または x,o の順序が逆)。
ウィキペディアにも素敵な書き込みがあります。式の順序を間違えた場合に備えて、回答をwikiとして残しました。
中置式から前置式に移行するアルゴリズムは次のとおりです。
-reverse input
TOS = top of stack
If next symbol is:
- an operand -> output it
- an operator ->
while TOS is an operator of higher priority -> pop and output TOS
push symbol
- a closing parenthesis -> push it
- an opening parenthesis -> pop and output TOS until TOS is matching
parenthesis, then pop and discard TOS.
-reverse output
したがって、あなたの例は次のようになります (x PUSH, o POP):
2*3/(2-1)+5*(4-1)
)1-4(*5+)1-2(/3*2
Next
Symbol Stack Output
) x )
1 ) 1
- x )- 1
4 )- 14
( o ) 14-
o 14-
* x * 14-
5 * 14-5
+ o 14-5*
x + 14-5*
) x +) 14-5*
1 +) 14-5*1
- x +)- 14-5*1
2 +)- 14-5*12
( o +) 14-5*12-
o + 14-5*12-
/ x +/ 14-5*12-
3 +/ 14-5*12-3
* x +/* 14-5*12-3
2 +/* 14-5*12-32
o +/ 14-5*12-32*
o + 14-5*12-32*/
o 14-5*12-32*/+
+/*23-21*5-41
スタックは LIFO (後入れ先出し) データ構造です。プッシュとポップの操作は簡単です。プッシュは何かをスタックに置き、ポップは何かを取り除きます。LIFO順序を維持するために、上に置いて上から外します。
編集 -- FIFO から LIFO に修正。フェイスパーム！
説明のために、空のスタックから始めます
| |
次に、「x」を押します
| | 'バツ'
次に、「y」を押します
| | 'x' 'y'
それからあなたはポップ
| | 'バツ'
Ok。他の回答者が説明したように、スタックは後入れ先出しのデータ構造です。Push 操作を使用して、要素をスタックの一番上に追加します。ポップ操作で要素を一番上から取り出します。要素は、挿入された順序とは逆の順序で削除されます (したがって、後入れ先出し)。たとえば、エレメント 1、2、3 をこの順序でプッシュすると、番号 3 がスタックの一番上になります。ポップ操作はそれを削除し (最後のインでした)、スタックの一番上に 2 を残します。
講義の残りの部分では、講師は算術式を評価するスタックベースのマシンについて説明しようとしました。このマシンは、スタックの一番上から 3 つの要素を連続してポップすることによって動作します。最初の 2 つの要素はオペランドで、3 番目の要素は演算子 (+、-、、/) です。次に、この演算子をオペランドに適用し、結果をスタックにプッシュします。このプロセスは、スタック上に式の値である要素が 1 つだけになるまで続行されます。
したがって、値「+/*23-21*5-41」を左から右の順序でスタックにプッシュすることから始めるとします。次に、上から 3 つの要素をポップします。後入れ先出しです。つまり、最初の 3 つの要素は、「1」、「4」、「-」の順です。数値 3 (4-1 の結果) をスタックにプッシュし、最上位の 3 つの要素 (3、5、*) をポップします。結果の 15 をスタックにプッシュします。
原則として、スタックは非常に単純です。ライフルのクリップを想像してみてください。一番上の弾丸にしかアクセスできません。それを取り出すことを「ポップ」と呼び、新しいものを挿入することを「プッシュ」と呼びます。
そのための非常に便利な例は、「元に戻す」ことができるアプリケーションです。
アプリケーションの各状態をスタックに保存するとします。たとえば、ユーザーが作成したすべてのタイプの後のアプリケーションの状態。
ユーザーが「元に戻す」を押すと、スタックから前の状態が「ポップ」されます。ユーザーが行うアクションごとに、新しい状態をスタックに「プッシュ」します (もちろん単純化されています)。
あなたの講師が具体的に何をしていたかについて - それを説明するために、もう少し情報が役に立ちます..
これらすべての良い例の後、アダム・シャンクマンはまだそれを理解できません. いくつかのコードを開いて試してみるべきだと思います。myStack.Push(1) と myStack.Pop(1) を試してみると、実際に画像が得られるはずです。しかし、それはあなたにとって挑戦になるでしょう！