blob: bbece0f117144f17d831569eb35d4f2080f3c8c3 (
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.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 {
/**
* 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(Token[] infixTokens) {
List<Token> postfixTokens = new ArrayList<>(infixTokens.length);
Deque<Token> opStack = new LinkedList<>();
/*
* Shunt each token.
*/
for(Token tok : infixTokens) {
/*
* Handle operators.
*/
if(tok.type.isOperator) {
Token curOp = opStack.peek();
/*
* Check if an operator is higher priority,
* respecting their left associativity.
*/
int leftPriority = tok.type.operatorPriority;
int rightPriority;
if(curOp == null)
rightPriority = 0;
else
rightPriority = curOp.type.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.type.operatorPriority;
if(curOp == null)
rightPriority = 0;
else
rightPriority = curOp.type.operatorPriority;
isHigherPrec = leftPriority >= rightPriority;
}
opStack.push(tok);
} else if(tok.type == TokenType.OPAREN) {
opStack.push(tok);
} else if(tok.type == TokenType.CPAREN) {
Token curOp = opStack.peek();
/*
* Pop things until we find the matching
* parenthesis.
*/
while(curOp.type != TokenType.OPAREN) {
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]);
}
}
|
