• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

Questions about Reverse Polish Notation.

N

notfred

Lifer
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?
 
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
 
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.
Click to expand...

Yep, that's how I think about it.
 
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.
 
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.
 
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 😀
 
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....
Click to expand...

Its also cool because I have an HP 48G 😀
Click to expand...

HP48G POWNS JOO!

Yes, I own one too.

dfi
 
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.
 
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....
Click to expand...

Its also cool because I have an HP 48G 😀
Click to expand...

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...
 
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 🙂
 
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.
Click to expand...

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:
Click to expand...

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.
 
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 +
 
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.
Click to expand...

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.
Click to expand...

he's "stacking" to the bottom

add to the bottom, remove frm the bottom. same thing as stacking on top
 
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....
Click to expand...

Its also cool because I have an HP 48G 😀
Click to expand...
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.
 
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 🙂
 
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.
Click to expand...
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 🙂
Click to expand...
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.
 
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 🙂
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top