blob: 3dc10eac68021ae00fc05c6694b2b35d23db656e (
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
package bjc.dicelang.expr;
import java.util.Arrays;
import java.util.Scanner;
import bjc.utils.data.ITree;
import bjc.utils.funcdata.FunctionalList;
import bjc.utils.parserutils.TreeConstructor;
/**
* Parser for simple math expressions.
*
* @author Ben Culkin
*/
public class Parser {
/*
* @TODO 10/08/17 Ben Culkin :MainSeperation This main method should be moved to
* its own class.
*/
/**
* Main method.
*
* @param args
* Unused CLI args.
*/
public static void main(final String[] args) {
/* Create our objects. */
final Tokens toks = new Tokens();
final Lexer lex = new Lexer();
/* Prepare our input source. */
final Scanner scan = new Scanner(System.in);
/* Read initial command. */
System.out.print("Enter a math expression (blank line to quit): ");
String ln = scan.nextLine().trim();
/* Enter REPL loop. */
while (!ln.equals("")) {
/* Print raw command. */
System.out.println("Raw command: " + ln);
System.out.println();
/* Lex command to infix tokens. */
final Token[] infixTokens = lex.lexString(ln, toks);
System.out.println("Lexed tokens: ");
for (final Token tok : infixTokens) {
System.out.println("\t" + tok);
}
/* Print out infix expression. */
System.out.print("Lexed expression: ");
for (final Token tok : infixTokens) {
System.out.print(tok.toExpr() + " ");
}
/* Space stages. */
System.out.println();
System.out.println();
/* Shunt infix tokens to postfix tokens. */
final Token[] postfixTokens = Shunter.shuntTokens(infixTokens);
System.out.println("Lexed tokens: ");
for (final Token tok : postfixTokens) {
System.out.println("\t" + tok);
}
/* Print out postfix tokens. */
System.out.print("Shunted expression: ");
for (final Token tok : postfixTokens) {
System.out.print(tok.toExpr() + " ");
}
/* Space stages. */
System.out.println();
System.out.println();
/* Construct a list from the array of tokens. */
final FunctionalList<Token> tokList = new FunctionalList<>(Arrays.asList(postfixTokens));
/* Construct a tree from the list of postfixed tokens. */
final ITree<Token> ast = TreeConstructor.constructTree(tokList, tok -> tok.typ.isOperator);
/* Print the tree, then the canonical expression for it. */
System.out.println("Parsed tree");
System.out.println(ast.toString());
System.out.println("\nCanonical expr: " + toCanonicalExpr(ast));
/* Space stages. */
System.out.println();
System.out.println();
/* Prompt for a new expression. */
System.out.print("Enter a math expression (blank line to quit): ");
/* Read it. */
ln = scan.nextLine().trim();
}
/* Cleanup after ourselves. */
scan.close();
}
/*
* Convert an expression to one that uses the smallest necessary amount of
* parens.
*/
private static String toCanonicalExpr(final ITree<Token> ast) {
final Token data = ast.getHead();
if (ast.getChildrenCount() == 0) {
/* Handle leaf nodes. */
return data.toExpr();
}
/* The left/right children. */
final ITree<Token> left = ast.getChild(0);
final ITree<Token> right = ast.getChild(1);
/* Recursively canonicalize them. */
String leftExpr = toCanonicalExpr(left);
String rightExpr = toCanonicalExpr(right);
/* Add parens if the left was higher priority. */
if (left.getChildrenCount() == 0) {
int leftPriority = left.getHead().typ.operatorPriority;
int dataPriority = data.typ.operatorPriority;
if (leftPriority >= dataPriority) {
leftExpr = String.format("(%s)", leftExpr);
}
}
/* Add parens if the right was higher priority. */
if (right.getChildrenCount() == 0) {
int rightPriority = right.getHead().typ.operatorPriority;
int dataPriority = data.typ.operatorPriority;
if (rightPriority >= dataPriority) {
rightExpr = String.format("(%s)", rightExpr);
}
}
return String.format("%s %s %s", leftExpr, data.toExpr(), rightExpr);
}
}
|
