Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
<body bgcolor="#ffffff"> I tried to implement this even in expanded code, but my grasp of Perl is still a little too loose. Expanding chipmunk's code didn't really help any either (I couldn't seem to expand it properly.. maybe it's just lack of sleep ;). So instead of submitting a golfed answer, I'd like to submit up the reasoning behind what I tried to implement to see if I was even on the right track. And if it was on the right track, maybe someone will benefit from the approach.

The basic idea behind the approach is to only examine three (3) elements of the stack at a time and work solely on those until the entire stack is resolved. Our three element pattern will consist of two numbers, and an operand. So if we test the three elements against the operator hash, 0 0 1 will be the truth values returned. Represented here as:

     

We'll now populate the stack with a test case 3 4 5 / + 2 * and go through converting it to the end string.

i=1: <tr align="center" bgcolor="#ffffff"">
3 4 5 / + 2 *
3 4 X        

The first iteration didn't return a match so move on position along the stack.

i=2: <tr align="center" bgcolor="#ffffff"">
3 4 5 / + 2 *
  4 5 / 2    

Our stack slice has matched its pattern. The 2 after the slice is to show the precedence of the operator, in the first match this doesn't have any bearing.

Having a match we now move it into our answer string. The first thing we do is set the precedence of our current string, which in this case is $precedence = 2; because the / operator has a value of 2 in the hash. We can then flip the operator into it's place between the two numbers and store it as the string "4/5". The last step is to sub the string back into the stack, and restart the iterations. The string will be represented as S in the stack for clarity.

i=1: <tr align="center" bgcolor="#ffffff"">
3 S + 2 *
3 S + 1  

Our stack slice has matched its pattern. This time the precedence of the operator will have to be compared against the current strings precedence. As 1 < 2 we don't need to insert parenthesis around the string. We perform the same operation as before, store the new $precedence = 1 then flip the last two elements (S and +), store it as the string "3+4/5", then sub it back into our now small stack.

i=1: <tr align="center" bgcolor="#ffffff"">
S 2 *
3 S * 2

Our stack slice has matched its pattern. The precedence operator of this stack piece is greater than our strings precedence 2 > 1 so we have to add parenthesis around the string before we move on. Once that's done we can follow the same operations as before, coming out with the string "(3+4/5)*2" which is correct to our defined precedence.

The string gets plugged back into the stack, the outer loop has it's condition fufilled (the stack has less than 3 elements) so exits returning our string.

Theoretically this approach should work for as many operators and levels of precedence a user cares to assign without extraneous parenthesis, as it evaluates them one at a time. Does this make sense? I couldn't get it to work and it's wasn't for lack of trying.

</body>

In reply to Re: (Golf) Reversing RPN Notation by Arguile
in thread (Golf) Reversing RPN Notation by Masem

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others having an uproarious good time at the Monastery: (7)
    As of 2014-12-21 06:19 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      Is guessing a good strategy for surviving in the IT business?





      Results (104 votes), past polls