Talk:Shunting yard algorithm (C)

From LiteratePrograms

Code origin

All code originally in this article was written by me. Nothing has been directly copied from other resources. This article and other online resources has been used as reference. Ahy1 10:06, 15 May 2007 (PDT)

Bugs

I am surpised to see that 1-3+8 results in -10, I would expect 6. Entering -3 returns an error.

The reason it resulted in -10, is that I had used different precedence level for + and -. This is now corrected: + and - now has the same level (5). The same with *, / and % (8).

There was a bug in handling the unary '-' operator which caused it to be threated as a binary when it was the first token. This is now corrected (I beleive).

Thanks for reporting these bugs. Ahy1 12:47, 31 July 2007 (PDT)

Thanks for your earlier fixes. I expect '-3 1' to fail because it lacks an operand, but it returns '2'.

On my PC, I had "ERROR: Number stack empty" with '-3 1', which in this case is incorrect. The stack actually had 2 element. I have changed the error message.

Anyway, this error should be catched earlier, when parsing the tokens. There is also another bug in the tokenizer ('3 -1' fails). I don't have time to fix this now, but will have a look at it later, unless someone else fixes it. Ahy1 13:03, 2 August 2007 (PDT)

Testing of the code.

I ported this code to use the standard template libraries stack container class and when running the test script I got a mismatch on the last error. My implementation returns the error "Stack error. No matching(" whilst the original sample returns the error "ERROR: Number stack empty". Looking at the code it seems that you never hit the "no matching ( " case as it is instead caught by the pop_numstack case. Just wondering if I should make my implementation match or not.

Paul.

Hi Paul! I don't think we should get "no matching (" on the last test, but it would be a natural result on the test before that. As you said, it seems like we will never hit the "no matching (", which makes the check totally unnecessary. This should be fixed either by removing the check for '(' or changing the way pop_numstack() works. In the last case the tests have to be updated. I will fix this when I find some spare time for it, unless anyone else is quicker...

A C++ implementation using the standard containers would be nice to have, so if you are allowed to post your port here it would be great! It doesn't have to pass the same tests, but sharing test code between two implementations might be an advantage. Ahy1 08:46, 10 September 2009 (MDT)