Post Reply 
My own infix to prefix approach. What do you think?
04-29-2014, 08:55 AM
Post: #8
RE: My own infix to prefix approach. What do you think?
(04-29-2014 04:16 AM)Thomas Klemm Wrote:  Or you can simply use the Shunting-yard algorithm.

Thomas beat me to it but this one-hit wonder from Dijkstra appears to be a milestone of algorithmic approach to this. The only (obvious) thing the vanilla algorithm description doesn't seem to cover is function calls with multiple arguments. For expressions it seems to work fine.

Unlike many wiki pages, the one Thomas referenced is actually pretty usable. A reasonable implementation can be worked out by understanding what's written on the page.

IBM had described another method for this in an early FORTRAN (pre FORTRAN IV) manual. I am sorry, but I cannot remember the particulars including whether IBM or Dijkstra got there first. But I do remember their approach involved consuming the expression and parenthesizing everything until the order of evaluation was unequivocal, and then converting it into object code. I realize that is not much of a description but you can find more online.

You are in an area now where there is a basic decision to be made. Do you want to understand things at a low level and write your own implementation from the algorithmic description, or do you want to write a high-level driver program that uses other people's library functions or tools to accomplish what you want? Of course, there is always the possibility of developing even the algorithm yourself, but for classical problems like this most things have been settled already.

It ain't OVER 'till it's 2 PICK
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: My own infix to prefix approach. What do you think? - HP67 - 04-29-2014 08:55 AM



User(s) browsing this thread: 1 Guest(s)