blob: 3d2a523e1c324c3d7085e6fb8890e8ef2301a2f2 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
package bjc.dicelang.expr;
import java.util.Deque;
import java.util.LinkedList;
import bjc.utils.funcdata.FunctionalList;
import bjc.utils.funcdata.IList;
/**
* Converts a infix series of tokens into a prefix series of tokens.
*
* @author Ben Culkin
*/
public class Shunter {
/**
* Convert a infix series of tokens to a postfix series of tokens.
*
* @param infixTokens
* The tokens in infix order.
*
* @return The tokens in postfix order.
*/
public static IList<Token> shuntTokens(final Token[] infixTokens) {
/* The returned tokens. */
final IList<Token> postfixTokens = new FunctionalList<>();
/* The current stack of operators. */
final Deque<Token> opStack = new LinkedList<>();
/* Shunt each token. */
for(final Token tok : infixTokens) {
/* Handle operators. */
if(tok.typ.isOperator) {
Token curOp = opStack.peek();
/*
* Check if an operator is higher priority,
* respecting their left associativity.
*
* @NOTE Should this be factored out into a
* method?
*/
int leftPriority = tok.typ.operatorPriority;
int rightPriority;
if(curOp == null) {
rightPriority = 0;
} else {
rightPriority = curOp.typ.operatorPriority;
}
boolean isHigherPrec = leftPriority >= rightPriority;
/*
* Pop all operators that are lower precedence
* than us.
*/
while(!opStack.isEmpty() && isHigherPrec) {
postfixTokens.add(opStack.pop());
curOp = opStack.peek();
leftPriority = tok.typ.operatorPriority;
if(curOp == null) {
rightPriority = 0;
} else {
rightPriority = curOp.typ.operatorPriority;
}
isHigherPrec = leftPriority >= rightPriority;
}
opStack.push(tok);
} else if(tok.typ == TokenType.OPAREN) {
opStack.push(tok);
} else if(tok.typ == TokenType.CPAREN) {
Token curOp = opStack.peek();
/*
* Pop things until we find the matching
* parenthesis.
*/
while(curOp.typ != TokenType.OPAREN) {
final Token tk = opStack.pop();
postfixTokens.add(tk);
curOp = opStack.peek();
}
if(!opStack.isEmpty()) {
opStack.pop();
}
} else {
postfixTokens.add(tok);
}
}
/*
* Flush remaining operators.
*/
while(!opStack.isEmpty()) {
postfixTokens.add(opStack.pop());
}
return postfixTokens;
}
}
|
