Parsing/RPN to infix conversion: Difference between revisions
(Go solution) |
(→{{header|TXR}}: Use each operator instead of for loop. Colorized.) |
||
Line 744: | Line 744: | ||
=={{header|TXR}}== |
=={{header|TXR}}== |
||
<div class="text highlighted_source" style="border:1pt dashed black;white-space:pre;overflow:auto;background:white;color:black;padding:1em;border:1px dashed #2f6fab;color:black;background-color:#f9f9f9;line-height:1.3em"><code><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">next</span> :<span style="color: #007080; background-color: #f0f0f0">args</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">define</span> <span style="color: #007080; background-color: #f0f0f0">space</span><span style="color: #912f11; background-color: #f0f0f0">)</span><span style="color: #077807; background-color: #f0f0f0">@/ */</span><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">end</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">define</span> <span style="color: #007080; background-color: #f0f0f0">number</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">nod</span><span style="color: #912f11; background-color: #f0f0f0">))</span><span style="color: #786000; background-color: #f0f0f0">@\</span><br> <span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">local</span> <span style="color: #007080; background-color: #f0f0f0">n</span><span style="color: #912f11; background-color: #f0f0f0">)@(</span><span style="color: #007080; background-color: #f0f0f0">space</span><span style="color: #912f11; background-color: #f0f0f0">)@{</span><span style="color: #007080; background-color: #f0f0f0">n</span><span style="color: #007080; background-color: #f0f0f0"> </span><span style="color: #077807; background-color: #f0f0f0">/[0-9]+/</span><span style="color: #912f11; background-color: #f0f0f0">}@(</span><span style="color: #007080; background-color: #f0f0f0">space</span><span style="color: #912f11; background-color: #f0f0f0">)</span><span style="color: #786000; background-color: #f0f0f0">@\</span><br> <span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">bind</span> <span style="color: #007080; background-color: #f0f0f0">nod</span> <span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">int-str</span> <span style="color: #007080; background-color: #f0f0f0">n</span> <span style="color: #077807; background-color: #f0f0f0">10</span><span style="color: #912f11; background-color: #f0f0f0">))</span><span style="color: #786000; background-color: #f0f0f0">@\</span><br><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">end</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">define</span> <span style="color: #007080; background-color: #f0f0f0">op</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">nod</span><span style="color: #912f11; background-color: #f0f0f0">))</span><span style="color: #786000; background-color: #f0f0f0">@\</span><br> <span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">local</span> <span style="color: #007080; background-color: #f0f0f0">op</span><span style="color: #912f11; background-color: #f0f0f0">)</span><span style="color: #786000; background-color: #f0f0f0">@\</span><br> <span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #007080; background-color: #f0f0f0">space</span><span style="color: #912f11; background-color: #f0f0f0">)</span><span style="color: #786000; background-color: #f0f0f0">@\</span><br> <span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">cases</span><span style="color: #912f11; background-color: #f0f0f0">)</span><span style="color: #786000; background-color: #f0f0f0">@\</span><br> <span style="color: #912f11; background-color: #f0f0f0">@{</span><span style="color: #007080; background-color: #f0f0f0">op</span><span style="color: #007080; background-color: #f0f0f0"> </span><span style="color: #077807; background-color: #f0f0f0">/[+\-*^]/</span><span style="color: #912f11; background-color: #f0f0f0">}</span><span style="color: #786000; background-color: #f0f0f0">@\</span><br> <span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">bind</span> <span style="color: #007080; background-color: #f0f0f0">nod</span> <span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">intern</span> <span style="color: #007080; background-color: #f0f0f0">op</span> <span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">*user-package*</span><span style="color: #912f11; background-color: #f0f0f0">))</span><span style="color: #786000; background-color: #f0f0f0">@\</span><br> <span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">or</span><span style="color: #912f11; background-color: #f0f0f0">)</span><span style="color: #786000; background-color: #f0f0f0">@\</span><br> /<span style="color: #786000; background-color: #f0f0f0">@\</span><br> <span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">bind</span> <span style="color: #007080; background-color: #f0f0f0">nod</span> <span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">intern</span> <span style="color: #077807; background-color: #f0f0f0">"\\"</span> <span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">*user-package*</span><span style="color: #912f11; background-color: #f0f0f0">))</span><span style="color: #786000; background-color: #f0f0f0">@\</span><br> <span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">end</span><span style="color: #912f11; background-color: #f0f0f0">)</span><span style="color: #786000; background-color: #f0f0f0">@\</span><br> <span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #007080; background-color: #f0f0f0">space</span><span style="color: #912f11; background-color: #f0f0f0">)</span><span style="color: #786000; background-color: #f0f0f0">@\</span><br><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">end</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">define</span> <span style="color: #007080; background-color: #f0f0f0">term</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">nod</span><span style="color: #912f11; background-color: #f0f0f0">))@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">cases</span><span style="color: #912f11; background-color: #f0f0f0">)@(</span><span style="color: #007080; background-color: #f0f0f0">number</span> <span style="color: #007080; background-color: #f0f0f0">nod</span><span style="color: #912f11; background-color: #f0f0f0">)@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">or</span><span style="color: #912f11; background-color: #f0f0f0">)@(</span><span style="color: #007080; background-color: #f0f0f0">op</span> <span style="color: #007080; background-color: #f0f0f0">nod</span><span style="color: #912f11; background-color: #f0f0f0">)@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">end</span><span style="color: #912f11; background-color: #f0f0f0">)@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">end</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">define</span> <span style="color: #007080; background-color: #f0f0f0">rpn</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">list</span><span style="color: #912f11; background-color: #f0f0f0">))@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">coll</span> :<span style="color: #007080; background-color: #f0f0f0">gap</span> <span style="color: #077807; background-color: #f0f0f0">0</span> :<span style="color: #007080; background-color: #f0f0f0">vars</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">list</span><span style="color: #912f11; background-color: #f0f0f0">))@(</span><span style="color: #007080; background-color: #f0f0f0">term</span> <span style="color: #007080; background-color: #f0f0f0">list</span><span style="color: #912f11; background-color: #f0f0f0">)@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">end</span><span style="color: #912f11; background-color: #f0f0f0">)@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">end</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">freeform</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #007080; background-color: #f0f0f0">rpn</span> <span style="color: #007080; background-color: #f0f0f0">rpn</span><span style="color: #912f11; background-color: #f0f0f0">)</span><span style="color: #007080; background-color: #f0f0f0">@junk</span><span style="color: #077807; background-color: #f0f0f0">@\n</span><br><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">output</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br>rpn tokens: [<span style="color: #007080; background-color: #f0f0f0">@rpn</span>]<br>trailing junk: [<span style="color: #007080; background-color: #f0f0f0">@junk</span>]<br><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">end</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">do</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">defvar</span> <span style="color: #007080; background-color: #f0f0f0">*prec*</span> <span style="color: #077807; background-color: #f0f0f0">'</span><span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #007080; background-color: #f0f0f0">^</span> . <span style="color: #077807; background-color: #f0f0f0">4</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">*</span> . <span style="color: #077807; background-color: #f0f0f0">3</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">\</span> . <span style="color: #077807; background-color: #f0f0f0">3</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">+</span> . <span style="color: #077807; background-color: #f0f0f0">2</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">-</span> . <span style="color: #077807; background-color: #f0f0f0">2</span><span style="color: #912f11; background-color: #f0f0f0">)))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">defvar</span> <span style="color: #007080; background-color: #f0f0f0">*asso*</span> <span style="color: #077807; background-color: #f0f0f0">'</span><span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #007080; background-color: #f0f0f0">^</span> . :<span style="color: #007080; background-color: #f0f0f0">right</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">*</span> . :<span style="color: #007080; background-color: #f0f0f0">left</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">\</span> . :<span style="color: #007080; background-color: #f0f0f0">left</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">+</span> . :<span style="color: #007080; background-color: #f0f0f0">left</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">-</span> . :<span style="color: #007080; background-color: #f0f0f0">left</span><span style="color: #912f11; background-color: #f0f0f0">)))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">defun</span> <span style="color: #007080; background-color: #f0f0f0">rpn-to-lisp</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">rpn</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">let</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">stack</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">each</span> <span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #007080; background-color: #f0f0f0">term</span> <span style="color: #007080; background-color: #f0f0f0">rpn</span><span style="color: #912f11; background-color: #f0f0f0">))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">format</span> <span style="color: #007080; background-color: #f0f0f0">t</span> <span style="color: #077807; background-color: #f0f0f0">"rpn term: ~s\n"</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">if</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">symbolp</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">let</span> <span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #007080; background-color: #f0f0f0">right</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">pop</span> <span style="color: #007080; background-color: #f0f0f0">stack</span><span style="color: #912f11; background-color: #f0f0f0">))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">left</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">pop</span> <span style="color: #007080; background-color: #f0f0f0">stack</span><span style="color: #912f11; background-color: #f0f0f0">)))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">push</span> <span style="color: #077807; background-color: #f0f0f0">'</span><span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #077807; background-color: #f0f0f0">,</span><span style="color: #007080; background-color: #f0f0f0">term</span> <span style="color: #077807; background-color: #f0f0f0">,</span><span style="color: #007080; background-color: #f0f0f0">left</span> <span style="color: #077807; background-color: #f0f0f0">,</span><span style="color: #007080; background-color: #f0f0f0">right</span><span style="color: #912f11; background-color: #f0f0f0">)</span> <span style="color: #007080; background-color: #f0f0f0">stack</span><span style="color: #912f11; background-color: #f0f0f0">))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">push</span> <span style="color: #007080; background-color: #f0f0f0">term</span> <span style="color: #007080; background-color: #f0f0f0">stack</span><span style="color: #912f11; background-color: #f0f0f0">))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">format</span> <span style="color: #007080; background-color: #f0f0f0">t</span> <span style="color: #077807; background-color: #f0f0f0">"stack: ~s\n"</span> <span style="color: #007080; background-color: #f0f0f0">stack</span><span style="color: #912f11; background-color: #f0f0f0">))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">if</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">rest</span> <span style="color: #007080; background-color: #f0f0f0">stack</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">return-from</span> <span style="color: #007080; background-color: #f0f0f0">error</span> <span style="color: #077807; background-color: #f0f0f0">"*excess stack elements*"</span><span style="color: #912f11; background-color: #f0f0f0">))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">pop</span> <span style="color: #007080; background-color: #f0f0f0">stack</span><span style="color: #912f11; background-color: #f0f0f0">)))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">defun</span> <span style="color: #007080; background-color: #f0f0f0">prec</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">cond</span><br> <span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">null</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)</span> <span style="color: #077807; background-color: #f0f0f0">99</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">symbolp</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">cdr</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">assoc</span> <span style="color: #007080; background-color: #f0f0f0">term</span> <span style="color: #007080; background-color: #f0f0f0">*prec*</span><span style="color: #912f11; background-color: #f0f0f0">)))</span><br> <span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">atom</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)</span> <span style="color: #077807; background-color: #f0f0f0">99</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">t</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">prec</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">car</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)))))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">defun</span> <span style="color: #007080; background-color: #f0f0f0">asso</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">cond</span><br> <span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">null</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)</span> :<span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">none</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">symbolp</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">cdr</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">assoc</span> <span style="color: #007080; background-color: #f0f0f0">term</span> <span style="color: #007080; background-color: #f0f0f0">*asso*</span><span style="color: #912f11; background-color: #f0f0f0">)))</span><br> <span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">atom</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)</span> :<span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">none</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">t</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">asso</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">car</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)))))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">defun</span> <span style="color: #007080; background-color: #f0f0f0">inf-op</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">op</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">if</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">eq</span> <span style="color: #007080; background-color: #f0f0f0">op</span> <span style="color: #077807; background-color: #f0f0f0">'</span><span style="color: #007080; background-color: #f0f0f0">\</span><span style="color: #912f11; background-color: #f0f0f0">)</span> <span style="color: #077807; background-color: #f0f0f0">"/"</span> <span style="color: #007080; background-color: #f0f0f0">op</span><span style="color: #912f11; background-color: #f0f0f0">))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">defun</span> <span style="color: #007080; background-color: #f0f0f0">inf-term</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">op</span> <span style="color: #007080; background-color: #f0f0f0">term</span> <span style="color: #007080; background-color: #f0f0f0">left-or-right</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">let</span> <span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #007080; background-color: #f0f0f0">pt</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">prec</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">po</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">prec</span> <span style="color: #007080; background-color: #f0f0f0">op</span><span style="color: #912f11; background-color: #f0f0f0">))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">at</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">asso</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">ao</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">asso</span> <span style="color: #007080; background-color: #f0f0f0">op</span><span style="color: #912f11; background-color: #f0f0f0">)))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">cond</span><br> <span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold"><</span> <span style="color: #007080; background-color: #f0f0f0">pt</span> <span style="color: #007080; background-color: #f0f0f0">po</span><span style="color: #912f11; background-color: #f0f0f0">)</span> <span style="color: #077807; background-color: #f0f0f0">`(</span><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #007080; background-color: #f0f0f0">lisp-to-infix</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)</span><span style="color: #077807; background-color: #f0f0f0">)`</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">></span> <span style="color: #007080; background-color: #f0f0f0">pt</span> <span style="color: #007080; background-color: #f0f0f0">po</span><span style="color: #912f11; background-color: #f0f0f0">)</span> <span style="color: #077807; background-color: #f0f0f0">`</span><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #007080; background-color: #f0f0f0">lisp-to-infix</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)</span><span style="color: #077807; background-color: #f0f0f0">`</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">and</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">eq</span> <span style="color: #007080; background-color: #f0f0f0">at</span> <span style="color: #007080; background-color: #f0f0f0">ao</span><span style="color: #912f11; background-color: #f0f0f0">)</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">eq</span> <span style="color: #007080; background-color: #f0f0f0">left-or-right</span> <span style="color: #007080; background-color: #f0f0f0">ao</span><span style="color: #912f11; background-color: #f0f0f0">))</span> <span style="color: #077807; background-color: #f0f0f0">`</span><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #007080; background-color: #f0f0f0">lisp-to-infix</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)</span><span style="color: #077807; background-color: #f0f0f0">`</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">t</span> <span style="color: #077807; background-color: #f0f0f0">`(</span><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #007080; background-color: #f0f0f0">lisp-to-infix</span> <span style="color: #007080; background-color: #f0f0f0">term</span><span style="color: #912f11; background-color: #f0f0f0">)</span><span style="color: #077807; background-color: #f0f0f0">)`</span><span style="color: #912f11; background-color: #f0f0f0">))))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">defun</span> <span style="color: #007080; background-color: #f0f0f0">lisp-to-infix</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">lisp</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">if</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">atom</span> <span style="color: #007080; background-color: #f0f0f0">lisp</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">if</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">null</span> <span style="color: #007080; background-color: #f0f0f0">lisp</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">return-from</span> <span style="color: #007080; background-color: #f0f0f0">error</span> <span style="color: #077807; background-color: #f0f0f0">"*stack underflow*"</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">if</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">eq</span> <span style="color: #007080; background-color: #f0f0f0">lisp</span> <span style="color: #077807; background-color: #f0f0f0">'</span><span style="color: #007080; background-color: #f0f0f0">\</span><span style="color: #912f11; background-color: #f0f0f0">)</span> <span style="color: #077807; background-color: #f0f0f0">"/"</span> <span style="color: #077807; background-color: #f0f0f0">`</span><span style="color: #007080; background-color: #f0f0f0">@lisp</span><span style="color: #077807; background-color: #f0f0f0">`</span><span style="color: #912f11; background-color: #f0f0f0">))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">let</span> <span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #007080; background-color: #f0f0f0">op</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">first</span> <span style="color: #007080; background-color: #f0f0f0">lisp</span><span style="color: #912f11; background-color: #f0f0f0">))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">left</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">second</span> <span style="color: #007080; background-color: #f0f0f0">lisp</span><span style="color: #912f11; background-color: #f0f0f0">))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">right</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">third</span> <span style="color: #007080; background-color: #f0f0f0">lisp</span><span style="color: #912f11; background-color: #f0f0f0">)))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">let</span> <span style="color: #912f11; background-color: #f0f0f0">((</span><span style="color: #007080; background-color: #f0f0f0">left-inf</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">inf-term</span> <span style="color: #007080; background-color: #f0f0f0">op</span> <span style="color: #007080; background-color: #f0f0f0">left</span> :<span style="color: #007080; background-color: #f0f0f0">left</span><span style="color: #912f11; background-color: #f0f0f0">))</span><br> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">right-inf</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">inf-term</span> <span style="color: #007080; background-color: #f0f0f0">op</span> <span style="color: #007080; background-color: #f0f0f0">right</span> :<span style="color: #007080; background-color: #f0f0f0">right</span><span style="color: #912f11; background-color: #f0f0f0">)))</span><br> <span style="color: #077807; background-color: #f0f0f0">`</span><span style="color: #912f11; background-color: #f0f0f0">@{</span><span style="color: #007080; background-color: #f0f0f0">left-inf</span><span style="color: #912f11; background-color: #f0f0f0">}</span><span style="color: #077807; background-color: #f0f0f0"> </span><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #007080; background-color: #f0f0f0">inf-op</span> <span style="color: #007080; background-color: #f0f0f0">op</span><span style="color: #912f11; background-color: #f0f0f0">)</span><span style="color: #077807; background-color: #f0f0f0"> </span><span style="color: #912f11; background-color: #f0f0f0">@{</span><span style="color: #007080; background-color: #f0f0f0">right-inf</span><span style="color: #912f11; background-color: #f0f0f0">}</span><span style="color: #077807; background-color: #f0f0f0">`</span><span style="color: #912f11; background-color: #f0f0f0">)))))</span><br><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">bind</span> <span style="color: #007080; background-color: #f0f0f0">infix</span> <span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">block</span> <span style="color: #007080; background-color: #f0f0f0">error</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">lisp-to-infix</span> <span style="color: #912f11; background-color: #f0f0f0">(</span><span style="color: #007080; background-color: #f0f0f0">rpn-to-lisp</span> <span style="color: #007080; background-color: #f0f0f0">rpn</span><span style="color: #912f11; background-color: #f0f0f0">))))</span><br><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">output</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br>infix: <span style="color: #007080; background-color: #f0f0f0">@infix</span><br><span style="color: #912f11; background-color: #f0f0f0">@(</span><span style="color: #1f3f81; background-color: #f0f0f0; font-weight: bold">end</span><span style="color: #912f11; background-color: #f0f0f0">)</span><br></code></div> |
|||
<lang txr>@(next :args) |
|||
@(define space)@/ */@(end) |
|||
@(define number (nod))@\ |
|||
@(local n)@(space)@{n /[0-9]+/}@(space)@\ |
|||
@(bind nod @(int-str n 10))@\ |
|||
@(end) |
|||
@(define op (nod))@\ |
|||
@(local op)@\ |
|||
@(space)@\ |
|||
@(cases)@\ |
|||
@{op /[+\-*^]/}@\ |
|||
@(bind nod @(intern op *user-package*))@\ |
|||
@(or)@\ |
|||
/@\ |
|||
@(bind nod @(intern "\\" *user-package*))@\ |
|||
@(end)@\ |
|||
@(space)@\ |
|||
@(end) |
|||
@(define term (nod))@(cases)@(number nod)@(or)@(op nod)@(end)@(end) |
|||
@(define rpn (list))@(coll :gap 0 :vars (list))@(term list)@(end)@(end) |
|||
@(freeform) |
|||
@(rpn rpn)@junk@\n |
|||
@(output) |
|||
rpn tokens: [@(rep)@rpn @(last)@rpn@(end)] |
|||
trailing junk: [@junk] |
|||
@(end) |
|||
@(do (defvar *prec* '((^ . 4) |
|||
(* . 3) |
|||
(\ . 3) |
|||
(+ . 2) |
|||
(- . 2))) |
|||
(defvar *asso* '((^ . :right) |
|||
(* . :left) |
|||
(\ . :left) |
|||
(+ . :left) |
|||
(- . :left))) |
|||
(defun rpn-to-lisp (rpn) |
|||
(let (stack) |
|||
(for ((iter rpn)) |
|||
(iter (if (rest stack) |
|||
(return-from error "*excess stack elements*") |
|||
(first stack))) |
|||
((set iter (cdr iter)) |
|||
(format t "stack: ~s\n" stack)) |
|||
(let ((term (car iter))) |
|||
(format t "rpn term: ~s\n" term) |
|||
(if (symbolp term) |
|||
(let ((right (pop stack)) |
|||
(left (pop stack))) |
|||
(push '(,term ,left ,right) stack)) |
|||
(push term stack)))))) |
|||
(defun prec (term) |
|||
(cond |
|||
((null term) 99) |
|||
((symbolp term) (cdr (assoc term *prec*))) |
|||
((atom term) 99) |
|||
(t (prec (car term))))) |
|||
(defun asso (term) |
|||
(cond |
|||
((null term) :none) |
|||
((symbolp term) (cdr (assoc term *asso*))) |
|||
((atom term) :none) |
|||
(t (asso (car term))))) |
|||
(defun inf-op (op) |
|||
(if (eq op '\) "/" op)) |
|||
(defun inf-term (op term left-or-right) |
|||
(let ((pt (prec term)) |
|||
(po (prec op)) |
|||
(at (asso term)) |
|||
(ao (asso op))) |
|||
(cond |
|||
((< pt po) `(@(lisp-to-infix term))`) |
|||
((> pt po) `@(lisp-to-infix term)`) |
|||
((and (eq at ao) (eq left-or-right ao)) `@(lisp-to-infix term)`) |
|||
(t `(@(lisp-to-infix term))`)))) |
|||
(defun lisp-to-infix (lisp) |
|||
(if (atom lisp) |
|||
(if (null lisp) |
|||
(return-from error "*stack underflow*") |
|||
(if (eq lisp '\) "/" `@lisp`)) |
|||
(let ((op (first lisp)) |
|||
(left (second lisp)) |
|||
(right (third lisp))) |
|||
(let ((left-inf (inf-term op left :left)) |
|||
(right-inf (inf-term op right :right))) |
|||
`@{left-inf} @(inf-op op) @{right-inf}`))))) |
|||
@(bind infix @(block error (lisp-to-infix (rpn-to-lisp rpn)))) |
|||
@(output) |
|||
infix: @infix |
|||
@(end)</lang> |
|||
<pre>$ ./txr rosetta/rpn.txr '3 4 2 * 1 5 - 2 3 ^ ^ / +' |
<pre>$ ./txr rosetta/rpn.txr '3 4 2 * 1 5 - 2 3 ^ ^ / +' |
Revision as of 18:19, 28 January 2012
You are encouraged to solve this task according to the task description, using any language you may know.
Create a program that takes an RPN representation of an expression formatted as a space separated sequence of tokens and generates the equivalent expression in 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.
RPN input sample output 3 4 2 * 1 5 - 2 3 ^ ^ / +
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
1 2 + 3 4 + ^ 5 6 + ^
( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )
- Operator precedence is given in this table:
operator precedence associativity ^ 4 Right * 3 Left / 3 Left + 2 Left - 2 Left
- Note
- '^' means exponentiation.
- 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.
- Postfix to infix from the RubyQuiz site.
AutoHotkey
<lang AHK>expr := "3 4 2 * 1 5 - 2 3 ^ ^ / +"
stack := {push: func("ObjInsert"), pop: func("ObjRemove")} out := "TOKEN`tACTION STACK (comma separated)`r`n" Loop Parse, expr, %A_Space% { token := A_LoopField if token is number stack.push([0, token]) if isOp(token) { b := stack.pop(), a := stack.pop(), p := b.1 > a.1 ? b.1 : a.1 p := Precedence(token) > p ? precedence(token) : p if (a.1 < b.1) and isRight(token) stack.push([p, "( " . a.2 " ) " token " " b.2]) else if (a.1 > b.1) and isLeft(token) stack.push([p, a.2 token " ( " b.2 " ) "]) else stack.push([p, a.2 . " " . token . " " . b.2]) } out .= token "`t" (isOp(token) ? "Push Partial expression " : "Push num" space(16)) disp(stack) "`r`n" } out .= "`r`n The final output infix expression is: '" disp(stack) "'" clipboard := out isOp(t){
return (!!InStr("+-*/^", t) && t)
} IsLeft(o){
return !!InStr("*/+-", o)
} IsRight(o){
return o = "^"
} Precedence(o){
return (InStr("+-/*^", o)+3)//2
} Disp(obj){
for each, val in obj
if val[2] o .= ", " val[2]
return SubStr(o,3)
} Space(n){
return n>0 ? A_Space Space(n-1) : ""
}</lang>
- Output
TOKEN ACTION STACK (comma separated) 3 Push num 3 4 Push num 3, 4 2 Push num 3, 4, 2 * Push Partial expression 3, 4 * 2 1 Push num 3, 4 * 2, 1 5 Push num 3, 4 * 2, 1, 5 - Push Partial expression 3, 4 * 2, 1 - 5 2 Push num 3, 4 * 2, 1 - 5, 2 3 Push num 3, 4 * 2, 1 - 5, 2, 3 ^ Push Partial expression 3, 4 * 2, 1 - 5, 2 ^ 3 ^ Push Partial expression 3, 4 * 2, ( 1 - 5 ) ^ 2 ^ 3 / Push Partial expression 3, 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 + Push Partial expression 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 The final output infix expression is: '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'
Go
No error checking. <lang go>package main
import (
"fmt" "strings"
)
var tests = []string{
"3 4 2 * 1 5 - 2 3 ^ ^ / +", "1 2 + 3 4 + ^ 5 6 + ^",
}
var opa = map[string]struct {
prec int rAssoc bool
}{
"^": {4, true}, "*": {3, false}, "/": {3, false}, "+": {2, false}, "-": {2, false},
}
const nPrec = 9
func main() {
for _, t := range tests { parseRPN(t) }
}
func parseRPN(e string) {
fmt.Println("\npostfix:", e) type sf struct { prec int expr string } var stack []sf for _, tok := range strings.Fields(e) { fmt.Println("token:", tok) if op, isOp := opa[tok]; isOp { rhs := &stack[len(stack)-1] stack = stack[:len(stack)-1] lhs := &stack[len(stack)-1] if lhs.prec < op.prec || (lhs.prec == op.prec && op.rAssoc) { lhs.expr = "(" + lhs.expr + ")" } lhs.expr += " " + tok + " " if rhs.prec < op.prec || (rhs.prec == op.prec && !op.rAssoc) { lhs.expr += "(" + rhs.expr + ")" } else { lhs.expr += rhs.expr } lhs.prec = op.prec } else { stack = append(stack, sf{nPrec, tok}) } for _, f := range stack { fmt.Printf(" %d %q\n", f.prec, f.expr) } } fmt.Println("infix:", stack[0].expr)
}</lang> Output:
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / + token: 3 9 "3" token: 4 9 "3" 9 "4" token: 2 9 "3" 9 "4" 9 "2" token: * 9 "3" 3 "4 * 2" token: 1 9 "3" 3 "4 * 2" 9 "1" token: 5 9 "3" 3 "4 * 2" 9 "1" 9 "5" token: - 9 "3" 3 "4 * 2" 2 "1 - 5" token: 2 9 "3" 3 "4 * 2" 2 "1 - 5" 9 "2" token: 3 9 "3" 3 "4 * 2" 2 "1 - 5" 9 "2" 9 "3" token: ^ 9 "3" 3 "4 * 2" 2 "1 - 5" 4 "2 ^ 3" token: ^ 9 "3" 3 "4 * 2" 4 "(1 - 5) ^ 2 ^ 3" token: / 9 "3" 3 "4 * 2 / (1 - 5) ^ 2 ^ 3" token: + 2 "3 + 4 * 2 / (1 - 5) ^ 2 ^ 3" infix: 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3 postfix: 1 2 + 3 4 + ^ 5 6 + ^ token: 1 9 "1" token: 2 9 "1" 9 "2" token: + 2 "1 + 2" token: 3 2 "1 + 2" 9 "3" token: 4 2 "1 + 2" 9 "3" 9 "4" token: + 2 "1 + 2" 2 "3 + 4" token: ^ 4 "(1 + 2) ^ (3 + 4)" token: 5 4 "(1 + 2) ^ (3 + 4)" 9 "5" token: 6 4 "(1 + 2) ^ (3 + 4)" 9 "5" 9 "6" token: + 4 "(1 + 2) ^ (3 + 4)" 2 "5 + 6" token: ^ 4 "((1 + 2) ^ (3 + 4)) ^ (5 + 6)" infix: ((1 + 2) ^ (3 + 4)) ^ (5 + 6)
Icon and Unicon
<lang Icon>procedure main() every rpn := ![
"3 4 2 * 1 5 - 2 3 ^ ^ / +", # reqd "1 2 + 3 4 + 5 6 + ^ ^", "1 2 + 3 4 + 5 6 + ^ ^", "1 2 + 3 4 + ^ 5 6 + ^" # reqd ] do { printf("\nRPN = %i\n",rpn) printf("infix = %i\n",RPN2Infix(rpn,show)) show := 1 # turn off inner working display }
end
link printf
procedure RPN2Infix(expr,show) #: RPN to Infix conversion static oi initial {
oi := table([9,"'"]) # precedence & associativity every oi[!"+-"] := [2,"l"] # 2L every oi[!"*/"] := [3,"l"] # 3L oi["^"] := [4,"r"] # 4R } show := if /show then printf else 1 # to show inner workings or not stack := [] expr ? until pos(0) do { # Reformat as a tree tab(many(' ')) # consume previous seperator token := tab(upto(' ')|0) # get token if token := numeric(token) then { # ... numeric push(stack,oi[token]|||[token]) show("pushed numeric %i : %s\n",token,list2string(stack)) } else { # ... operator every b|a := pop(stack) # pop & reverse operands pr := oi[token,1] as := oi[token,2] if a[1] < pr | (a[1] = pr & oi[token,2] == "r") then a[3] := sprintf("( %s )",a[3]) if b[1] < pr | (b[1] == pr & oi[token,2] == "l") then b[3] := sprintf("( %s )",b[3]) s := sprintf("%s %s %s",a[3],token,b[3]) push(stack,[pr,as,s]) # stack [prec, assoc, expr] show("applied operator %s : %s\n",token,list2string(stack)) } } if *stack ~= 1 then stop("Parser failure") return stack[1,3]
end
procedure list2string(L) #: format list as a string
s := "[ " every x := !L do s ||:= ( if type(x) == "list" then list2string(x) else x) || " " return s || "]"
end</lang>
printf.icn provides formatting
Output:
RPN = "3 4 2 * 1 5 - 2 3 ^ ^ / +" pushed numeric 3 : [ [ 9 ' 3 ] ] pushed numeric 4 : [ [ 9 ' 4 ] [ 9 ' 3 ] ] pushed numeric 2 : [ [ 9 ' 2 ] [ 9 ' 4 ] [ 9 ' 3 ] ] applied operator * : [ [ 3 l 4 * 2 ] [ 9 ' 3 ] ] pushed numeric 1 : [ [ 9 ' 1 ] [ 3 l 4 * 2 ] [ 9 ' 3 ] ] pushed numeric 5 : [ [ 9 ' 5 ] [ 9 ' 1 ] [ 3 l 4 * 2 ] [ 9 ' 3 ] ] applied operator - : [ [ 2 l 1 - 5 ] [ 3 l 4 * 2 ] [ 9 ' 3 ] ] pushed numeric 2 : [ [ 9 ' 2 ] [ 2 l 1 - 5 ] [ 3 l 4 * 2 ] [ 9 ' 3 ] ] pushed numeric 3 : [ [ 9 ' 3 ] [ 9 ' 2 ] [ 2 l 1 - 5 ] [ 3 l 4 * 2 ] [ 9 ' 3 ] ] applied operator ^ : [ [ 4 r 2 ^ 3 ] [ 2 l 1 - 5 ] [ 3 l 4 * 2 ] [ 9 ' 3 ] ] applied operator ^ : [ [ 4 r ( 1 - 5 ) ^ 2 ^ 3 ] [ 3 l 4 * 2 ] [ 9 ' 3 ] ] applied operator / : [ [ 3 l 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ] [ 9 ' 3 ] ] applied operator + : [ [ 2 l 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ] ] infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" RPN = "1 2 + 3 4 + 5 6 + ^ ^" infix = "( 1 + 2 ) ^ ( 3 + 4 ) ^ ( 5 + 6 )" RPN = "1 2 + 3 4 + 5 6 + ^ ^" infix = "( 1 + 2 ) ^ ( 3 + 4 ) ^ ( 5 + 6 )" RPN = "1 2 + 3 4 + ^ 5 6 + ^" infix = "( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )"
J
Implementation:
<lang j>tokenize=: ' ' <;._1@, deb
ops=: ;:'+ - * / ^' doOp=: plus`minus`times`divide`exponent`push@.(ops&i.) parse=:3 :0
stack=: i.0 2 for_token.tokenize y do.doOp token end. 1{:: ,stack
)
parens=:4 :0
if. y do. '( ',x,' )' else. x end.
)
NB. m: precedence, n: is right associative, y: token op=:2 :0
L=. m - n R=. m - -.n smoutput;'operation: ';y 'Lprec left Rprec right'=. ,_2{.stack expr=. ;(left parens L > Lprec);' ';y,' ';right parens R > Rprec stack=: (_2}.stack),m;expr smoutput stack
)
plus=: 2 op 0 minus=: 2 op 0 times=: 3 op 0 divide=: 3 op 0 exponent=: 4 op 1
push=:3 :0
smoutput;'pushing: ';y stack=: stack,_;y smoutput stack
)</lang>
The stack structure has two elements for each stack entry: expression precedence and expression characters.
Required example:
<lang j> parse '3 4 2 * 1 5 - 2 3 ^ ^ / +' pushing: 3 +-+-+ |_|3| +-+-+ pushing: 4 +-+-+ |_|3| +-+-+ |_|4| +-+-+ pushing: 2 +-+-+ |_|3| +-+-+ |_|4| +-+-+ |_|2| +-+-+ operation: * +-+-----+ |_|3 | +-+-----+ |3|4 * 2| +-+-----+ pushing: 1 +-+-----+ |_|3 | +-+-----+ |3|4 * 2| +-+-----+ |_|1 | +-+-----+ pushing: 5 +-+-----+ |_|3 | +-+-----+ |3|4 * 2| +-+-----+ |_|1 | +-+-----+ |_|5 | +-+-----+ operation: - +-+-----+ |_|3 | +-+-----+ |3|4 * 2| +-+-----+ |2|1 - 5| +-+-----+ pushing: 2 +-+-----+ |_|3 | +-+-----+ |3|4 * 2| +-+-----+ |2|1 - 5| +-+-----+ |_|2 | +-+-----+ pushing: 3 +-+-----+ |_|3 | +-+-----+ |3|4 * 2| +-+-----+ |2|1 - 5| +-+-----+ |_|2 | +-+-----+ |_|3 | +-+-----+ operation: ^ +-+-----+ |_|3 | +-+-----+ |3|4 * 2| +-+-----+ |2|1 - 5| +-+-----+ |4|2 ^ 3| +-+-----+ operation: ^ +-+-----------------+ |_|3 | +-+-----------------+ |3|4 * 2 | +-+-----------------+ |4|( 1 - 5 ) ^ 2 ^ 3| +-+-----------------+ operation: / +-+-------------------------+ |_|3 | +-+-------------------------+ |3|4 * 2 / ( 1 - 5 ) ^ 2 ^ 3| +-+-------------------------+ operation: + +-+-----------------------------+ |2|3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3| +-+-----------------------------+ 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3</lang>
PicoLisp
We maintain a stack of cons pairs, consisting of precedences and partial expressions. Numbers get a "highest" precedence of '9'. <lang PicoLisp>(de leftAssoc (Op)
(member Op '("*" "/" "+" "-")) )
(de precedence (Op)
(case Op ("\^" 4) (("*" "/") 3) (("+" "-") 2) ) )
(de rpnToInfix (Str)
(let Stack NIL (prinl "Token Stack") (for Token (str Str "_") (cond ((num? Token) (push 'Stack (cons 9 @))) # Highest precedence ((not (cdr Stack)) (quit "Stack empty")) (T (let (X (pop 'Stack) P (precedence Token)) (set Stack (cons P (pack (if ((if (leftAssoc Token) < <=) (caar Stack) P) (pack "(" (cdar Stack) ")") (cdar Stack) ) " " Token " " (if ((if (leftAssoc Token) <= <) (car X) P) (pack "(" (cdr X) ")") (cdr X) ) ) ) ) ) ) ) (prin Token) (space 6) (println Stack) ) (prog1 (cdr (pop 'Stack)) (and Stack (quit "Garbage remained on stack")) ) ) )</lang>
Test (note that the top-of-stack is in the left-most position): <lang PicoLisp>: (rpnToInfix "3 4 2 * 1 5 - 2 3 \^ \^ / +") Token Stack 3 ((9 . 3)) 4 ((9 . 4) (9 . 3)) 2 ((9 . 2) (9 . 4) (9 . 3))
- ((3 . "4 * 2") (9 . 3))
1 ((9 . 1) (3 . "4 * 2") (9 . 3)) 5 ((9 . 5) (9 . 1) (3 . "4 * 2") (9 . 3)) - ((2 . "1 - 5") (3 . "4 * 2") (9 . 3)) 2 ((9 . 2) (2 . "1 - 5") (3 . "4 * 2") (9 . 3)) 3 ((9 . 3) (9 . 2) (2 . "1 - 5") (3 . "4 * 2") (9 . 3)) ^ ((4 . "2 \^ 3") (2 . "1 - 5") (3 . "4 * 2") (9 . 3)) ^ ((4 . "(1 - 5) \^ 2 \^ 3") (3 . "4 * 2") (9 . 3)) / ((3 . "4 * 2 / (1 - 5) \^ 2 \^ 3") (9 . 3)) + ((2 . "3 + 4 * 2 / (1 - 5) \^ 2 \^ 3")) -> "3 + 4 * 2 / (1 - 5) \^ 2 \^ 3"
- (rpnToInfix "1 2 + 3 4 + \^ 5 6 + \^")
Token Stack 1 ((9 . 1)) 2 ((9 . 2) (9 . 1)) + ((2 . "1 + 2")) 3 ((9 . 3) (2 . "1 + 2")) 4 ((9 . 4) (9 . 3) (2 . "1 + 2")) + ((2 . "3 + 4") (2 . "1 + 2")) ^ ((4 . "(1 + 2) \^ (3 + 4)")) 5 ((9 . 5) (4 . "(1 + 2) \^ (3 + 4)")) 6 ((9 . 6) (9 . 5) (4 . "(1 + 2) \^ (3 + 4)")) + ((2 . "5 + 6") (4 . "(1 + 2) \^ (3 + 4)")) ^ ((4 . "((1 + 2) \^ (3 + 4)) \^ (5 + 6)")) -> "((1 + 2) \^ (3 + 4)) \^ (5 + 6)"</lang>
Python
<lang python>from collections import namedtuple
OpInfo = namedtuple('OpInfo', 'prec assoc') L, R = 'Left Right'.split()
ops = {
'^': OpInfo(prec=4, assoc=R), '*': OpInfo(prec=3, assoc=L), '/': OpInfo(prec=3, assoc=L), '+': OpInfo(prec=2, assoc=L), '-': OpInfo(prec=2, assoc=L), ')': OpInfo(prec=9, assoc=L), #NUM: OpInfo(prec=0, assoc=L) }
numinfo = OpInfo(prec=9, assoc=L)
NUM, LPAREN, RPAREN = 'NUMBER ( )'.split()
def get_input(inp = None):
'Inputs a space separated expression and returns list of tokens' if inp is None: inp = input('expression: ') return inp.strip().split()
def rpn2infix(tokens):
stack = [] # [ (partial_expr, (prec, assoc)), ... ] table = ['TOKEN,ACTION,STACK (comma separated)'.split(',')] for token in tokens: if token in ops: action = 'Push partial expression' opinfo = ops[token] b = stack.pop(); a = stack.pop() if b[1].prec < opinfo.prec: b = '( %s )' % b[0], ops[')'] if a[1].prec < opinfo.prec: a = '( %s )' % a[0], ops[')'] stack.append( ('%s %s %s' % (a[0], token, b[0]), opinfo) ) else: action = 'Push num' stack.append((token, numinfo)) row = (token, action, ', '.join(str(s[0]) for s in stack)) #pp(row, width=120) table.append( row )
return table
if __name__ == '__main__':
rpn = '3 4 2 * 1 5 - 2 3 ^ ^ / +' print( 'For RPN expression: %r\n' % rpn ) infix = rpn2infix(get_input(rpn)) maxcolwidths = [len(max(x, key=lambda y: len(y))) for x in zip(*infix)] row = infix[0] print( ' '.join('{cell:^{width}}'.format(width=width, cell=cell) for (width, cell) in zip(maxcolwidths, row))) for row in infix[1:]: print( ' '.join('{cell:<{width}}'.format(width=width, cell=cell) for (width, cell) in zip(maxcolwidths, row)))
print('\n The final output infix expression is: %r' % infix[-1][2])</lang>
- Sample output
For RPN expression: '3 4 2 * 1 5 - 2 3 ^ ^ / +' TOKEN ACTION STACK (comma separated) 3 Push num 3 4 Push num 3, 4 2 Push num 3, 4, 2 * Push partial expression 3, 4 * 2 1 Push num 3, 4 * 2, 1 5 Push num 3, 4 * 2, 1, 5 - Push partial expression 3, 4 * 2, 1 - 5 2 Push num 3, 4 * 2, 1 - 5, 2 3 Push num 3, 4 * 2, 1 - 5, 2, 3 ^ Push partial expression 3, 4 * 2, 1 - 5, 2 ^ 3 ^ Push partial expression 3, 4 * 2, ( 1 - 5 ) ^ 2 ^ 3 / Push partial expression 3, 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 + Push partial expression 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 The final output infix expression is: '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'
Ruby
See Parsing/RPN/Ruby
<lang ruby>rpn = RPNExpression.new("3 4 2 * 1 5 - 2 3 ^ ^ / +") infix = rpn.to_infix ruby = rpn.to_ruby</lang> outputs
for RPN expression: 3 4 2 * 1 5 - 2 3 ^ ^ / + Term Action Stack 3 PUSH [node[3]] 4 PUSH [node[3], node[4]] 2 PUSH [node[3], node[4], node[2]] * MUL [node[3], node[*]<left=node[4], right=node[2]>] 1 PUSH [node[3], node[*]<left=node[4], right=node[2]>, node[1]] 5 PUSH [node[3], node[*]<left=node[4], right=node[2]>, node[1], node[5]] - SUB [node[3], node[*]<left=node[4], right=node[2]>, node[-]<left=node[1], right=node[5]>] 2 PUSH [node[3], node[*]<left=node[4], right=node[2]>, node[-]<left=node[1], right=node[5]>, node[2]] 3 PUSH [node[3], node[*]<left=node[4], right=node[2]>, node[-]<left=node[1], right=node[5]>, node[2], node[3]] ^ EXP [node[3], node[*]<left=node[4], right=node[2]>, node[-]<left=node[1], right=node[5]>, node[^]<left=node[2], right=node[3]>] ^ EXP [node[3], node[*]<left=node[4], right=node[2]>, node[^]<left=node[-]<left=node[1], right=node[5]>, right=node[^]<left=node[2], right=node[3]>>] / DIV [node[3], node[/]<left=node[*]<left=node[4], right=node[2]>, right=node[^]<left=node[-]<left=node[1], right=node[5]>, right=node[^]<left=node[2], right=node[3]>>>] + ADD [node[+]<left=node[3], right=node[/]<left=node[*]<left=node[4], right=node[2]>, right=node[^]<left=node[-]<left=node[1], right=node[5]>, right=node[^]<left=node[2], right=node[3]>>>>] Infix = 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 Ruby = 3 + 4 * 2.to_f / ( 1 - 5 ) ** 2 ** 3
Tcl
<lang tcl>package require Tcl 8.5
- Helpers
proc precassoc op {
dict get {^ {4 right} * {3 left} / {3 left} + {2 left} - {2 left}} $op
} proc pop stk {
upvar 1 $stk s set val [lindex $s end] set s [lreplace $s end end] return $val
}
proc rpn2infix rpn {
foreach token $rpn {
switch $token { "^" - "/" - "*" - "+" - "-" { lassign [pop stack] bprec b lassign [pop stack] aprec a lassign [precassoc $token] p assoc if {$aprec < $p || ($aprec == $p && $assoc eq "right")} { set a "($a)" } if {$bprec < $p || ($bprec == $p && $assoc eq "left")} { set b "($b)" } lappend stack [list $p "$a $token $b"] } default { lappend stack [list 9 $token] } } puts "$token -> $stack"
} return [lindex $stack end 1]
}
puts [rpn2infix {3 4 2 * 1 5 - 2 3 ^ ^ / +}] puts [rpn2infix {1 2 + 3 4 + ^ 5 6 + ^}]</lang> Output:
3 -> {9 3} 4 -> {9 3} {9 4} 2 -> {9 3} {9 4} {9 2} * -> {9 3} {3 {4 * 2}} 1 -> {9 3} {3 {4 * 2}} {9 1} 5 -> {9 3} {3 {4 * 2}} {9 1} {9 5} - -> {9 3} {3 {4 * 2}} {2 {1 - 5}} 2 -> {9 3} {3 {4 * 2}} {2 {1 - 5}} {9 2} 3 -> {9 3} {3 {4 * 2}} {2 {1 - 5}} {9 2} {9 3} ^ -> {9 3} {3 {4 * 2}} {2 {1 - 5}} {4 {2 ^ 3}} ^ -> {9 3} {3 {4 * 2}} {4 {(1 - 5) ^ 2 ^ 3}} / -> {9 3} {3 {4 * 2 / (1 - 5) ^ 2 ^ 3}} + -> {2 {3 + 4 * 2 / (1 - 5) ^ 2 ^ 3}} 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3 1 -> {9 1} 2 -> {9 1} {9 2} + -> {2 {1 + 2}} 3 -> {2 {1 + 2}} {9 3} 4 -> {2 {1 + 2}} {9 3} {9 4} + -> {2 {1 + 2}} {2 {3 + 4}} ^ -> {4 {(1 + 2) ^ (3 + 4)}} 5 -> {4 {(1 + 2) ^ (3 + 4)}} {9 5} 6 -> {4 {(1 + 2) ^ (3 + 4)}} {9 5} {9 6} + -> {4 {(1 + 2) ^ (3 + 4)}} {2 {5 + 6}} ^ -> {4 {((1 + 2) ^ (3 + 4)) ^ (5 + 6)}} ((1 + 2) ^ (3 + 4)) ^ (5 + 6)
TXR
@(next :args)
@(define space)@/ */@(end)
@(define number (nod))@\
@(local n)@(space)@{n /[0-9]+/}@(space)@\
@(bind nod @(int-str n 10))@\
@(end)
@(define op (nod))@\
@(local op)@\
@(space)@\
@(cases)@\
@{op /[+\-*^]/}@\
@(bind nod @(intern op *user-package*))@\
@(or)@\
/@\
@(bind nod @(intern "\\" *user-package*))@\
@(end)@\
@(space)@\
@(end)
@(define term (nod))@(cases)@(number nod)@(or)@(op nod)@(end)@(end)
@(define rpn (list))@(coll :gap 0 :vars (list))@(term list)@(end)@(end)
@(freeform)
@(rpn rpn)@junk@\n
@(output)
rpn tokens: [@rpn]
trailing junk: [@junk]
@(end)
@(do (defvar *prec* '((^ . 4)
(* . 3)
(\ . 3)
(+ . 2)
(- . 2)))
(defvar *asso* '((^ . :right)
(* . :left)
(\ . :left)
(+ . :left)
(- . :left)))
(defun rpn-to-lisp (rpn)
(let (stack)
(each ((term rpn))
(format t "rpn term: ~s\n" term)
(if (symbolp term)
(let ((right (pop stack))
(left (pop stack)))
(push '(,term ,left ,right) stack))
(push term stack))
(format t "stack: ~s\n" stack))
(if (rest stack)
(return-from error "*excess stack elements*"))
(pop stack)))
(defun prec (term)
(cond
((null term) 99)
((symbolp term) (cdr (assoc term *prec*)))
((atom term) 99)
(t (prec (car term)))))
(defun asso (term)
(cond
((null term) :none)
((symbolp term) (cdr (assoc term *asso*)))
((atom term) :none)
(t (asso (car term)))))
(defun inf-op (op)
(if (eq op '\) "/" op))
(defun inf-term (op term left-or-right)
(let ((pt (prec term))
(po (prec op))
(at (asso term))
(ao (asso op)))
(cond
((< pt po) `(@(lisp-to-infix term))`)
((> pt po) `@(lisp-to-infix term)`)
((and (eq at ao) (eq left-or-right ao)) `@(lisp-to-infix term)`)
(t `(@(lisp-to-infix term))`))))
(defun lisp-to-infix (lisp)
(if (atom lisp)
(if (null lisp)
(return-from error "*stack underflow*")
(if (eq lisp '\) "/" `@lisp`))
(let ((op (first lisp))
(left (second lisp))
(right (third lisp)))
(let ((left-inf (inf-term op left :left))
(right-inf (inf-term op right :right)))
`@{left-inf} @(inf-op op) @{right-inf}`)))))
@(bind infix @(block error (lisp-to-infix (rpn-to-lisp rpn))))
@(output)
infix: @infix
@(end)
$ ./txr rosetta/rpn.txr '3 4 2 * 1 5 - 2 3 ^ ^ / +' rpn tokens: [3 4 2 * 1 5 - 2 3 ^ ^ \ +] trailing junk: [] rpn term: 3 stack: (3) rpn term: 4 stack: (4 3) rpn term: 2 stack: (2 4 3) rpn term: * stack: ((* 4 2) 3) rpn term: 1 stack: (1 (* 4 2) 3) rpn term: 5 stack: (5 1 (* 4 2) 3) rpn term: - stack: ((- 1 5) (* 4 2) 3) rpn term: 2 stack: (2 (- 1 5) (* 4 2) 3) rpn term: 3 stack: (3 2 (- 1 5) (* 4 2) 3) rpn term: ^ stack: ((^ 2 3) (- 1 5) (* 4 2) 3) rpn term: ^ stack: ((^ (- 1 5) (^ 2 3)) (* 4 2) 3) rpn term: \ stack: ((\ (* 4 2) (^ (- 1 5) (^ 2 3))) 3) rpn term: + stack: ((+ 3 (\ (* 4 2) (^ (- 1 5) (^ 2 3))))) infix: 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3 $ ./txr rosetta/rpn.txr '1 2 + 3 4 + ^ 5 6 + ^' rpn tokens: [1 2 + 3 4 + ^ 5 6 + ^] trailing junk: [] rpn term: 1 stack: (1) rpn term: 2 stack: (2 1) rpn term: + stack: ((+ 1 2)) rpn term: 3 stack: (3 (+ 1 2)) rpn term: 4 stack: (4 3 (+ 1 2)) rpn term: + stack: ((+ 3 4) (+ 1 2)) rpn term: ^ stack: ((^ (+ 1 2) (+ 3 4))) rpn term: 5 stack: (5 (^ (+ 1 2) (+ 3 4))) rpn term: 6 stack: (6 5 (^ (+ 1 2) (+ 3 4))) rpn term: + stack: ((+ 5 6) (^ (+ 1 2) (+ 3 4))) rpn term: ^ stack: ((^ (^ (+ 1 2) (+ 3 4)) (+ 5 6))) infix: ((1 + 2) ^ (3 + 4)) ^ (5 + 6)
Associativity tests (abbreviated output):
$ ./txr rosetta/rpn.txr '1 2 3 + +' [ ... ] infix: 1 + (2 + 3) $ ./txr rosetta/rpn.txr '1 2 + 3 +' [ ... ] infix: 1 + 2 + 3 $ ./txr rosetta/rpn.txr '1 2 3 ^ ^' rpn tokens: [1 2 3 ^ ^] [ ... ] infix: 1 ^ 2 ^ 3 $ ./txr rosetta/rpn.txr '1 2 ^ 3 ^' [ ... ] infix: (1 ^ 2) ^ 3