;Task:
Create a program that takes an [[wp:Reverse Polish notation|RPN]] representation of an expression formatted as a space separated sequence of tokens and generates the equivalent expression in [[wp:Infix notation|infix notation]].

* Assume an input of a correct, space separated, string of tokens
* Generate a space separated output string representing the same expression in infix notation
* Show how the major datastructure of your algorithm changes with each new token parsed.
* Test with the following input RPN strings then print and display the output here.
:{| class="wikitable"
! RPN input !! sample output
|- || align="center"
| <code>3 4 2 * 1 5 - 2 3 ^ ^ / +</code>|| <code>3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3</code>
|- || align="center"
| <code>1 2 + 3 4 + ^ 5 6 + ^</code>|| <code>( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )</code>
|}

* Operator precedence and operator associativity is given in this table:
:{| class="wikitable"

! operator !! [[wp:Order_of_operations|precedence]] !! [[wp:Operator_associativity|associativity]] !! operation
|- || align="center"
|                   <big><big> ^ </big></big>  ||  4  ||  right  ||  exponentiation
|- || align="center"
|                   <big><big> * </big></big>  ||  3  ||   left  ||  multiplication
|- || align="center"
|                   <big><big> / </big></big>  ||  3  ||   left  ||     division
|- || align="center"
|                   <big><big> + </big></big>  ||  2  ||   left  ||     addition
|- || align="center"
|                   <big><big> - </big></big>  ||  2  ||   left  ||   subtraction
|}


;See also:
* &nbsp; [[Parsing/Shunting-yard algorithm]] &nbsp; for a method of generating an RPN from an infix expression.
* &nbsp; [[Parsing/RPN calculator algorithm]] &nbsp; for a method of calculating a final value from this output RPN expression.
* &nbsp; [http://www.rubyquiz.com/quiz148.html Postfix to infix] &nbsp; from the RubyQuiz site.
<br><br>