How can I estimate the stack space needed to turn an infix expression into a postfix expression

Question

There is the famous shunting-yard algorithm that can be used to turn an infix expression (such as 1 + 2 * 3) into a postfix expression (such as 1 2 2 * +). The shunting-yard algorithm needs a stack to store elements that are about to be moved.

Is it possible to pre-estimate the length of the stack needed to perform a translation of a specific input into its postfix form in linear time and constant memory?

Answer 1

Sure. The shunting-yard algorithm only pushes operators (including parentheses) onto the stack, so a first-order approximation is the number of operators in the expression. With a little more intelligence, you could scan the expression and look for associativity and grouping. But by the time you were done, you would probably have written a stack-based algorithm for determining the best estimate of the stack size required for the expression, and would have doubled your execution cost.

Answer 2

On the old HP-45 calculator we always scanned for the most deeply nested parentheses, and started evaluation there. That should be a quick O(N) algorithm for N tokens in the input.

In practice, it was challenging to create an expression that blew the 4-high stack of the HP-45.