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

[HP67]

(04-29-2014 12:35 PM)Les Bell Wrote:  

(04-29-2014 08:55 AM)HP67 Wrote:  Thomas beat me to it but this one-hit wonder from Dijkstra appears to be a milestone of algorithmic approach to this.

Ah, but there's the rub - it's a one-hit wonder - which topped the charts in 1961,

I meant it's the only thing Dijkstra has contributed that was actually useful.

(04-29-2014 12:35 PM)Les Bell Wrote:  but the world has moved on since then.

Really? I haven't seen anything formalized.

(04-29-2014 12:35 PM)Les Bell Wrote:  How do you add support for complex numbers? Vectors? Arrays? Flow control such as function definition, if-then-else and while? Local vs global variables? Classes? And so it goes

I won't put words in your mouth but it sounds like you're suggesting complex numbers, vectors, and arrays didn't exist in Dijkstra's time but they did. The shunting-yard algorithm is not an implementation, it's an algorithm. It works, and it's been extended usefully. I don't see any problems with the algorithm breaking on anything you mentioned.

As for your coments about function definition, local vs global variables, classes, etc, none of that is in context here. The shunting yard algorithm is about translating an infix expression to a postfix expression. That's all. You've complicated the discussion by conflating scanning with parsing, and by suggesting the OP use a bigger hammer where it isn't even clear a hammer is needed in the first place.

(04-29-2014 12:35 PM)Les Bell Wrote:  . . . The decision really is, does Matt want to learn a generally-useful approach to parsing and language translation, or one algorithm for one specific problem?

The 800-pound gorilla dressed as a "generally-useful approach" you seem to be suggesting is other people's tools. That is one of the best ways I know to never learn anything at all and to never become a good coder.

And that is why I asked "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?"

(04-29-2014 12:35 PM)Les Bell Wrote:  Hand-coding the shunting-yard algorithm is a basic exercise in coding stacks and queues, but ANTLR gets more work done, faster, using much more powerful techniques. Much better for exploring the underlying ideas and turning them into something useful.

That's just a matter of opinion, and it's one that I strongly disagree with. But, I agree it's a matter of choice that should at least be articulated. Most of the coders today are cut and paste jockeys. All the big and popular languages have so many libraries that you really don't have to be much of anything to "write" a program. You can be real productive until something goes wrong.

On the other hand, if you want to understand things nothing beats writing your own programs and your own tools.