Questions about Reverse Polish Notation.

[notfred]

OK, I'm reading about this, trying to figure it out, but what I'm reading is inconsistent. I have 2 examples here:

1 2 + 4 * 3 +
which translates to:
((1 + 2) * 4) + 3

And that makes sense. add the 1 adn the two, multiply the result by 4, and add 3 to the result.

then I have this example:
3 4 7 + *
Which is supposed to translate to: 3 * ( 4 + 7)

How come it's not written as 4 7 + 3 *?
That would be consistent with the first example. And then, even if it's written how it is, it seems like it should represent (3+4)*7 instead of 3*(4+7).

Can someone help explain this?

 

[CanOWorms]

I used to do it like this... the numbers stack on top of each other. When you come up to an operator, you pop the 2 on top of the stack and perform the operation, get the result and put it back into the stack.

So

3 4 7 + *

the 3, 4, and 7 are into the stack like this:

7
4
3

You get to the +, so then you pop the 7 and 4 and get 11 (4+7) and put it in the stack so you have:

11
3

then you pop those 2 because you get to the * and get (4+7)*3

 

[StormRider]

Originally posted by: CanOWorms
I used to do it like this... the numbers stack on top of each other. When you come up to an operator, you pop the 2 on top of the stack and perform the operation, get the result and put it back into the stack.

Yep, that's how I think about it.

 

[Jzero]

You have to read each token one-by-one from left to right. Push numbers onto the stack. When you encounter an operator, you pop the two topmost operands, execute the operation and push the result back onto the stack.
Push 3
Push 4 (Stack = 3, 4)
Push seven (Stack = 3, 4, 7)
Encounter +. Execute on 7 and 4. Push 11 onto stack (Stack = 3, 11).
Encounter *. Execute on 3 and 11. Push 33 onto stack.

It is the same as 4 7 + 3 *

That's the only way I can make RPN work for me.

 

[Hayabusa Rider]

Lets do the second example

3
4
7
+
*

The 3 and 4 do not act on each other. They are in the stack, and no operator is after the 4. It just sits there for now. The 4 and 7 do have an operator following, so you have 11

you now have

3
11
*

That gives 33, which is what you are supposed to have. Remember RPN is not nested. It works left to right and whatever operator appears always acts on the 2 numbers immediately preceding. Follow that rule.

 

[amnesiac]

Dammit, you guys broke my nerd-o-meter.

Thanks a lot. :|

 

[Jzero]

RPN is cool b/c it eliminates the need for parenthesis and confusion over order of operations....

 

[Hayabusa Rider]

Originally posted by: Jzero
RPN is cool b/c it eliminates the need for parenthesis and confusion over order of operations....

Its also cool because I have an HP 48G

 

[GoSharks]

49g here - rpn kicks ass, so much easier and faster [for me]

 

[Soybomb]

Tell me I wasn't the only one who when they heard someone mention reverse polish notation (I was in highschool at the time) that thought they were getting a huge load of crap fed to them. I figured it had to be some math geeks joke like pig latin or something. Then I figured out they were serious

 

[syberscott]

48G and 49G, ha!

 

[dfi]

Originally posted by: Hayabusarider

Originally posted by: Jzero
RPN is cool b/c it eliminates the need for parenthesis and confusion over order of operations....

Its also cool because I have an HP 48G

HP48G POWNS JOO!

Yes, I own one too.

dfi

 

[Ameesh]

reverse polish notation (like on the hp calcs) is also known as using a stack, or LIFO buffer, as a CS student you probably know what stacks are and how they work.

 

[MazerRackham]

Originally posted by: Hayabusarider

Originally posted by: Jzero
RPN is cool b/c it eliminates the need for parenthesis and confusion over order of operations....

Its also cool because I have an HP 48G

My 48G died last year, and I'm still sad about it!

I want the "hard" keys on the 48 series, so I'm going to pass on the 49 series for now...

 

[Hayabusa Rider]

Can TI calcs be used in RPN? I hate to think when my hp goes, I have to go back to the old way. I piss people off because I am much faster than they are, and they cant figure it out

 

[sciencewhiz]

both ways get the same answer, chose which one you like best

 

[notfred]

Originally posted by: Hayabusarider
Lets do the second example

3
4
7
+
*

The 3 and 4 do not act on each other. They are in the stack, and no operator is after the 4. It just sits there for now. The 4 and 7 do have an operator following, so you have 11

you now have

3
11
*

That gives 33, which is what you are supposed to have. Remember RPN is not nested. It works left to right and whatever operator appears always acts on the 2 numbers immediately preceding. Follow that rule.

How does that work on a stack? You'd have to pop the 3, 4, and 7 before you got to the +. It's not much of a stack if you have to tear the whole thing apart.

You get to the +, so then you pop the 7 and 4 and get 11 (4+7) and put it in the stack so you have:

How do you "get" to the plus? You either have to skip over the three numbers, or skip over the *... it doesn't make any sense.

 

[gopunk]

read 3, push 3
read 4 push 4
read 7 push 7
read +, pop 7, pop 4, push 11 [note: since this is 7+4]
read * pop 11, pop 3, push 33 [note: since this is 11*33]

note that you could also write this as:

4 7 * 3 +

 

[wake]

Damn I miss college...

 

[dighn]

Originally posted by: notfred

Originally posted by: Hayabusarider
Lets do the second example

3
4
7
+
*

The 3 and 4 do not act on each other. They are in the stack, and no operator is after the 4. It just sits there for now. The 4 and 7 do have an operator following, so you have 11

you now have

3
11
*

That gives 33, which is what you are supposed to have. Remember RPN is not nested. It works left to right and whatever operator appears always acts on the 2 numbers immediately preceding. Follow that rule.

How does that work on a stack? You'd have to pop the 3, 4, and 7 before you got to the +. It's not much of a stack if you have to tear the whole thing apart.

he's "stacking" to the bottom

add to the bottom, remove frm the bottom. same thing as stacking on top

 

[manly]

Originally posted by: Hayabusarider

Originally posted by: Jzero
RPN is cool b/c it eliminates the need for parenthesis and confusion over order of operations....

Its also cool because I have an HP 48G

I also have a 48G, and I always wished I had the GX even though I *never* use the calculator.

I guess between RPN and the Calculus threads, math is notfred's Achille's Heal?

I don't think there's anything to be added to the explanation (Ameesh pretty much summed it up), except to say the operator implicitly pops the last two operands off the stack, operates on them, and then pushes the result back onto the stack. So what's a bit vague from the example input string, "3 4 7 + *" is that the stack has been changed as soon as the + operation is performed.

 

[notfred]

I think I got it now. The operators don't go onto the stack, they're operated on immediately, and only the numbers are pushed to the stack, right?
I'll practice it a bit tomorrow.

And I may not be the best in the world at calculus, but I've never been exposed to RPN before today. I think if I understand it by the end of tomorrow, I'm doing ok

 

[ElFenix]

i have a 48G

what a great calculator

once you get use to RPN its sooo much better

 

[manly]

Originally posted by: notfred
I think I got it now. The operators don't go onto the stack, they're operated on immediately, and only the numbers are pushed to the stack, right?
I'll practice it a bit tomorrow.

Yeah, like I alluded to, the problem is that the example input string "3 4 7 + *" doesn't really elucidate the actual mechanics of RPN. It's just a rough notation. I was considering showing the state of the stack step by step, but I'm too lazy to be bothered. (Actually Jzero already did this.)

And I may not be the best in the world at calculus, but I've never been exposed to RPN before today. I think if I understand it by the end of tomorrow, I'm doing ok

Sounds like you already got it; it takes just a few minutes with an HP calculator in your hands. Unfortunately, Calculus takes a bit longer. Funny thing is it appears most geeks exposed to HP calculators become RPN zealots for life, even though they hardly ever break out the calculator anymore.

 

[Hayabusa Rider]

I have never seen one page on RPN, except in my HP manual, so I probably used incorrect terminology. I just look at a thing and see how it works, and I do not always know the proper labels. Just an intuitive answer to me. Sorry for the confusion