我需要使用 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, ) 从中您可以遍历标记。你知道你的第一个是父母。其次是父母，所以你知道你有一个复杂的孩子。所以你的树是：
op1
op2
然后你打了另一个paren，意思是一个新的复杂的孩子。第二个开放括号之后的下一个标记是t1 t2你的树
op1
op2
t1 t2
然后你得到一个接近的括号标记，所以你结束了 op2 的复杂子代，你的下一个标记是 op1 的下一个子代，这意味着你的树看起来像
op1
op2
t1 t2
t3
最后，您点击了最后一个关闭括号，它结束了 op1 的复杂子代。
现在您可以遍历树，在空间上拆分子节点。第一个节点是 op1，所以没有分裂，与 op2 相同。't1 t2' 分裂成 't1' 和 't2' 所以你最终将该节点分成两个所以你的树看起来像
op1
op2
t1
t2
t3
您可能可以轻松地将空间拆分放入第一种方法中，这样您就不必两次遍历树。
首先，我建议您将此问题拆分为两个子问题，第一个 - 解析输入，第二个 - 创建树。
您可以对第一个使用字符串标记器和堆栈，您可以跳过“op1”，因为通常您的问题看起来像 ((t1 t2) t3)。因此，当您当前的元素将是 = ")" 时，您应该从堆栈中弹出元素，直到您到达 "(" 并从该元素中创建新节点并将其放回堆栈。另一个问题是您的数据类型是什么将存储在堆栈中，显然它不会是字符串，因此您可能必须创建一些可以放置在那里的元素层次结构，例如 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());
}
}