My own infix to prefix approach. What do you think?

[HP67]

(04-29-2014 11:31 PM)Les Bell Wrote:  The key point is that the shunting yard algorithm does one thing only - parse infix expressions and emit a prefix representation.

The shunting-yard algorithm doesn't parse anything. It is a relatively dumb state machine. If the input token stream represents a valid arithmetic infix expression the machine produces a representative postfix expression as a token stream. It is up to the implementer to write his own scanner and various other pieces. As far as the algorithm goes, and even as far as implementing it goes, parsing is not part of the discussion.

But yes, that is all the OP asked for: To convert an infix expression to a postfix expression. Therefore Thomas' answer is the right one. Telling the OP to go learn a parser generator toolkit in Java is confusing, harmful, and most of all doesn't answer the question.

(04-29-2014 11:31 PM)Les Bell Wrote:  To paraphrase, I'll simply say that with the shunting yard algorithm, Matt has been given a fish; but ANTLR is a complete fishing rod, hooks, bait, pots, pans and a vegetable garden with all the things he'll need to cook that fish and any others he catches.

All the OP asked was how to convert an infix expression into a postfix expression. He doesn't need anything you mentioned to understand that. What Thomas pointed him to was about the best answer we could give. Indeed, your answer to use a parser generator not only doesn't answer the question, it goes one further and totally obscures the exact knowledge the OP asked about.

I'm sure it wasn't intentional but you essentially thread-jacked a discussion on "how do infix expressions get converted to postfix expressions" into "let's write a parser using automated parser generator tools." Your approach would be acceptable in a one semester course where students are supposed to "write" their own compiler. They can't do that from scratch, so they use all the tools you mention. But none of that is what the OP asked about. It's totally off-topic.

Neither the Dragon book (in various versions) nor Lexx, Yacc, Bison, etc. have advanced the state of the art of converting infix expressions to postfix expressions. They have nothing to do with that at all. There is a big difference between building a parse tree for abstract syntax or grammer and the conversion of a mathematic infix expression to postfix, which is the subject of this thread. And also no, Dijkstra hasn't made any impact on our work, nor has he impressed any of us who write software for a living.