Talk:Shunting yard algorithm

Early discussions

--78.50.237.77 (talk) 07:40, 10 May 2012 (UTC)

The code does not compile because of missing cast at line: 223, 226, 236, 240, 243, 257 for "&sc". I know it is implicite casting which is supported by C, but for example gcc doesn't compile.

The right form is

printf("%s;\n",(char *) &sc);

instead of

printf("%s;\n", &sc);

Please correct it.

---

I think the code of this page is not correct. In particular, the output shown by the example is not correct. Let me copy here the execution example (August 23rd, 2011)

input: a = D(f - b * c + d, !e, g)
output: afbc*-d+e!gD=
order: (arguments in reverse order)
_00 = c * b;
_01 = _00 - f;
_02 = d + _01;
_03 = ! e;
_04 = D(g, _03, _02)
_05 = _04 = a;
_05 is a result

Observe the output of "_01". It should be

_01 = f - _00

The problem is located in the execution_order function. The code that says

sc = stack[sl - 1];
sl--;
printf("%s %c ", &sc, c);
sc = stack[sl - 1];
sl--;
printf("%s;\n",&sc);

should be replaced by

sc = stack[sl - 2];
printf("%s %c ", &sc, c);
sc = stack[sl - 1];
sl--; sl--;
printf("%s;\n",&sc);

In this case the output of the execution is

input: a = D(f - b * c + d, !e, g)
output: afbc*-d+e!gD=
order: (arguments in reverse order)
_00 = b * c;
_01 = f - _00;
_02 = _01 + d;
_03 = ! e;
_04 = D(g, _03, _02)
_05 = a = _04;
_05 is a result

Lgoster (talk) 14:45, 23 August 2011 (UTC)

—

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)

Abstract syntax tree

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

Answer:

Every time you push an operator, pop off the necessary number of arguments, so it could look something like this (untested):

   struct node{
       val self;
       int argc;
       node *argv;
   }
   bool ast_add(node *stack,val new_val,int max_len,int len){
       if(max_len)return false;//could realloc
       node n;
       n.argv=(n.argc=val_get_arity(n.self=new_val))&&(node*)malloc(n.argc*sizeof(node));
       if(len<n.argc)
           return false;
       for(int i=0;i<n.argc;++i)
           n.argv[i]=stack[--len];
       stack[len++]=n;
   }

— Preceding unsigned comment added by 99.240.99.150 (talk • contribs) 8 September 2011

While the effort above is appreciated, it is really not much help. Because it's pretty stiff old-school C highly steeped in the idiosyncratic conventions of the C run-time and other compiler jargon terms (like "arity"), it's not really understandable by anyone other than an expert C programmer (most of whom already know this). More problematic is its dependence on the principle of popping off "the necessary number of arguments" (i.e., "arity"), information that the shunting-yard algorithm is not supposed to have nor need.

What's really needed here is an addition to the main article that provides a working pseudocode example of a Shunting-Yard algorithm that produces correct AST output with the information that is available. Otherwise, the claim should be removed. RBarryYoung (talk) 21:26, 25 November 2012 (UTC)

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

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)

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)

Bitwise XOR operator in example is incorrect?

The complex example section has these two statements:

• "^ has higher precedence than /"
• "^ is evaluated right-to-left"

Neither of these statements are true, at least in most programming languages I can think of:

http://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B#Operator_precedence

Treating bitwise XOR like C++ should produce this final RPN output, presuming I didn't screw up my test program:

 3 4 2 * 1 5 - / + 2 ^ 3 ^

The current revision shoves "^ ^ / +" to the end of the output. Can someone verify that my assertion (and work!) are correct?

155.229.108.58 (talk) 21:32, 23 February 2009 (UTC)Ryan C. Gordon

Exponential operator

The operator '^' in this case isn't the bitwise XOR operator as in C++ but rather the exponential operator, so '^' is right-associative and has greater precedence than '/' in this example. Nevertheless, this could be explicitly stated in the article to avoid such confusion. —Preceding unsigned comment added by 190.232.14.227 (talk) 21:21, 6 March 2009 (UTC)

C++ example code

I just took a look at the C++ example code, and it is shocking.

Why on earth are enums not being used in place of those magic numbers? I would go ahead and change it myself but I assume there's a reason behind not using enums.

Can someone clarify this? 124.168.95.207 (talk) 04:43, 18 July 2010 (UTC)

And what's the use of a huge block of code in the middle of an article?

bug

There is a bug in the argument-number checking both in the algorithm and in the code. The program crashes for some incorrect input (ie: "a + (b + )"). I don't know the solution so I am not modifying the article. Need an expert, someone can help? - —Preceding unsigned comment added by 90.80.39.41 (talk) 15:45, 20 July 2010 (UTC)

The algorithm is assuming sane input, which is fine for illustrating the basics of how the algorithm works. I would say its not really wikipedias job to provide fully working solutions with full error checking. A quick fix is to add a sanity check after the output has been produced, basically count up the number of numbers and variables, n, count up the number of binary operators, m, to be sane m=n-1. This can actually be done by checking the return value from execution_order(output) which must be true.

A better approach would be to check the input, while parsing, using a formal grammar Backus–Naur Form. If we restrict ourselves to numbers, variable, binary operators and brackets then we basically have two states: next token must be a number, variable or left bracket; next token must be an operator or right bracket. This is the approach taken in [1] which does have a working implementation of the algorithm which I have successfully used myself.--Salix (talk): 19:18, 20 July 2010 (UTC)

.svg is confusing from step d) to step e)

The .svg graphic is confusing from step d) to step e). The transition between earlier steps only moves one item at a time. The transition from step d) to step e) moves three items at once. It's unclear as to which '+' was moved to the output and which plus is moved to the operand stack for that transition. Was the plus on the operand stack moved to the output and the plus at the input moved to the operand stack? Or, was the plus from the input moved to the output? If someone doesn't understand the algorithm, they won't know that the plus at the output is from the operand stack and the plus now on the operand stack was from the input. They won't recognize that both pluses were moved and one of them is now in the same place that the other one was. They'll think that the plus from the input was moved to the output. This can be resolved by moving fewer items per state transition, or by changing the second plus to a minus. —Preceding unsigned comment added by 98.243.108.232 (talk) 18:12, 21 December 2010 (UTC)

C example

The following should be added to the C example after the #include statements so it compiles in ANSI C:

 #define bool int
 #define false 0
 #define true 1

These terms are not supported. —Preceding unsigned comment added by 71.220.68.202 (talk) 03:54, 10 January 2011 (UTC)

I see that change made it in the article. Another option is to include the c99 header <stdbool.h> which save two lines of code but break ANSI c89 compatibility. R4p70r (talk) 06:02, 18 February 2011 (UTC)

I'm testing C example. I'm getting correct output when reversing operator precedence OR changed code to:

((op_left_assoc(c) && (op_preced(c) >= op_preced(sc))) ||
                          (op_preced(c) > op_preced(sc))))

Is it bug in algorithm ? (i'm analyzing resulting expression left-to-right). — Preceding unsigned comment added by 5.20.182.75 (talk) 19:03, 13 January 2013 (UTC)

Parsing mathematical equations

The article states that the shunting-yard algorithm is a method for parsing mathematical equations. I'm not too versed in mathematics but it seems that the word "equations" imply the equality between two expressions. The thing is I don't see an equal signs in the infix input to the algorithm. Is it correct to say that equations are being parsed in this context? R4p70r (talk) 05:01, 18 February 2011 (UTC)

Indeed, it is probably not strictly correct. I would use the term "expressions". C3lticmatt (talk) 16:25, 28 March 2011 (UTC)

Prefix notation

I can make no sense of the sentence explaining prefix notation:

The shunting yard algorithm can also be applied to produce prefix notation (also known as polish notation). To do this one would simply start from the beginning of a string of tokens to be parsed and work backwards, and then reversing the output queue (therefore making the output queue an output stack).

Presumably the participle 'reversing' should be 'reverse'. But then how do you start at the beginning of a string and work backwards, without falling off the beginning of the string? Marinheiro (talk) 10:16, 8 December 2011 (UTC)

Python external link

Python implementation is not correct. I opened a bug with an original author: https://github.com/ekg/shuntingyard/issues/1 — Preceding unsigned comment added by Yuriyzubarev (talk • contribs) 19:46, 23 March 2012 (UTC)