38 lines
1.9 KiB
Text
38 lines
1.9 KiB
Text
;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:
|
|
* [[Parsing/Shunting-yard algorithm]] for a method of generating an RPN from an infix expression.
|
|
* [[Parsing/RPN calculator algorithm]] for a method of calculating a final value from this output RPN expression.
|
|
* [http://www.rubyquiz.com/quiz148.html Postfix to infix] from the RubyQuiz site.
|
|
<br><br>
|
|
|