First, you've compared expressions in reverse Polish notation and an infix notation here.
Second, under some interpretations a1 a2∧a3∧b1 b2∧b3∧c1 c2∧c3∧∨∨ is more precise than (a1∧a2∧a3)∨(b1∧b2∧b3)∨(c1∧c2∧c3), since the order of parsing all strings in (a1∧a2∧a3)∨(b1∧b2∧b3)∨(c1∧c2∧c3) is not clear (do we parse a1∧a2 first or a2∧a3?). At the same time that parsing order isn't relevant to say computing (a1∧a2∧a3)∨(b1∧b2∧b3)∨(c1∧c2∧c3) since both (S, $\land$) and (S, $\lor$) are commutative semigroups.
Third, in Reverse Polish notation for any expression where the main function is binary, we have a left argument and a right argument. Let's look at an algorithm to determine whether or not an expression is in Reverse Polish notation.
- For any n-ary function or predicate symbol assign (n-1) to that symbol.
- Assign -1 to all variables.
Thus, $\lor$ gets assigned "1", and $\lnot$ gets assigned 0.
Now start at the end of the expression and assume we have 0 before we start counting. An expression is a well-formed expression in Reverse Polish notation if and only if it is a variable, or starts with a natural number on the right and ends with -1 on the left and only gets to -1 at the last position on the left.
Now if we have a binary function as the symbol on the far right of some well-formed expression, then we'll have a left expression and a right expression. It turns out that the right expression has a "0" corresponding to the symbol in the leftmost position, and the left expression has a "-1" corresponding to the symbol in the leftmost position. Determine the right expression first, and then the left expression second For example, let A be binary, K binary, and N unary... the assignments above for xyAzNuNNKA give us the following:
x y A z N u N N K A
| | | | | | | | | |
-1 0 1 0 1 1 2 2 2 1
Thus, zNuNNK is the right expression of the main "A" expression, and xyA is the left expression of the main "A" expression. Thus, since xyKN=xNyNA and xyAN=xNyNK, if we wanted to find say how to figure out where the negation in
xyzKAuvKwzyKAAKN goes we just figure out what the left and right expressions of xyzKAuvKwzyKAAK are. Then we put an "N" after each of those expressions, and concatenate them accordingly (corresponding to how the non-negated left expression and right expression were concatenated) and switch the main function to its dual.
For an expression with just binary functions like ((a1∧(a2∧a3))∨(((b1∧b2)∧b3)∨((c1∧c2)∧c3))), we look at how it gets constructed from its sub-expressions. At the first level we have (a2∧a3), (b1∧b2), and (c1∧c2). At the second level we have (a1∧(a2∧a3), ((b1∧b2)∧b3), and ((c1∧c2)∧c3). At the third level we have (((b1∧b2)∧b3)∨((c1∧c2)∧c3)). And at the fourth level we have ((a1∧(a2∧a3))∨(((b1∧b2)∧b3)∨((c1∧c2)∧c3))). So, we can translate each expression at level 1 from (x?y) to xy? where "?" is some binary function. Then we translate all level 2 expressions, and so on, until no more levels are left. But, let's call $\land$, K when in Reverse Polish notation, and $\lor$, A so we don't get confused when translating. With this example that would mean we start with
((a1∧(a2∧a3))∨(((b1∧b2)∧b3)∨((c1∧c2)∧c3))) which becomes
after transforming all level 1 expressions. Now transforming the next level we obtain
Transforming the next level we obtain
And thus finally
Parsing the expression into a tree should help to determine the level of a sub-expression.