Printable View
Hi to all. i'm new in this forum, it's cool..
i have to solve an algorithm
i have two matrix, one composed of operations and the other composed of numbers.
es: first matrix: |1|2|3|4|5|
second matrix: |+|+|+|+|
notice that there are n numbers and (n-1) operations.
i have to combine them to generate all the valid rpn(Reverse Polish notation) expressions..
hope i explaned it correctly..
thank you very much!
Hi,
First of all: my solution is far away from efficient, but it should work :-)
I think it is much easier to code it, than to predict, how many upn-results you will get by a given number n of numbers and n-1 of operators.
First you derive a list all possible permutations of the numbers, then a list of all permutations of the operators.
Then you derive a list of all possibilities to put operators and numbers together. This is the tricky part. You can by representing every number as a 1 and every operator as a 0 , describe every possible order by a permutation of n 1s and n-1 0s. So we have 2n-1 over n possible orders. But not all of them are allowed. Before the i-th operator there have to be i+1 numbers in a valid order. In the simplest algorithm just sort out all not valid orders and you have with the both upper permutations of the numbers and operators all possible upn-orders.
If you can imagine every permutation of 1-s and 0s from above as a walk trough a matrix with n rows and n-1 columns starting with the top left corner and each step only can go down or to the right, you have a bijection from the walks to the permutations. The vaild paths always stay in the top right corner, so you have transformed the problem of counting the valid permutations to counting the valid paths in a triangle. Maybe this does not seem much easier, but I remember very foggy a test, where we had to derive just this number of paths trough such a triangle. So it should be possible, maybe easy for somebody with a combinatorics background.
Greetings,
Marco
See the postfix algorithm: http://en.wikipedia.org/wiki/Reverse_Polish_notation