Push和Pop对堆栈意味着什么？

Question

长话短说我的讲师是垃圾，他通过投影仪向我们展示了前缀堆栈，他的大阴影挡住了一切，所以我错过了重要的东西。

他指的是推和弹，推=0，弹出=x

他举了一个例子，但我根本不明白他是如何得到答案的，

2*3/(2-1)+5*(4-1)

step 1反转：)1-4(*5+)1-2(/3*2 ok我可以看到

然后他继续写x和o的运算，我完全迷惑了。

回答14-5*12-32*/+，然后再次颠倒以获得+/*23-21*5-41

如果有人能给我解释一下推送弹出，这样我就可以理解了，我已经在网上看过了，但是我发现很多东西似乎比这更进一步，所以我真的需要先在这里得到一个理解。

Answer 1

希望这能帮助你可视化一个Stack，以及它是如何工作的。

空堆栈：

|     |
|     |
|     |
-------

在推送A之后，你会得到：

|     |
|     |
|  A  |
-------

在推送B之后，你会得到：

|     |
|  B  |
|  A  |
-------

弹出后，你会得到：

|     |
|     |
|  A  |
-------

在推送C之后，你会得到：

|     |
|  C  |
|  A  |
-------

弹出后，你会得到：

|     |
|     |
|  A  |
-------

弹出后，你会得到：

|     |
|     |
|     |
-------

Answer 2

Oren A发布的步枪夹类比相当不错，但我将尝试另一个类比，并尝试预测教练试图传达的内容。

顾名思义，堆栈是一种“事物”的排列，它具有：

• A top
• A bottom
• 在顶部和底部之间的排序(例如，从顶部第二个，从底部第三个)。

(把它想象成书桌上的一堆书，你只能从上面拿东西)

把一些东西放到堆栈上意味着“把它放在最上面”。从堆栈中弹出一些东西意味着“从堆栈中取出顶部的‘东西’”。

一个简单的用法是颠倒单词的顺序。假设我想颠倒这个词：“爆米花”。我从左往右推每个字母(全部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)
    ======

当我弹出()七次时，我得到的字母顺序如下：

n，r，o，c，p，o，p

中缀/后缀/前缀的转换是计算机科学中在教授堆栈时的一个病理示例：

Infix to Postfix conversion.

将后缀转换为中缀表达式非常简单：

(从左到右扫描表达式)

1. For stack (操作数)将其推送到堆栈上。
2. 每次遇到运算符(+，-，/，*)时，从堆栈中弹出两次，并将运算符放在它们之间。把它推到堆栈上：

因此，如果我们有53+2*，我们可以通过以下步骤将其转换为infix：

1. Push 5.
2. Push 3.
3. Encountered +：pop 3，pop 5，push 5+3 on stack (与5和3顺序一致)
4. push 2.
5. Encountered *：pop 2，pop (5+3)，push (2 *(5+3))。

*当您到达表达式的末尾时，如果它的格式正确，则堆栈应该只包含一项。

通过引入“x”和“o”，他可能一直将它们用作中缀表达式的左操作数和右操作数的临时保持器:x+ o、x-o等(或者x、o的顺序颠倒)。

还有一个很好的write up on wikipedia。我把我的答案留在了wiki上，以防我搞砸了表达式的任何顺序。

Answer 3

从中缀表达式到前缀表达式的算法是：

-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