Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

comment on

( [id://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":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others musing on the Monastery: (3)
As of 2024-03-29 06:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found