Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
Any pointers to code snippets would be great, before I roll my own.

The simplest way I know to convert Infix to RPN is to use stacks. You will need two stacks, one for operators, and the other a container for your RPN formated expression. Then the algorithm basically goes something like this:

my $token_count = 0; while (@tokens) { my $token = shift @tokens; # if its an opening paran then ... if ($token eq '(') { push(@operator_stack, $token); } # if it's an operator then ... elsif (is_operator($token)) { push(@operator_stack, $token); } # if its a closing paran then ... elsif ($token eq ')') { # empty the operator stack until # we find the opening paren while (@operator_stack && $operator_stack[-1] ne '(') { # and push everything onto the # operator stack push @program_stack, (pop @operator_stack); } # then pop the opening paren off pop @operator_stack; } # if its not an operator, or a paran ... else { push @program_stack, $token; $token_count++; # if we have 2 or more tokens on the # program stack (since out last operator) # we need to get an operator .... if ($token_count >= 2){ # unless the top of our operator stack # is a opening paran, in which case # we have a sub-expression which needs # to be handled first next if $operator_stack[-1] eq '('; # otherwise grab the operator, and ... push @program_stack, (pop @operator_stack); # reset the token count $token_count = 1; } } } # and lastly, empty whats left of your # operator stack onto your program stack push @program_stack, (pop @operator_stack) while (@operator_stack);

I got this algorithm from a old book on FORTH, and they had this table in it, which I found helpful in visually explaining the algorithm.

 source string  | operator stack | program stack
----------------+----------------+----------------
    A+(B*C-D)/E |                |                
     +(B*C-D)/E |                | A
      (B*C-D)/E | +              | A                                      
       B*C-D)/E | +(             | A      
        *C-D)/E | +(             | AB
         C-D)/E | +(*            | AB                    
          -D)/E | +(*            | ABC           
           D)/E | +(-            | ABC*
            )/E | +(-            | ABC*D                     
             /E | +              | ABC*D-            
              E | +/             | ABC*D-                         
                | +/             | ABC*D-E                                       
                |                | ABC*D-E/+      

Of course, this code and algorithm somewhat relies on properly nested parens, and will not handle the 'max()' part of your expression, but it's something to start with.

The more complex way to do it (and both more flexible and robust) is to build a parse tree out of your expression, then you can get infix, postfix, prefix, whatever-fix order you want just by traversing the tree in different ways. I actually show examples of this conversion-through-traversal in the docs for my module Tree::Binary (more specifically the examples are in Tree::Binary::Visitor::InOrderTraversal, Tree::Binary::Visitor::PreOrderTraversal and Tree::Binary::Visitor::PostOrderTraversal in their SYNOPSIS sections).

The algorithm for building a parse tree is not entirely unlike the stack version above, except its more complex and you are not building a program stack, but a parse tree. The operator stack is still a very useful tool in helping you decide to go up or down the tree. Unfortunately I don't have any example code for this, and besides, it is very dependent upon how you structure your tree anyway. I am sure though that a quick google search on building parse trees will provide you with some insight.

-stvn

In reply to Re: Generic RPN Translator available? by stvn
in thread Generic RPN Translator available? by saintmike

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 sharing their wisdom with the Monastery: (1)
As of 2024-05-22 13:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found