Reverse Polish Grows on Trees - Computerphile 

However, even the HP folks admitted that algebraic entry (as TI was doing) was much easier and simpler. Hence why RPN fell out of use. It actually does take more up-front training. You end up using your tool in a way which contradicts how all written math is done. I like the concept of RPN and I like HP calcs, but it's important to recognize that it's *not* inherently superior. It forces you to re-arrange the equation in your head, instead of just typing it in as you would write it down.

I feel like one thing that is being undersold is that infix calculators, in an attempt to take away the hard work, seriously end up gimping the user by robbing them access to the stack. Meanwhile postfix and prefix calculators are pretty much forced to give you access to a stack and it greatly expands the capabilities of the calculator. A great example being looking at the quadratic formula, which is often one of the first programs people are taught to put in their calculators. When you solve it you don't just get one solution, you usually get two. A RPN calculator handles that perfectly. It just pushes both values to the stack. Both values become readily available for you or your programs to use in an incredibly predictable manor. Meanwhile an infix calculator isn't really set up to store temporary values. The best most of them will do is store one of the solutions in an ANS variable. If you want both answers though you are just out of luck without resorting to global variables. So on infix calculators you are stuck writing programs that have to stand pretty much completly alone. Creating actual functions that can feed each other was only supported on the most expensive of the TI calculators. Even then the functionality of those functions was limited as you couldn't return complex data structures, something trivial to do on an RPN calculator.

ive first found out that RPN exists after discovering forth, and found the idea of manipulating a stack of numbers quite interesting

LaTeX is wonderful.

But I want 2^3^4 to be treated as (2^3)^4 and give me 4096, because that is the most common scenario by far when doing computations. For instance I would rather hope that e^(ln 10)^3 gives me 1000 and not 200400.18. If I had a calculator that gave the latter answer I might be inclined to reprogram it with a hammer...

ib9rt Actually, you probably don't. If you read a typeset paper on mathematics and it has a 2 with a small 3 above it to the right and an even smaller 4 above that and to the right (or some other operand) it translates to a right-associative operation when written out without typesetting since (2^3)^4 = 2^(3*4). It's also a natural extention into tetration since it doesn't require parentheses. I'll admit that it's rather contrived and likely to screw up anyone not in the know which is why I nerd sniped some of my friends with it. I imagine almost all new calculators will probably use the right-associative version from now on though. I always wonder if the reason languages like C and Java don't have an operator for exponentiation on integral types is because of this. I find the potential that there's someone out there who implements a library that overloads the bitwise xor operator as exponentiation and a poor sap that uses that operator twice in a row without understanding the associativity of the operators in the mathematical paper they probably got the algorithm from and the ones in the language to be pretty funny.

You learned polish when you were 14?? Congrats, it's a difficult language! :D

+Harrison Harris For "(a / b) / c" you could just write in RPN "a b / c /" RPN doesn't mean that all of the operators must be at the end of an expression.

+Harrison Harris There are also stack manipulation operations such as SWAP and ROT (swap and rotate). 1 2 3 SWAP => 1 3 2 1 2 3 ROT => 2 3 1 So given "a b c" and trying to achieve "(a/b)/c" you can do "a b c ROT ROT / /" or just "a b / c/" like the other commenter said.

I think he definitely could have simplified that explanation. What he's doing is a depth-first search, which I think should have been mentioned. If you follow the path that he drew, it's much easier to say that you write down anything you find while moving back toward the top of the tree. Or, anything immediately to the left of your path while you draw it can be written down. There's no need to differentiate between the operators and operands.

Sure. Walking a tree is actually simpler, though harder to see the bigger picture because it's recursive. It looks like this: visit(node): if isOperand(node): print(node) else: visit(node.right) visit(node.left) print(node)

0pyrophosphate0 Ah, yeah, that makes sense. Sean Wolcott Shouldn't you print the left node first and then the right node? Also, isn't that exactly what I wrote?

NNOTM Yes, and yes. I didn't see you had more to say, and I confuse my left and right.

NNOTM rewrite your algorithm as an iterative function and you will see that it is equivalent to walking around the tree.

+amigojapan Basically, you start at the deepest level of your expression and chain those bits together. Consider the infix expression "(1+2)/(3+4)". You can see that before doing the division you need to do each addition, starting with the numerator, then divide those two results together (in the correct order, of course). postfix( 1 2 + ) = infix( 1 + 2 ) postfix( 3 4 + ) = infix( 3 + 4 ) postfix( a b / ) = infix( a / b ) Chaining them together: postfix( 1 2 + 3 4 + /) = infix( ( 1 + 2 )/( 3 + 4 ) ) Notice the number of parentheses used for each style. The RPN uses 0 parentheses, which means fewer keystrokes and faster input.

In the animation dude's defense, the professor was being confusing. He kept saying "looking to the left", but at the same time he kept talking about a node in the tree when he passed by it, whether the node was to the left or not. If he truly only ever looked to the left, he would never see an operator before an operand, and wouldn't have to ask the question "can you write it down?". You can see that the professor messes up on the root node (the plus) when he asks if you can write it down when he's at the bottom of the node. From the bottom of the node while looking left, you can't see the node at all. So he shouldn't have mentioned it in the first place. When the root node finally is to the left of the walking dude, he will have passed all other nodes and the root will be the only one left to write down. So I can understand why the animation guy was confused.

DGCDWJ the professor meant looking to 90 degrees anticlockwise to the direction you're currently walking.

actually, the whole tree is turned 90 degrees to the left (or anticlockwise) in the professor`s paper - so he is absolutely right, but the animation is not so accurate!

Not to YOUR left, to the left from the perspective of the character walking around the tree, imagine you're the character, and you're walking forward around the tree, then you look to the left. Not to the left on the paper, the left direction is dependent on what direction the character is moving.

ahhh ty so much @@timotree3

yeah, but you would see B before A and thus you'd end up with bac*+ which is definitely not what you want. If you're looking to the right you'd also have to then specify a limit of how far to the right can you actually see. since the example is huggint the tree to the characters left side, you only see the immediate node next to you, while for this to work with the right side would require range, and would mess up even more on more sophisticated trees.

Many thanks for spotting this, I will add an annotation - and apologies! >Sean

that can be done, but a lot comes down to performance: directly interpreting the syntax-tree tends to make for a fairly slow interpreter (say, 1000x slower than native C); compiling to bytecode, it can be made a fair bit faster, more so if the bytecode already has all the type-information and variable locations worked out. if you then directly interpret the bytecode, often it may be instead closer to 100x (most of the time typically going into a "while/switch" loop or similar construction). otherwise, we can convert it to threaded-code (interpreting via a series of direct function calls), and get maybe 10x-30x of native speed; if converted into naive ASM / machine-code, and then run, it may be around 3x-5x of native C; throw a register allocator and an optimizer on it, and it may be 1x-2x. so, typically, static compilers will convert everything to optimized machine code, so that it runs fast (albeit the compiler is slower and the code isn't really portable). compilers for VMs will often compile to a stack-based bytecode, leaving it up to the backend what to do with the code (say, directly interpreting single-use functions, and JIT compiling frequently-used functions, ...). like, fast as computers are, for many things performance can still often be an issue. some VMs will use a register-oriented bytecode (ex: like Dalvik or LLVM), which has pros and cons vs a stack bytecode: it is more complicated to produce by a compiler, but can be higher-performance for threaded-code or JIT output (for a still relatively simple backend, mostly due to typically needing 30-60% fewer operations to accomplish a task and being able to put more of the work on the compiler). (note: "registers" in this sense are closer to temporary-variables than to CPU registers). also possible is to use a stack-based bytecode, but convert to a register IR internally for the threaded-code or JIT, allowing for simpler compilers at the cost of a more complicated backend (they now need to flatten the stack onto registers/temporaries and similar, include a basic optimizer, ...). this being fairly common in stack-based VMs.

Yes, you're absolutely right about the performance aspect of course. I was assuming that the code is parsed and executed exactly once (like for example in some kind of calculator application), in which case recursive evaluation should be faster, I suspect. That is, however, unrealistic for most real programs out there.

Björn P. yeah, could be. this is a fairly common strategy in many LISP variants IIRC. also fairly common though in these cases (such as in a shell or shell-script interpreter or similar) is to directly parse the code and execute commands on a token-by-token basis (without building an intermediate AST), where generally the input is a big glob of code. likewise, in assemblers, it is fairly common to go fairly directly from the ASM to the machine-code output (with no intermediate AST). in past experiments, I had observed that it was possible to feed about 10-15 MB/sec of ASM code through an assembler, which seemed "probably fast enough" at the time. going directly from tokens to bytecode would probably be a bad idea for an HLL compiler though (would tangle/complicate things and hinder AST-level operations, such as expression folding, ...).

you mean china

You don't want a reverse polish notation stain on your shirt.