Talk:Shunting yard algorithm

From Wikipedia, the free encyclopedia

I think this page needs correction: o1 is associative or left-associative and its precedence is greater than or equal should be less than or equal, and o1 is right-associative and its precedence is less than that of o2 should too. The method works fine when using that modification, but gives strange answers otherwise. The example also follows the rule as less than, not greater than.

—

Is the complex example correct? I'm new at RPN, but I think I remember my basic arithmetic. When I enter 3 4 2 * 1 5 - 2 ^ / + in an RPN calculator, I get 3.5, but when I calculate 3+4*2/(1-5)^2, I get 0.6875. I'll be really embarrassed if I miscalculated. lomedhi

—

3+4*2/(1-5)^2
3+4*2/(-4)^2
3+4*2/16
3+8/16
3+0.5
3.5

Italo Tasso 05:32, 24 October 2006 (UTC)

—

Whoops. I screwed up my order of operations on 3+8/16. I saw it in my head as:

\frac{3+8}{16}

I am indeed duly embarrassed.

lomedhi 21:08, 7 November 2006 (UTC)

Contents

[edit] Abstract syntax tree

How to use this algorithm to produce an abstract syntax tree? exe 01:01, 11 March 2007 (UTC)

[edit] Operator precedence??

Hello, I have just implemented this algorithm and I believe that the latest corrections (by anonymous users) to the detailed description might be wrong. I believe it should read

1) while there is an operator, o2, at the top of the stack, and either

o1 is associative or left-associative and its precedence is less than (lower precedence) or equal to that of o2, or

o1 is right-associative and its precedence is less than (lower precedence) that of o2,

Earlier versions of this page seem to have had it this way originally

Also, ^2^3 in infix notation means ^8 by my reckoning, so the final answer I get for the complex example 3+4*2/(1−5)^2^3 is 3.0001220703125

Mike mueller nz 11:48, 4 April 2007 (UTC)

After a bit of head scratching and rereading I was able to implement this in Perl with no problems besides the fact that this was my second program in Perl... I used at as one function of a command line calculator, with somewhat cleaned up math problems going in and an array where each element was an operand or operator making an RPN equation going out the other. 72.50.165.166 05:47, 5 April 2007 (UTC)

-

How to handle functions in the stack?


Bjc world (talk) 14:02, 31 December 2007 (UTC) BEGIN
I think 'The algorithm in detail' section needs to clarify how to process functions when the token being examined is an operator. In particular, the logic describes what to do if the top element on the stack is an operator, but it does not say what to do if the top element on the stack is a function or parenthesis (the stack may contain left parentheses, functions and operators). I believe the correct functionality is to treat functions like operators, but then there is the question of what precedence a function has. In my implementation, I have set functions to have a higher precedence than multiplication and division and lower than parenthesis and this seems to work.
Bjc world (talk) 14:02, 31 December 2007 (UTC) END

[edit] unary minus "-"

Does this algorithm work with unary minus "-" ( -x + x = 0 ) ?

If so, are these fundamental properties or conventions satisfied? :

a-b = a+(-b)

-a^b = -(a^b)

a/-b = a/(-b)

a^-b = a^(-b)

a/-b^c = a/-(b^c)

a^-b^c = a^-(b^c)

Thanks.

yes but priorities must be such that
  • binary_on_stack < minus (=> pospounding output of binary_on_stack, so minus goes first)
  • and minus_on_stack < binary ( binary goes first )
  • ...

edit: basically you answered yourself ca1 (talk) 01:20, 11 May 2008 (UTC)

[edit] a a + + c

something like that will parse ok. should not there be mentioned that input has to be correct infix? ca1 (talk) 01:03, 11 May 2008 (UTC)