listsstacksand queues infix to postfix conversion not only can stack be used to evaluate postfix expressionbut we can also use stack to convert an expression in standard form (otherwise known as infixinto postfix we will concentrate on small version of the general problem by allowing only the operators +*()and insisting on the usual precedence rules we will further assume that the expression is legal suppose we want to convert the infix expression into postfix correct answer is when an operand is readit is immediately placed onto the output operators are not immediately outputso they must be saved somewhere the correct thing to do is to place operators that have been seenbut not placed on the outputonto the stack we will also stack left parentheses when they are encountered we start with an initially empty stack if we see right parenthesisthen we pop the stackwriting symbols until we encounter (correspondingleft parenthesiswhich is popped but not output if we see any other symbol (+*()then we pop entries from the stack until we find an entry of lower priority one exception is that we never remove from the stack except when processing for the purposes of this operationhas lowest priority and highest when the popping is donewe push the operator onto the stack finallyif we read the end of inputwe pop the stack until it is emptywriting symbols onto the output the idea of this algorithm is that when an operator is seenit is placed on the stack the stack represents pending operators howeversome of the operators on the stack that have high precedence are now known to be completed and should be poppedas they will no longer be pending thus prior to placing the operator on the stackoperators that are on the stackand which are to be completed prior to the current operatorare popped this is illustrated in the following tableexpression stack when third operator is processed action * - + is completedis pushed / + * nothing is completedis pushed - * / is completedis pushed - * + and are completedis pushed parentheses simply add an additional complication we can view left parenthesis as high-precedence operator when it is an input symbol (so that pending operators remain pendingand low-precedence operator when it is on the stack (so that it is not accidentally removed by an operatorright parentheses are treated as the special case to see how this algorithm performswe will convert the long infix expression above into its postfix form firstthe symbol is readso it is passed through to the output