广义表的简单理解在这篇博文中：https://blog.csdn.net/lishanleilixin/article/details/87364496，在此不做赘述。
Java实现广义表：
package 广义表;
import java.util.Stack;
public class Test {
public final int TAG_TABLE = 1;
public final int TAG_ITEM = 0;
private char mStartSymb = '(';
private char mEndSymb = ')';
private Node mGenTable;
class Node {
int tag;
Object data;
Node mPh;
Node mPt;
public Node(Node ph, Node pt, int tag, Object data) {
this.mPh = ph;
this.mPt = pt;
this.tag = tag;
this.data = data;
}
}
public Test(String genTable) {
if(genTable == null)
throw new NullPointerException("genTable is null");
initTable(genTable);
}
public Test() {
mGenTable = new Node(null, null, TAG_TABLE, null);
}
public Test(Test b) {
if(b != null) {
mGenTable = b.mGenTable;
}
}
public void initTable(String genTable) {
String ts = genTable.replaceAll("\\s", "");
int len = ts.length();
Stack<Character> symStack = new Stack<Character>();
Stack<Node> nodeStack = new Stack<Node>();
initSymbolicCharactor(ts);
mGenTable = new Node(null, null, TAG_TABLE, null);
Node itemNode, tableNode = mGenTable, tmpNode;
for (int i = 0; i < len; i++) {
if(ts.charAt(i) == mStartSymb) {
tmpNode = new Node(null, null ,TAG_TABLE, null);
symStack.push(ts.charAt(i));
if(symStack.size() > 1) {
nodeStack.push(tableNode);
tableNode.mPh = tmpNode;
tableNode = tableNode.mPh;
}
else {
tableNode.mPt = tmpNode;
tableNode = tableNode.mPt;
}
}
else if(ts.charAt(i) == mEndSymb) {
if(symStack.isEmpty()) {
throw new NullPointerException(
"IllegalArgumentException in constructor GeneralizedTable!...");
}
if(symStack.size() > 1) {
tableNode = nodeStack.pop();
}
symStack.pop();
}
else if(ts.charAt(i) == ',') {
tableNode.mPt = new Node(null, null, TAG_TABLE, null);
tableNode = tableNode.mPt;
}
else {
itemNode = new Node(null, null, TAG_ITEM, ts.charAt(i));
tableNode.mPh = itemNode;
}
}
if(!symStack.isEmpty()) {
throw new NullPointerException(
"IllegalArgumentException in constructor GeneralizedTable!...");
}
}
public void initSymbolicCharactor(String ts) {
mStartSymb = ts.charAt(0);
switch (mStartSymb) {
case '(':
mEndSymb = ')';
break;
case '{':
mEndSymb = '}';
break;
case '[':
mEndSymb = ']';
break;
default:
throw new IllegalArgumentException(
"IllegalArgumentException ---> initSymbolicCharactor");
}
}
public void print() {
print(mGenTable);
}
private void print(Node node) {
if(node == null) return;
if(node.tag == 0) System.out.print(node.data.toString() + "\t");
print(node.mPh);
print(node.mPt);
}
public int depth() {
if(mGenTable == null)
throw new NullPointerException("Generalized Table is null !.. ---> method depth");
return depth(mGenTable);
}
private int depth(Node node) {
if(node == null || node.tag == 0) return 0;
int depHeader = 0, depTear = 0;
depHeader = 1 + depth(node.mPh);
depTear = depth(node.mPt);
return depHeader > depTear ? depHeader : depTear;
}
public int length() {
if(mGenTable == null || mGenTable.mPt == null) return -1;
int len = 0;
Node node = mGenTable;
while(node.mPt != null) {
node = node.mPt;
if(node.mPh == null && node.mPt == null) break;
len++;
}
return len;
}
public Test getHeader() {
if(isEmpty()) return null;
Node node = mGenTable.mPt;
Test test = new Test();
test.mGenTable.mPt = node.mPh;
return test;
}
public Test getTear() {
if(mGenTable == null) return null;
Node node = mGenTable.mPt;
Test test = new Test();
test.mGenTable.mPt = node.mPt;
return test;
}
public boolean isEmpty() {
if(mGenTable == null) return true;
Node node = mGenTable.mPt;
return node.mPh == null || node.mPt == null;
}
public static void main(String[] args) {
Test test = new Test("(c,a,b,(a,b,c),(a,(a,b),c))");
test.print();
System.out.println();
System.out.println("该广义表的深度为:" + test.depth());
System.out.println("该广义表的长度为:" + test.length());
Test t2 = test.getTear();
t2.print();
}
}