Infix-to-postfix conversion can be performed in a single left-to-right pass using a stack, resting on the observation that the relative order of operands is preserved between the two notations while only the order and position of operators changes, with postfix listing operators in the order they must be executed. Operands are appended to the output immediately, since nothing can precede them; an operator cannot be emitted until its right operand has been fully emitted, so it is held on a stack, and encountering a lower-precedence operator (or the end of the expression) marks the boundary of a held operator's right operand and licenses popping it to the output. Parentheses extend the rule by delimiting a self-contained subexpression: an opening parenthesis is pushed and acts as a barrier that popping must never cross, and a closing parenthesis pops operators until that barrier is reached and then discards it. This belongs to the data structures and algorithms subfield of computer science, specifically stack applications in expression parsing.
Infix-to-postfix conversion can be performed in a single left-to-right pass using a stack, resting on the observation that the relative order of operands is preserved between the two notations while …