Что означают Push и Pop для стеков?

Question

Короче говоря, мой лектор - дерьмо, и он показывал нам инфикс для префикса стеков через оверхед, и его огромная тень блокировала все, поэтому я пропустил важные вещи

он имел в виду толчок и поп,push = 0 pop = x

он привел пример, но я вообще не вижу, как он получает свой ответ,

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

шаг 1 Обратный ход: )1-4(*5+)1-2(/3*2 хорошо, я вижу, что

Затем он продолжал писать операции X и O, и я полностью растерялся

answer 14-5*12-32*/+, затем снова повернулся, чтобы получить +/*23-21*5-41

, если кто-нибудь сможет мне объяснитьтолчок, чтобы я мог понять, я был бы очень признателен, я смотрел онлайн, но много вещей, которые я нашел, кажется, на шаг выше этого, поэтому мне действительно нужно сначала получить понимание здесь

Answer 1

Надеюсь, это поможет вам визуализировать стек и как он работает.

Пустой стек:

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

После нажатия A вы получите:

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

После нажатия B вы получите:

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

После Popping вы получаете:

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

После нажатия C вы получите:

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

После Popping вы получаете:

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

После Popping вы получаете:

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

Answer 2

Аналогия с винтовочным зажимом, опубликованная Oren A , довольно хороша, но я попробую другой и попытаюсь предугадать, что инструктор пытался донести.

Стек,как следует из названия, это расположение «вещей», которое имеет:

• Верх
• Низ
• Порядок между верхом и низом (например, второйсверху, 3-е снизу).

(представьте, что это буквальная стопка книг на вашем столе, и вы можете взять что-то только сверху)

Что-то толкатьв стеке означает «положить его сверху».Извлечение чего-либо из стека означает «убрать верхнюю« вещь »из стека».

Простое использование - изменение порядка слов.Скажем, я хочу поменять слово: «попкорн».Я нажимаю каждую букву слева направо (все 7 букв), а затем выталкиваю 7 букв, и они заканчиваются в обратном порядке.Похоже, именно это он делал с этими выражениями.

push (p) push (o) push (p) push (c) push (o) push (r) push (n)

после нажатия всего слова стек выглядит следующим образом:

   |  n   |  <- top
   |  r   |
   |  o   |
   |  c   |
   |  p   |
   |  o   |
   |  p   |  <- bottom (first "thing" pushed on an empty stack)
    ======

когда я pop () семь раз, я получаю буквы в следующем порядке:

n, r, o, c, p, o, p

преобразование инфикса / постфикса / префикса является патологическим примером в информатике при обучении стекам:

преобразование инфикса в постфикс.

Преобразование после исправления в инфиксное выражение довольно простое:

(сканирование выражения слева направо)

1. Для каждого числа (операнда) нажмите его наstack.
2. Каждый раз, когда вы сталкиваетесь с оператором (+, -, /, *), дважды выталкивайте из стека и помещайте оператор между ними.Вставьте это в стек:

Итак, если у нас есть 53 + 2 *, мы можем преобразовать это в инфикс, выполнив следующие шаги:

1. Нажмите 5.
2. Push 3.
3. Обнаружено +: pop 3, pop 5, push 5 + 3 в стеке (соответствует порядку 5 и 3)
4. Push 2.
5. Encountered *: pop 2, pop (5 + 3), push (2 * (5 + 3)).

* Когда вы достигнете конца выражения, если оно было сформировано правильно, выстек должен содержать только один элемент.

Введя 'x' и 'o', он, возможно, использовал их в качестве временных держателей для левого и правого операндов выражения infix: x + o, x - o,и т. д. (или порядок x, o обратный).

В Википедии также есть хорошая запись.Я оставил свой ответ в виде вики-случая. Я испортил любой порядок выражений.

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

Answer 4

Стек - это структура данных LIFO (Last In First Out). Операции push и pop просты. Push кладет что-то в стек, а pop снимает. Вы кладете на верх и снимаете верх, чтобы сохранить порядок LIFO.

edit - исправлено из FIFO в LIFO. Facepalm!

чтобы проиллюстрировать, вы начинаете с пустого стека

|

тогда вы нажимаете 'x'

| 'Х'

тогда вы нажимаете 'y'

| 'x' 'y'

тогда вы поп

| 'Х'

Answer 5

• push = добавить в стек
• pop = удалить из стека

Answer 6

Хорошо. Как объяснили другие авторы, стек - это структура данных «первым пришел - первым вышел». Вы добавляете элемент на вершину стека с помощью операции Push. Вы берете элемент сверху с помощью операции Pop. Элементы удаляются в обратном порядке в том порядке, в котором они были вставлены (следовательно, Last In, First Out). Например, если вы подтолкнете элементы 1,2,3 в таком порядке, число 3 будет на вершине стека. Операция Pop удалит его (он был последним) и оставит 2 на вершине стека.

Что касается остальной части лекции, лектор попытался описать основанную на стеке машину, которая оценивает арифметические выражения. Машина работает, непрерывно выталкивая 3 элемента из верхней части стопки. Первые два элемента являются операндами, а третий - оператором (+, -, *, /). Затем он применяет этот оператор к операндам и помещает результат в стек. Процесс продолжается до тех пор, пока в стеке не останется только один элемент, который является значением выражения.

Итак, предположим, что мы начинаем с помещения значений "+ / * 23-21 * 5-41" в порядке слева направо в стек. Затем мы выталкиваем 3 элемента сверху. Последний вход - первый выход, что означает, что первые 3 элемента - это «1», «4» и «-» в этом порядке. Мы помещаем число 3 (результат 4-1) в стек, а затем выталкиваем три верхних элемента: 3, 5, *. Поместите результат 15 в стек и т. Д.

Answer 7

Просто:

• pop : возвращает элемент сверху и удаляет его из стека

• push : добавить предмет на вершину стека.

Answer 8

Стек в принципе довольно прост: представьте себе винтовочный зажим - Вы можете получить доступ только к самой верхней пуле - вынуть ее называется «поп», а вставить новую - «толкать».
Очень полезный пример для этого - для приложений, которые позволяют вам «отменить».
Представьте, что вы сохраняете каждое состояние приложения в стеке. например состояние приложения после каждого типа, который делает пользователь.
Теперь, когда пользователь нажимает «отменить», вы просто «выталкиваете» предыдущее состояние из стека. За каждое действие, которое выполняет пользователь - вы «помещаете» новое состояние в стек (это, конечно, упрощено).
О том, что конкретно делал ваш лектор, - чтобы объяснить это, была бы полезна дополнительная информация.

Answer 9

после всех этих хороших примеров Адам Шенкман все еще не может понять это.Я думаю, что вы должны открыть некоторый код и попробовать его.После того, как вы попробуете myStack.Push (1) и myStack.Pop (1), вы действительно должны получить картину.Но, судя по всему, даже это будет проблемой для вас!