332 5 3 * -
12 34 2- * 8 /
At first glance, the two styles are very strange, is it? They are a notation of an expression of an expression that is going to talk about.
Now, prepare a very narrow cylinder, the cartridge is bottom, like a slender cup, rough fine and a coin. Do a few small round paper on the same coin, write "3" "32" " " "5" "3" "*" "" - ", remember, each paper is written on the paper. Only write one, or write only one calculation symbol, put them on the above order. Ok, now I listen carefully, I will pick up a small circular paper according to the order, and do the following rules repeatedly:
1. If you are holding a number, don't say, put it directly into the cylinder;
2. If you are holding an arithmetic symbol, don't put it in. First remove the two numbers from the cylinder (of course, first take the most up, the cylinder is fine), then the two numbers are determined by the calculation symbol, and write the result on a new sheet of paper, then Put into the tube. For example, you have " ", you have to take out "32" and "3", let them add, "35", write "35" on a new sheet of paper (now "34" and " 12 "You can throw it away) and put this new sheet of paper into the cylinder.
When there is only one number in the cylinder, you can stop, I guess this number is 20, yes, this is the value of this expression!
What we just did, in fact, a "stack", the stack is a data structure, with a nature - LIFO - Last Input First Output, you have already appreciated, just like a plate, You can only take it from the top, and you can only put it on the top. The movement of the put it is called "into the stack", and it is called "pop-up". In the future, you can imagine the stack into a plate, or the small cylinders and small sheets mentioned above, the stack is so simple!
The reverse polish expression seems to be more cumbersome, actually useful in the computer. The computer can not know the addition and subtraction first after the first multiplication, in addition to the inner brackets, it will turn your input to the reverse Polan expression, which can constantly perform the above two rules until the results are calculated to tell you. Now you can try it on your computer and try to make a program, let it read into a reverse polish expression, then let it calculate!
Did you make it? If you answer "Yes", you can follow another problem, for sequences of 7 elements 1 2 3 4 5 6 7, after the treatment of a stack (such as 1 2 3, 3 2, 4) , 4th pop-up ... so, etc.), how many different arrangements can you get? Can you get 4 3 5 2 1 7 6? Can you get 3 2 4 5 7 1 6?
