blob: 213e4736d4fceebf7131e9209898947063b5c06d (
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
106
107
108
109
110
|
package bjc.dicelang.expr;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
/**
* Converts a infix series of tokens into a prefix series of tokens.
*
* @author Ben Culkin
*/
public class Shunter {
/*
* @NOTE
* Why does this method return an array, and not the list of
* tokens?
*/
/**
* 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 Token[] shuntTokens(final Token[] infixTokens) {
/* The returned tokens. */
final List<Token> postfixTokens = new ArrayList<>(infixTokens.length);
/* 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.toArray(new Token[0]);
}
}
|
