Most calculators use infix notation, while some use Reverse Polish Notation (RPN, also known as postfix). RPN calculators, most famously those made by Hewlett-Packard, have never been particularly popular, except as niche products for engineers, statisticians, and such. One of the benefits of RPN for calculators is that they require fewer keystrokes to enter complicated expressions. We would like to explore how big of a difference that can be.
As an example, the math expression 2 * (13 + 2) / 7 requires 11 keystrokes on an infix calculator — one for each digit, operator, and parenthesis, plus one (the "=" key) to signal the end of the last number. On a RPN calculator, we instead enter 13 2 + 2 * 7 /, which requires 9 keystrokes — one for each digit and operator, and one (the "Enter" key) to separate the entry of the otherwise adjacent numbers 13 and 2.
As another example, 2 * (1 + 3) requires 7 keystrokes on an infix calculator — one for each digit, operator, and parenthesis. Here, the "=" key is unnecesary, as the calculator evaluates the multiplication once the parenthesis is entered. On an RPN, the equivalent 1 3 + 2 * requires 6 keystrokes — one for each digit, operator, and use of "Enter".
To describe how RPN's advantage grows for larger expressions, we have to think in terms of patterns. For example, the infix expression pattern 1 + 2 + 3 + … + n corresponds to the RPN expression pattern 1 2 + 3 + … n +. The exact number of keystrokes for each is hard to describe, since the number of digits grows logarithmically. More interestingly, however, the difference in keystrokes is 0 — they each have the same number of digits and operators, and the infix requires no parentheses and one "=", while the RPN requires one "Enter".
Give an infix expression pattern, and the corresponding RPN expression pattern, that has a maximal difference in required keystrokes.
Having lots of unnecessary parentheses would be silly and would make this comparison uninteresting. So, ignore infix expressions that have parentheses that are unnecessary, given the standard operator precedence.