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
|
package bjc.utils.parserutils;
import java.util.Deque;
import java.util.LinkedList;
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
*
* @param <T>
* The elements of the parse tree
*/
public class TreeConstructor {
/**
* Construct a tree from a list of tokens in postfix notation
*
* Only binary operators are accepted.
*
* @param toks
* The list of tokens to build a tree from
* @param opPredicate
* The predicate to use to determine if something is a
* operator
* @return A AST from the expression
*/
public static <T> AST<T> constructTree(FunctionalList<T> toks,
Predicate<T> opPredicate) {
GenHolder<Pair<Deque<AST<T>>, AST<T>>> initState =
new GenHolder<>(new Pair<>(new LinkedList<>(), null));
toks.forEach((ele) -> {
if (opPredicate.test(ele)) {
initState.transform((par) -> {
Deque<AST<T>> lft = par.merge((deq, ast) -> deq);
AST<T> mergedAST = par.merge((deq, ast) -> {
AST<T> right = deq.pop();
AST<T> left = deq.pop();
AST<T> newAST = new AST<T>(ele, left, right);
deq.push(newAST);
return newAST;
});
Pair<Deque<AST<T>>, AST<T>> newPair =
new Pair<>(lft, mergedAST);
return newPair;
});
} else {
AST<T> newAST = new AST<>(ele);
initState.doWith((par) -> par.doWith((deq, ast) -> {
deq.push(newAST);
}));
initState.transform((par) -> {
return (Pair<Deque<AST<T>>, AST<T>>) par
.apply((d) -> d, (a) -> newAST);
});
}
});
return initState.unwrap((par) -> par.merge((deq, ast) -> ast));
}
}
|
