Stack Overflow
Stack Overflow

Questions tagged [shunting-yard]

The Dijkstra Shunting-yard algorithm is a very general, linear time, stack-based algorithm for parsing mathematical expressions.

The Dijkstra Shunting-yard algorithm is a very general, linear time, stack-based algorithm for parsing mathematical expressions specified in infix notation. It can be used to produce output in Reverse Polish notation (RPN) or as an abstract syntax tree (AST). It was invented by the Dutch computer science Edsger Dijkstra, and published in 1960. He named it the "shunting yard" algorithm because its operation resembles that of a railroad shunting yard.

It is not used in most production compilers, as they already have more general parsing systems that include arithmetic expressions as a special case. It is very widely used as a teaching exercise, and it can be used in compilers for special languages where the programmer can add operators or redefine operator precedence, which are easily made variable in the algorithm, unlike the parsers generally used in production compilers.

Wikipedia page

124 questions
26
votes
7 answers

How can I modify my Shunting-Yard Algorithm so it accepts unary operators?

I've been working on implementing the Shunting-Yard Algorithm in JavaScript for class. Here is my work so far: var userInput = prompt("Enter in a mathematical expression:"); var postFix = InfixToPostfix(userInput); var result =…
KingNestor
  • 65,976
  • 51
  • 121
  • 152
12
votes
1 answer

Abstract syntax tree using the shunting yard algorithm

I have an infix expression that I have tokenised and would like to proceed to create an abstract syntax tree. I understand the shunting-yard algorithm used in these cases. I have only found ways to convert the infix expression to RPN format, not…
user27114
  • 129
  • 1
  • 3
12
votes
2 answers

unary minus in shunting yard expression parser

here is my expression parser using shunting-yard algorithm it work well as expected except in one situation , when I use unary minus like in -2*3 it wont work (I think it shouldn't because I didn't find anything in algorithm to handle this ) is…
PedramH
  • 123
  • 1
  • 8
11
votes
2 answers

Shunting-Yard Validate Expression

We use the Shunting-Yard algorithm to evaluate expressions. We can validate the expression by simply applying the algorithm. It fails if there are missing operands, miss-matched parenthesis, and other things. The Shunting-Yard algorithm however…
denver
  • 2,863
  • 2
  • 31
  • 45
10
votes
2 answers

handling unary minus for shunting-yard algorithm

Is there a better way to handle unary "-" in converting a infix expression to a postfix one? The obvious one would be prefix every unary "-" with a 0. Does anyone know better implementation? Thanks!
JASON
  • 7,371
  • 9
  • 27
  • 40
8
votes
5 answers

Problems with a shunting yard algorithm

I have successfully implemented a shunting yard algorithm in java. The algorithm itself was simple however I am having trouble with the tokenizer. Currently the algorithm works with everything I want excluding one thing. How can I tell the…
The Dude
  • 310
  • 7
  • 15
8
votes
4 answers

How to count number of arguments of a method while converting infix expression to reverse polish notation

I have an expression like below. MIN(MAX(AVG(AVG(4,2),2,3),SUM(1,2))) I have implemented shunting yard algorithm to convert infix to reversed polish notation. I add the function MAX , MIN and AVG with two arguments. But suppose if I want to…
Bankelaal
  • 408
  • 1
  • 9
  • 24
8
votes
3 answers

Infix to postfix algorithm that takes care of unary operators

The I/p to the algo will be an expression like this: a+(-b) a*-b+c i.e any expression that a standard C compiler would support. Now I've the input already formatted as a stream of tokens , the tokens contain info whether its an operator or an…
Aditya
  • 310
  • 1
  • 3
  • 11
7
votes
9 answers

Efficiency of stack-based expression evaluation for math parsing

I have to write, for academic purposes, an application that plots user-input expressions like: f(x) = 1 - exp(3^(5*ln(cosx)) + x) The approach I've chosen to write the parser is to convert the expression in RPN with the Shunting-Yard algorithm,…
Davide Valdo
  • 779
  • 8
  • 21
6
votes
4 answers

Trouble understanding what to do with output of shunting-yard algorithm

I've been looking at the wiki page: http://en.wikipedia.org/wiki/Shunting-yard_algorithm I've used the code example to build the first part, basically I can currently turn : 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 into 3 4 2 * 1 5 − 2 3 ^ ^ / + But I don't…
Patrick Lorio
  • 5,520
  • 11
  • 45
  • 74
6
votes
1 answer

Shunting yard algorithm with functions

my first post here :) I saw that there are a lot of questions about the Shunting yard algorithm but I hope there still are forum members that interested to help me with yet another question about this algorithm. I did search trough the other posts…
Tom
  • 221
  • 1
  • 4
  • 16
6
votes
1 answer

Shunting yard algorithm for immediate evaluation

Generally, programs which evaluate an infix mathematical expression use some variation of the Shunting Yard Algorithm to first translate the expression into Reverse Polish Notation, and then evaluate the Reverse Polish Notation to get a single final…
Siler
  • 8,976
  • 11
  • 64
  • 124
6
votes
1 answer

Arithmetic Expression Evaluation using Reverse Polish Notation (RPN)

A mathematical expression is usually expressed in infix notation. For evaluation purposes, we can change it to postfix (reverse polish) notation (using algorithms like Shunting-Yard) and then evaluate the postfix notation using stack. I found out…
ManiAm
  • 1,759
  • 5
  • 24
  • 43
6
votes
1 answer

Handling extra operators in Shunting-yard

Given an input like this: 3+4+ Algorithm turns it in to 3 4 + + I can find the error when it's time to execute the postfix expression. But, is it possible to spot this during the conversion? (Wikipedia article and internet articles I've read do not…
mikbal
  • 1,168
  • 1
  • 16
  • 27
5
votes
0 answers

Can the shunting-yard algorithm be used to parse expressions containing a mix of logical, comparison and arithmetic operators?

According to Wikipedia the shunting-yard algorithm is used to parse mathematical expressions. But is there any reason it could not be used with a mix of logical and arithmetic expressions, as well as comparisons? As an example, could one use it to…
Alex
  • 1,157
  • 3
  • 11
  • 25
1
2 3
…
8 9