Applications of Queues
and Stacks
Sridhar Alagar
Shunting Yard Algorithm
• Infix notation: humans understand well
• Postfix notation: expression can be unambiguously evaluated
• Shunting yard algorithm: convert exp. in infix to postfix
CS 6301 IDSA 2
Shunting Yard: Example
CS 6301 IDSA 3
Input
3+4*5/(2+1)^2
Output (queue)
Stack
Current token is operand
add to output queue
Shunting Yard: Example
CS 6301 IDSA 4
Input
+4*5/(2+1)^2
Output (queue)
3
Stack
Current token is operator
stack is empty
push to stack
Shunting Yard: Example
CS 6301 IDSA 5
Input
4*5/(2+1)^2
Output (queue)
3
+
Stack
Current token is operand
add to output queue
Shunting Yard: Example
CS 6301 IDSA 6
Input
*5/(2+1)^2
Output (queue)
34
+
Stack
Current token is operator
top of stack has lower precedence op
push token
Shunting Yard: Example
CS 6301 IDSA 7
Input
5/(2+1)^2
Output (queue)
34
*+
Stack
Current token is operand
add to output queue
Shunting Yard: Example
CS 6301 IDSA 8
Input
/(2+1)^2
Output (queue)
345
*+
Stack
Current token is operator
top of stack has equal precedence op
but left associative
pop to output queue
Shunting Yard: Example
CS 6301 IDSA 9
Input
/(2+1)^2
Output (queue)
345*
+
Stack
Current token is operator
top of stack has lower precedence op
push token
Shunting Yard: Example
CS 6301 IDSA 10
Input
(2+1)^2
Output (queue)
345*
/+
Stack
Current token is ‘(‘
push token
Shunting Yard: Example
CS 6301 IDSA 11
Input
2+1)^2
Output (queue)
345*
(/+
Stack
Current token is operand
add to output queue
Shunting Yard: Example
CS 6301 IDSA 12
Input
+1)^2
Output (queue)
345*2
(/+
Stack
Current token is operator
top of stack is ‘(‘
push token
Shunting Yard: Example
CS 6301 IDSA 13
Input
1)^2
Output (queue)
345*2
+(/+
Stack
Current token is operand
add it to output queue
Shunting Yard: Example
CS 6301 IDSA 14
Input
)^2
Output (queue)
345*21
+(/+
Stack
Current token is ‘)’
pop stack to output till top == ‘(‘
pop ‘(‘ and discard
discard token
Shunting Yard: Example
CS 6301 IDSA 15
Input
^2
Output (queue)
345*21+
/+
Stack
Current token is operator
top of stack has lower precedence op
push token
Shunting Yard: Example
CS 6301 IDSA 16
Input
2
Output (queue)
345*21+
^/+
Stack
Current token is operand
add to output queue
Shunting Yard: Example
CS 6301 IDSA 17
Output (queue) Input
345*21+2
^/+
Stack
No more tokens
pop stack to output till empty
Shunting Yard: Example
CS 6301 IDSA 18
Input
3+4*5/(2+1)^2
Output (queue)
345*21+2^/+
Stack
Shunting Yard Algorithm
19
while next token t not null {
if t is an operand
add to output queue
else if t is an operator
while (stack top has higher precedence or
equal precedence but left associative)
pop stack to output queue
push t
else if t is ‘(‘
push t
else if t is ‘)’
while stack top is not ‘(‘
pop stack top to output queue
pop and discard // if not ‘(‘, error
} // end while
pop the remaining operators from stack to output
Recursive Descent Parser
• What does a parser do?
• Given grammar G, and string s.
• Does s belong to the language generated by G?
• Parser for G will verify, and if so, construct a derivation tree or
evaluate it.
CS 6301 IDSA 20
Parser
CS 6301 IDSA 21
| Tokenizer | tokens |
| Parser | AST |
Back end of
compiler
input string
Grammar for Arithmetic Expression
22
E -> E addop T | T
T -> T multop F | F
F -> (E) | num
addop -> +|-
multop -> *|/
num -> digit num | digit
digit -> 0|1|…|9
Few Observations about the grammar:
E is the start symbol
has terminal and non-terminal symbols
lhs has only non-terminal symbols
production rules on rhs
Goal: Write a parser for this grammar.
Derivation Tree for a given input
23
E -> E addop T | T
T -> T multop F | F
F -> (E) | num
addop -> +|-
multop -> *|/
num -> digit num | digit
digit -> 0|1|…|9
Input = 3+4*2
How to write a parser for the grammar?
24
E -> E addop T | T
T -> T multop F | F
F -> (E) | num
addop -> +|-
multop -> *|/
num -> digit num | digit
digit -> 0|1|…|9
One method for every non-terminal
For every non-terminal in the production
rule (rhs) its method is invoked
Terminal on the rhs leads to
consuming/evaluating the token
Is there a problem with the left
recursion in the grammar?
Avoid left recursion
25
E -> E addop T | T
T -> T multop F | F
F -> (E) | num
addop -> +|-
multop -> *|/
num -> digit num | digit
digit -> 0|1|…|9
E -> T {addop T}*
T -> F {multop F}*
F -> (E) | num
addop -> +|-
multop -> *|/
num -> digit num | digit
digit -> 0|1|…|9
Parser for evaluating an arithmetic exp.
• Input to the parser: tokens – Queue <String>
• Output is evaluated value of the input
• Every method for non-terminal returns a integer value
CS 6301 IDSA 26
Method to evaluate E
27
int evalE(Queue<String> qt){
int val1 = evalT(qt);
while((qt.peek().equals(“+”) ||
(qt.peek().equals(“-”)){
String oper = qt.remove();
int val2 = evalT(qt);
if(oper.equals(“+”))
val1 += val2;
else val1 -= val2
}
return val1;
}
E -> T {addop T}*
T -> F {multop F}*
F -> (E) | num
addop -> +|-
multop -> *|/
num -> digit num | digit
digit -> 0|1|…|9
Method to evaluate T
28
int evalT(Queue<String> qt){
int val1 = evalF(qt);
while((qt.peek().equals(“*”) ||
(qt.peek().equals(“/”)){
String oper = qt.remove();
int val2 = evalF(qt);
if(oper.equals(“*”))
val1 *= val2;
else val1 /= val2
}
return val1;
}
E -> T {addop T}*
T -> F {multop F}*
F -> (E) | num
addop -> +|-
multop -> *|/
num -> digit num | digit
digit -> 0|1|…|9
Method to evaluate F
29
int evalF(Queue<String> qt){
if((qt.peek().equals(“(”){
String oper = qt.remove();
int val = evalE(qt);
oper = qt.remove(); //”)”
}
else {
String num = qt.remove();
val = Integer.parseInt(num);
}
return val;
}
E -> T {addop T}*
T -> F {multop F}*
F -> (E) | num
addop -> +|-
multop -> *|/
num -> digit num | digit
digit -> 0|1|…|9
References
https://en.wikipedia.org/wiki/Shunting-yard_algorithm
https://en.wikipedia.org/wiki/Recursive_descent_parser
CS 6301 IDSA 30