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
111
112
113
114
115
116
117
|
package bjc.utils.parserutils;
import java.util.Deque;
import java.util.LinkedList;
import java.util.function.Function;
import java.util.function.Predicate;
import bjc.utils.data.GenHolder;
import bjc.utils.data.Pair;
import bjc.utils.funcdata.FunctionalList;
/**
* Creates a parse tree from a postfix expression
*
* @author ben
*
*/
public class TreeConstructor {
/**
* Construct a tree from a list of tokens in postfix notation
*
* Only binary operators are accepted.
*
* @param <T>
* The elements of the parse tree
* @param tokens
* The list of tokens to build a tree from
* @param operatorPredicate
* The predicate to use to determine if something is a
* operator
* @return A AST from the expression
*
* @deprecated Use
* {@link TreeConstructor#constructTree(FunctionalList, Predicate, Predicate, Function)}
* instead
*/
public static <T> AST<T> constructTree(FunctionalList<T> tokens,
Predicate<T> operatorPredicate) {
return constructTree(tokens, operatorPredicate, (op) -> false,
null);
}
/**
* Construct a tree from a list of tokens in postfix notation
*
* Only binary operators are accepted.
*
* @param <T>
* The elements of the parse tree
* @param tokens
* The list of tokens to build a tree from
* @param operatorPredicate
* The predicate to use to determine if something is a
* operator
* @param isSpecialOperator
* The predicate to use to determine if an operator needs
* special handling
* @param handleSpecialOperator
* The function to use to handle special case operators
* @return A AST from the expression
*
* FIXME The handleSpecialOp function seems like an ugly
* interface. Maybe there's a better way to express how that
* works
*/
public static <T> AST<T> constructTree(FunctionalList<T> tokens,
Predicate<T> operatorPredicate, Predicate<T> isSpecialOperator,
Function<Deque<AST<T>>, AST<T>> handleSpecialOperator) {
GenHolder<Pair<Deque<AST<T>>, AST<T>>> initialState =
new GenHolder<>(new Pair<>(new LinkedList<>(), null));
tokens.forEach((element) -> {
if (operatorPredicate.test(element)) {
initialState.transform((pair) -> {
Deque<AST<T>> queuedASTs =
pair.merge((queue, currentAST) -> queue);
AST<T> mergedAST = pair.merge((queue, currentAST) -> {
AST<T> newAST;
if (isSpecialOperator.test(element)) {
newAST = handleSpecialOperator.apply(queue);
} else {
AST<T> rightAST = queue.pop();
AST<T> leftAST = queue.pop();
newAST = new AST<>(element, leftAST, rightAST);
}
queue.push(newAST);
return newAST;
});
Pair<Deque<AST<T>>, AST<T>> newPair =
new Pair<>(queuedASTs, mergedAST);
return newPair;
});
} else {
AST<T> newAST = new AST<>(element);
initialState.doWith(
(pair) -> pair.doWith((queue, currentAST) -> {
queue.push(newAST);
}));
initialState.transform((pair) -> {
return (Pair<Deque<AST<T>>, AST<T>>) pair.apply(
(queue) -> queue, (currentAST) -> newAST);
});
}
});
return initialState.unwrap(
(pair) -> pair.merge((queue, currentAST) -> currentAST));
}
}
|
