StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The rifle clip analogy posted by <strong>Oren A</strong> is pretty good, but I'll try another one and try to anticipate what the instructor was trying to get across.</p> <p>A stack, as it's name suggests is an arrangement of "things" that has:</p> <ul> <li>A top</li> <li>A bottom</li> <li>An ordering in between the top and bottom (e.g. second from the top, 3rd from the bottom).</li> </ul> <p>(think of it as a literal stack of books on your desk and you can only take something from the top)</p> <p>Pushing something on the stack means "placing it on top". Popping something from the stack means "taking the top 'thing'" off the stack.</p> <p>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.</p> <p>push(p) push(o) push(p) push(c) push(o) push(r) push(n)</p> <p>after pushing the entire word, the stack looks like:</p> <pre><code> | n | <- top | r | | o | | c | | p | | o | | p | <- bottom (first "thing" pushed on an empty stack) ====== </code></pre> <p>when I pop() seven times, I get the letters in this order:</p> <p>n,r,o,c,p,o,p</p> <p>conversion of infix/postfix/prefix is a pathological example in computer science when teaching stacks:</p> <p><a href="http://scriptasylum.com/tutorials/infix_postfix/algorithms/infix-postfix/index.htm" rel="noreferrer">Infix to Postfix conversion.</a></p> <p>Post fix conversion to an infix expression is pretty straight forward:</p> <p>(scan expression from left to right)</p> <ol> <li>For every number (operand) push it on the stack.</li> <li>Every time you encounter an operator (+,-,/,*) pop twice from the stack and place the operator between them. Push that on the stack:</li> </ol> <p>So if we have 53+2* we can convert that to infix in the following steps:</p> <ol> <li>Push 5.</li> <li>Push 3.</li> <li>Encountered +: pop 3, pop 5, push 5+3 on stack (be consistent with ordering of 5 and 3)</li> <li>Push 2.</li> <li>Encountered *: pop 2, pop (5+3), push (2 * (5+3)).</li> </ol> <p>*When you reach the end of the expression, if it was formed correctly you stack should only contain one item.</p> <p>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).</p> <p>There's a nice <a href="http://en.wikipedia.org/wiki/Reverse_Polish_notation" rel="noreferrer">write up on wikipedia</a> as well. I've left my answer as a wiki incase I've botched up any ordering of expressions.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload