Java を使用する必要があるため、スクリプト言語のサポートは使用しないでください。
解析する必要がある文字列表現は次のようになります。
op1 (t1,t2,t3,...)
ここで、t1、t2、t3 などは、原子単位のようなものでもop2 (t11,t12,t13 ...)、単なる原子単位でもかまいません (要素自体で構成することはできません)。
具体例は次のとおりです。
op1 (op2 (t1 t2) t3)
構造（階層）のようなツリーで解析したい
op1
op2
t1
t2
t3
op1 がツリーのルート、op2 が op1 の左側のサブチャイルド、t3 が op1 の右側のサブチャイルドであると仮定します。t1 と t2 は、それぞれ op2 の子です。
Javaでどうすればできますか？困難な部分は、結果のツリーがバイナリ ツリーであってはならないということです。ノードは、任意の数の子を持つことができます。
JavaCC を使用できない場合は、StringTokenizerクラスを調べることができます。数回のパスでそれを行うことができます。最初に、括弧でトークン化して、最初のパス ツリーを作成します。次に、ツリーをたどってスペースでトークン化し、リーフのみを持ち、ネストされたツリーを持たないノード (つまり、括弧を含む子がない) のツリー ノードをさらに肉付けすることができます。
op1 (op2 (t1 t2) t3)「(」および「)」でトークン化すると、トークンが提供されます (トークンを含めるように要求すると仮定します) op1, (, op2, (, t1 t2, ), t3, ) 。あなたはあなたの最初が親であることを知っています。2 番目は親であるため、複雑な子供がいることがわかります。あなたのツリーは次のようになります。
op1
op2
次に、新しい複雑な子を意味する別の括弧をヒットします。2 番目の開いた括弧の後の次のトークンはt1 t2、ツリーが
op1
op2
t1 t2
次に、近い親トークンを取得するため、op2 の複雑な子を終了し、次のトークンは op1 の次の子になります。つまり、ツリーは次のようになります。
op1
op2
t1 t2
t3
最後に、op1 の複雑な子を終了する最後の閉じ括弧をヒットします。
これで、子ノードをスペース上で分割しながら、ツリーをたどることができます。最初のノードは op1 であるため、op2 と同じように分割されません。「t1 t2」は「t1」と「t2」に分割されるため、そのノードを 2 つに分割することになり、ツリーは次のようになります。
op1
op2
t1
t2
t3
ツリーを 2 回歩く必要がないように、スペース分割を最初の方法に簡単に入れることができます。
まず、この問題を 2 つのサブ問題に分割することをお勧めします。1 つ目は入力の解析、2 つ目はツリーの作成です。
最初のものには文字列トークナイザーとスタックを使用できます。一般に問題は ((t1 t2) t3) のように見えるため、「op1」をスキップできます。したがって、現在の要素が = ")" になるときは、"(" に到達するまでスタックから要素をポップし、その要素から新しいノードを作成してスタックに戻す必要があります。スタックに格納しますが、明らかに文字列ではないため、そこに配置できる要素の階層を作成する必要があります。たとえば、StringElement、NodeElement、StartQuoteElement などです。
楽しみのためだけに、非常に迅速で非常に汚い、そして明らかにバグのあるソリューションです。ねえ、少なくともそれはあなたの例を解決します!!!!
package parser;
import java.util.Collection;
import java.util.ArrayList;
import java.util.Arrays;
/**
*
* @author gpeche
*/
public class Parser {
private static abstract class Node {
String name;
String getName() { return name; }
abstract boolean isComposite();
Node(String name) { this.name = name; }
}
private static class PrimitiveNode extends Node {
@Override boolean isComposite() { return false; }
PrimitiveNode(String name) { super(name); }
@Override public String toString() { return "PrimitiveNode(\"" + name + "\")"; }
}
private static class CompositeNode extends Node {
Collection<Node> children = new ArrayList<Node>();
void addChild(Node childNode) { children.add(childNode); }
Collection<Node> getChildren() { return new ArrayList<Node>(children); }
@Override boolean isComposite() { return false; }
CompositeNode(String name) { super(name); }
@Override public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("CompositeNode(\"");
sb.append(name);
sb.append("\") { ");
boolean isFirstNode = true;
for (Node node: children) {
if (!isFirstNode) {
sb.append(", ");
}
sb.append(node.toString());
isFirstNode = false;
}
sb.append(" }");
return sb.toString();
}
}
// Parser state
int pos = 0;
String[] tokens;
static final String OPENING_PAR = "(";
static final String CLOSING_PAR = ")";
static final String OP_PLUS = "+";
static final String OP_MINUS = "-";
static final String OP_MULTIPLY = "*";
static final String OP_DIVIDE = "/";
static final String OP_MODULUS = "mod";
static final String OP_INT_DIVIDE = "div";
static final Collection<String> PARENTHESIS = Arrays.asList(OPENING_PAR, CLOSING_PAR);
static final Collection<String> OPERATIONS = Arrays.asList( OP_PLUS,
OP_MINUS,
OP_MULTIPLY,
OP_DIVIDE,
OP_MODULUS,
OP_INT_DIVIDE);
public Node parse(String treeRepresentation) {
tokenize(treeRepresentation);
return parseNode();
}
private void tokenize(String treeRepresentation) {
treeRepresentation = treeRepresentation.replace("(", " ( ");
treeRepresentation = treeRepresentation.replace(")", " ) ");
tokens = treeRepresentation.split("\\s+");
}
private Node parseNode() {
// check that current token is not a "syntax" token
String currentToken = tokens[pos];
if (PARENTHESIS.contains(currentToken)) {
throw new IllegalArgumentException(String.format("Invalid token %d, expected identifier. got %s", pos + 1, currentToken));
}
boolean isComposite = currentToken != null &&
(currentToken.startsWith("op") || // Accept identifiers as operations (function support :P)
OPERATIONS.contains(currentToken));
return isComposite? parseComposite() : parsePrimitive();
}
private Node parseComposite() {
CompositeNode composite = new CompositeNode(tokens[pos]);
pos++;
if (!OPENING_PAR.equals(tokens[pos])) {
throw new IllegalArgumentException(String.format("Invalid token %d, expected '(', got %s", pos + 1, tokens[pos]));
} else {
// Ignore opening parenthesis
pos++;
}
boolean nextIsIdentifier;
do {
composite.addChild(parseNode());
nextIsIdentifier = !PARENTHESIS.contains(tokens[pos]);
} while (nextIsIdentifier);
if (!CLOSING_PAR.equals(tokens[pos])) {
throw new IllegalArgumentException(String.format("Invalid token %d, expected ')', got %s", pos + 1, tokens[pos]));
} else {
pos++;
}
return composite;
}
private Node parsePrimitive() {
// Create primitive node and advance position
Node result = new PrimitiveNode(tokens[pos]);
pos++;
return result;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Parser parser = new Parser();
Node parsedNode = parser.parse("op1 (op2 (t1 t2) t3)");
System.out.println(parsedNode.toString());
}
}