What do Push and Pop mean for Stacks?

Question

long story short my lecturer is crap, and was showing us infix to prefix stacks via an overhead projector and his bigass shadow was blocking everything so i missed the important stuff

he was referring to push and pop, push = 0 pop = x

he gave an example but i cant see how he gets his answer at all,

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

step 1 Reverse : )1-4(*5+)1-2(/3*2 ok i can see that

he then went on writing x's and o's operations and i got totally lost

answer 14-5*12-32*/+ then reversed again to get +/*23-21*5-41

if some one could explain to me the push pop so i could understand i would be very greatful, i have looked online but alot stuff im finding seems to be a step above this, so i really need to get an understanding here first

Nymphalid

Answer 1

Hopefully this will help you visualize a Stack, and how it works.

Empty Stack:

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

After Pushing A, you get:

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

After Pushing B, you get:

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

After Popping, you get:

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

After Pushing C, you get:

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

After Popping, you get:

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

After Popping, you get:

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

Ingressive

Thought the OP was not very clear, he's not asking about the basics of stacks. He's asking about the transformation of infix math to the equivalent prefix expression using stacks... – Especial

@dmckee: The title said What do Push and Pop mean for Stacks?, so I thought that the context of the question (infix math) was not relevent. – Ingressive

Well, it's not that the question was clear, or that the OP made it easy, but see his comment on hvgotcodes answer. – Especial

Answer 2

The rifle clip analogy posted by Oren A is pretty good, but I'll try another one and try to anticipate what the instructor was trying to get across.

A stack, as it's name suggests is an arrangement of "things" that has:

• A top
• A bottom
• An ordering in between the top and bottom (e.g. second from the top, 3rd from the bottom).

(think of it as a literal stack of books on your desk and you can only take something from the top)

Pushing something on the stack means "placing it on top". Popping something from the stack means "taking the top 'thing'" off the stack.

A simple usage is for reversing the order of words. Say I want to reverse the word: "popcorn". I push each letter from left to right (all 7 letters), and then pop 7 letters and they'll end up in reverse order. It looks like this was what he was doing with those expressions.

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

after pushing the entire word, the stack looks like:

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

when I pop() seven times, I get the letters in this order:

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

conversion of infix/postfix/prefix is a pathological example in computer science when teaching stacks:

Infix to Postfix conversion.

Post fix conversion to an infix expression is pretty straight forward:

(scan expression from left to right)

1. For every number (operand) push it on the stack.
2. Every time you encounter an operator (+,-,/,*) pop twice from the stack and place the operator between them. Push that on the stack:

So if we have 53+2* we can convert that to infix in the following steps:

1. Push 5.
2. Push 3.
3. Encountered +: pop 3, pop 5, push 5+3 on stack (be consistent with ordering of 5 and 3)
4. Push 2.
5. Encountered *: pop 2, pop (5+3), push (2 * (5+3)).

*When you reach the end of the expression, if it was formed correctly you stack should only contain one item.

By introducing 'x' and 'o' he may have been using them as temporary holders for the left and right operands of an infix expression: x + o, x - o, etc. (or order of x,o reversed).

There's a nice write up on wikipedia as well. I've left my answer as a wiki incase I've botched up any ordering of expressions.

Paperweight

Oops. Talking about @oren A's example. This became a popular question to answer it seems. – Paperweight

Answer 3

The algorithm to go from infix to prefix expressions is:

-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

So your example goes something like (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

Protege

Finally a responsive answer (admittedly, it took a while to get the OP to be clear what the questions was...)! However, you haven't been fully clear yet. You have implicitly reversed the input (say be sticking on an stack before you begin), and likewise implicitly reversed the output. Probably the OP got that much from the lecture, but future readers would benefit from your being explicit here... – Especial

How is it possible to write down the code because we cannot pass symbols as argument ? – Oleic

Answer 4

A Stack is a LIFO (Last In First Out) data structure. The push and pop operations are simple. Push puts something on the stack, pop takes something off. You put onto the top, and take off the top, to preserve the LIFO order.

edit -- corrected from FIFO, to LIFO. Facepalm!

to illustrate, you start with a blank stack

|

then you push 'x'

| 'x'

then you push 'y'

| 'x' 'y'

then you pop

| 'x'

Jacobson

Stacks are Last In First Out. FIFO is a queue. – Reminisce

Mixed up stacks with queues. Stacks are LIFO (last in, first out), whereas Queues are FIFO structures. You push items onto a stack, and when you pop, you get the last item you put into it. For queues, pushing adds items, but pop returns the first thing you put in. – Kosaka

thanks for some feedback guys, @matt i didnt mean to be insulting to the man, but imo he's not as good a teacher compared to the rest of my lecturers in my other modules, programming, comp org, comp maths, comp apps, sorry if the word crap offends you. I am in college in Ireland Nix, and adam shankman isnt my real name, so no fear of any repercussions there lol en.wikipedia.org/wiki/Adam_Shankman, any how back to my predicament i dont understand how we convert 2*3/(2-1)+5*(4-1) to final answer +/*23-21*5-41 via the push pop, He gave a 30 minute lecture and my notes aren't much good !! – Nymphalid

Answer 5

A stack in principle is quite simple: imagine a rifle's clip - You can only access the topmost bullet - taking it out is called "pop", inserting a new one is called "push".
A very useful example for that is for applications that allow you to "undo".
Imagine you save each state of the application in a stack. e.g. the state of the application after every type the user makes.
Now when the user presses "undo" you just "pop" the previous state from the stack. For every action the user does - you "push" the new state to the stack (that's of course simplified).
About what your lecturer specifically was doing - in order to explain it some more information would be helpful..

Daniels

@Oren: The undo stack example is good, not everyone knows how a rifle's clip operates... – Curettage

@Amnon: Thanks. You obviously do.. Let's see if those who you think don't, really don't.. I'll try to think of a better one anyhow (-: – Daniels

Pez dispenser is the one my instructor used. Anyone who's familiar with the trading card game Magic:The Gathering knows intrinsically how a stack works. – Gluteal

@Oren. It's a stack of pancakes. Everyone knows pancakes. Add new pankake to the top of the stak = push. Eat the pancake off the top of the stack = pop. Look at the pancake on the top of stack and drool = peek. You can't (easily) access lower pancakes without first eating the ones on top of them. – Usual

@Visionary: Wouldn't know what that is called in English in a gazillion years... But yeah, it's a good example. – Daniels

@Jason - But in a stack of pancakes you can always see all of them.. (don't mean to be petty.. But I think it's less obvious). – Daniels

@Oren: You can't see the faces of the panckes - only enough of the sides to count them. Unlike a rifle clip, you can't take an item off the bottom, the stack cannot be oriented sideways, and it is often actually called a 'stack of pancakes'. (This is a rifle clip: rickysinc.com/Ammo/Ammo%20French%208-5.jpg) – Usual

@Jason: This is a very specific and unlike the most, example of a rifle clip. Most rifle clips look like M-16's for example - deuce45s.com/…. But you proved Amnon's point. I'll use Pez dispenser for someone that English is he's first language, next time. – Daniels

@Oren: That's an "ammunition magazine", not a "rifle clip". (not that it particularly matters, but if you want people to get the concept (and it is a good concept), it just helps to use the right word) – Usual

There it is.. My English again. Anyhow, thanks for the tip (-: – Daniels

Answer 6

Ok. As the other answerers explained, a stack is a last-in, first-out data structure. You add an element to the top of the stack with a Push operation. You take an element off the top with a Pop operation. The elements are removed in reverse order to the order they were put inserted (hence Last In, First Out). For example, if you push the elments 1,2,3 in that order, the number 3 will be at the top of the stack. A Pop operation will remove it (it was the last in) and leave 2 at the top of the stack.

Regarding the rest of the lecture, the lecturer tried to describe a stack-based machine that evaluates arithmetic expressions. The machine operates by continuously popping 3 elements from the top of the stack. The first two elements are operands and the third is an operator (+, -, *, /). It then applies this operator on the operands, and pushes the result onto the stack. The process continues until there is only one element on the stack, which is the value of the expression.

So, suppose we begin by pushing the values "+/*23-21*5-41" in left-to-right order onto the stack. We then pop 3 elements from the top. The last in is first out, which means the first 3 element are "1", "4", and "-" in that order. We push the number 3 (the result of 4-1) onto the stack, then pop the three topmost elements: 3, 5, *. Push the result, 15, onto the stack, and so on.

Curettage

what the lecturer explained is how to convert an infix expression to a prefix expression using a stack, so you can evaluate it later using another stack. – Protege

Answer 7

• push = add to the stack
• pop = remove from the stack

Bronchiectasis

Answer 8

Simply:

• pop: returns the item at the top then remove it from the stack

• push: add an item onto the top of the stack.

Maryrose

Answer 9

after all these good examples adam shankman still can't make sense of it. I think you should open up some code and try it. The second you try a myStack.Push(1) and myStack.Pop(1) you really should get the picture. But by the looks of it, even that will be a challenge for you!

Kimbro