In Polish/Prefix notation of binary operations, are all expression unambiguous w.r.t. which operator is applied first?

98 Views Asked by At

Take binary operator ~ and a chain like a ~ b ~ c. It is ambiguous as it can mean either of:

  1. (a ~ b) ~ c
  2. a ~ (b ~ c)

That is to say, expressed in infix notation, the expression is ambiguous when the parentheses are omitted.

Written in Polish/prefix notation however, there is no ambiguity even if we omit the parentheses:

  1. (a ~ b) ~ c becomes ~(~(a b) c) which without parentheses is ~~abc
  2. a ~ (b ~ c) becomes ~(a ~(b c)) which without parentheses is ~a~bc

Are there scenarios where Polish/prefix notation can be ambiguous?

I went over all permutations of ~~abc trying to find an ambiguous Polish/prefix notation expression, but none were ambiguous:

ab~c~  # invalid, string must start with `~`
abc~~  # invalid, string must start with `~`
~a~bc  # This is #2 above.
a~b~c  # invalid, string must start with `~`
ab~~c  # invalid, string must start with `~`
~~abc  # This is #1 above.
~abc~  # invalid, string cannot end with `~`
a~bc~  # invalid, string must start with `~`
~ab~c  # invalid, the second `~` only has one operand
a~~bc  # invalid, string must start with `~`

I have tested only the bare minimum (a chain of two applications of the binary operation); I could try three, four, etc, but probably someone here knows the answer.