Java Algorithms Stacks!

memphis

Hi people.

I have a college assignment to do on Stacks, using Java. (Don't worry, I'm not intending to ask ye to do it for me, but I am seeking help).

I was wondering if someone could briefly explain to me how the push and pop algorithms works. The assignment program is to read in a postfix expression with numbers and operators. It then decides how to add, subtract, multipy, etc. For example, the user enters 12 3 + and the output should be 15. (it gets harder)!

Can someone explain how this works please. Once I understand the algorithm, I think I should have a better understanding of how to implement it in java.

Thanks in advance!!!

satchmo

Think of it as making a pile of plates. 'Pushing' is when you place a plate on top of the pile, 'popping' is when you take a plate off. The first plate to go on the pile will be the last to come off, since every other one will be stacked on top of it - hence the 'FILO' order (First In Last Out). Take this stack of numbers with 5 places:

[ ][ ][ ][ ][ ]
We push in a 1:
[1][ ][ ][ ][ ]
Then push in a 2 and then a 3:
[3][2][1][ ][ ]
Then 'pop' the stack - 3 (at the top) gets popped and returned
[2][1][ ][ ][ ]

The easiest way to program a stack is probably an array with a seperate index counter. Instead of shunting every number over by one to allow a new number to be pushed in (this isn't very efficient), we have a topOfStack pointer (just an int with an aray index in it) which keeps track of where the top of the stack is. So then whenever a new number gets pushed in, simply put the new number in at the topOfStack position, and move topOfStack over by one. Similarly when the stack gets popped, just move it back by one and return the number at the topOfStack position. The above example done this way: (X denotes where the topOfStack is pointing to)

[ ][ ][ ][ ][ ]
 X
push a 1:
[1][ ][ ][ ][ ]
    X
push a 2 and a 3:
[1][2][3][ ][ ]
          X
and pop the stack:
[1][2][ ][ ][ ]
       X

Handily enough, you can also make this stack into a Circular Buffer simply by allowing the topOfStack pointer to wrap around to the beginning when the stack gets full.

As for your postfix stack, when a binary operator gets pushed on, pop off the two previous numbers, perform the operation on them, and push the result back on. I seem to remember it being a little trickier than this, but that's the basic idea.

seamus

Originally posted by Jazz
As for your postfix stack, when a binary operator gets pushed on, pop off the two previous numbers, perform the operation on them, and push the result back on. I seem to remember it being a little trickier than this, but that's the basic idea.

Ah yes, I think you have it there. We did this last year but I kind of forgot.

For the postfix expression, evaluate every token in order. If the token is a number, push it onto the stack. If teh token is an operator, pop the previous 2 vales off the stack, perform the operation, and push the result onto the stack, then continue evaluating the symbols......

Kev

no, that would be a queue.

Rabies

Originally posted by memphis
I have a college assignment to do on Stacks, using Java. (Don't worry, I'm not intending to ask ye to do it for me, but I am seeking help).

I was wondering if someone could briefly explain to me how the push and pop algorithms works. The assignment program is to read in a postfix expression with numbers and operators. It then decides how to add, subtract, multipy, etc. For example, the user enters 12 3 + and the output should be 15. (it gets harder)!

Can someone explain how this works please. Once I understand the algorithm, I think I should have a better understanding of how to implement it in java.

memphis you should have it form last year. it is exactly the same assignment. look back through your notes and code and you will prob find it.

satchmo

He's right DBC, that'd be a queue. Shame on you, of all people!

DeadBankClerk

I heart 'delete' core.

Was looking at it from right to left or something bad

memphis

Originally posted by Rabies
memphis you should have it form last year. it is exactly the same assignment. look back through your notes and code and you will prob find it.

Hi there, my good old friend. Funny how you popped (no pun intended) back to boards.ie when I ask am important question.

Don't panic I have last years notes, and I also have the parenthesis code, that one of the girls gave me. I just wanted to understand the algorithm better.

Thanks for all the help everyone.