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

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

он имел в виду push и pop, push = 0 pop = x

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

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

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

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

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

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

Ответ 1

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

Пустой стек:

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 2

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

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

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

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

Нажатие чего-то на стеке означает "размещение его сверху". Выталкивать что-то из стека означает "взять верхнюю вещь" из стека.

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

толчок (р) толчок (о) толчок (р) толчок (с) толчок (о) толчок (г) толчок (п)

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

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

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

п, г, о, с, р, о, р

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

Инфикс для преобразования Postfix.

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

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

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

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

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

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

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

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

Ответ 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

Ответ 4

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

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

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

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

| 'Х'

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

| 'x' 'y'

тогда вы поп

| 'Х'

Ответ 5

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

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

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

Ответ 6

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

Ответ 7

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

Ответ 8

Просто:

pop: возвращает элемент сверху, затем удаляет его из стека
нажмите: добавьте элемент на вершину стека.

Ответ 9

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