Number of characters in Postfix notation when number in Infix notation is known

Question

I am converting expressions with only function calls and integers from Infix notation to Postfix notation (only letters,digits,commas,brackets and no spaces).

For example, add(add(1,2),add(3,4)) to 1 2 add 3 4 add add.
Input expression is 22 characters long, output is 19, by 3 shorter.

sqrt(add(5,11)) to 5 11 add sqrt.
Input expression is 15 characters long, output is 13, by 2 shorter.

Will be Postfix notation always shorter by amount of characters equal to amount of functions?

Answer 1

Does infix require more syntax? That is an interesting question. However, the examples you give are prefix notation, rather than infix. Short answer though: Yes, infix can require more syntax in some situations (e.g. to disambiguate operator precedence).

I believe that counting necessary tokens may be more meaningful than counting characters. Let's see what happens.

In your prefix examples, by moving the opening parens to the left of the operators and replacing the commas with spaces, we have Lisp: (+ (+ 1 2) (+ 3 4)) and (sqrt (+ 5 11)).

We can then simply reverse everything and have a postfix notation (but no reduction in token or character count): ((1 2 +) (3 4 +) +) and ((5 11 +) sqrt).

Given that the arity is fixed (+ is binary, sqrt is unary), we can unambiguously remove the parens and have Forth: 1 2 + 3 4 + + and 5 11 + sqrt. In fact, with fixed arity operators the parens were not needed in any case. They never were meaningful, necessary tokens to begin with.

But does infix require more syntax? Well, because of operator precedence, this 2 × (3 + 4) is not the same as 2 × 3 + 4. The parens are necessary to indicate precedence in infix notation. Whatever syntax you choose, you will have to have something added to disambiguate this. However in postfix (or prefix) these two expressions can be represented unambiguously with equal token count (and always fewer than in infix): 2 3 × 4 + and 2 3 4 + × or 3 4 + 2 ×.

I hope that answers what you were getting at!