广义表是对线性表的扩展――线性表存储的所有的数据都是原子的（一个数或者不可分割的结构），且所有的数据类型相同。而广义表是允许线性表容纳自身结构的数据结构。
广义表定义：
广义表是由n个元素组成的序列：LS = （a1，a2, ... an）;其中 ai是一个原子项或者是一个广义表。n是广义表的长度。若ai是广义表，则称为LS的子表。
广义表表头和表尾： 若广义表LS不空，则a1，称为LS的表头，其余元素组成的子表称为表尾。
广义表的长度： 若广义表不空，则广义表所包含的元素的个数，叫广义表的长度。
广义表的深度： 广义表中括号的最大层数叫广义表的深度。
例如：
对广义表LS=((),a,b,(a,b,c),(a,(a,b),c))
表头为子表LSH = ();
表尾为子表LST = (a,b,(a,b,c),(a,(a,b),c));
广义表LS的长度：5
广义表LS的深度：3
对于广义表的操作都是建立在已经构建好的广义表上，那么如何通过一个广义表字符串构造一个广义表？
广义表的存储结构――广义表有多重存储结构，以下只讲代码中使用的存储结构，代码中采用以下存储结构：
| tag | data | pH | pT |
tag ：tag == 0 ； 表示该节点为原子节点 。tag == 1 ； 表示该节点为表节点
data ：data是原子节点的数据，为表节点时该值域无效。
pH ：广义表的表头――是一个表节点或原子节点。
pT ：广义表的表尾――必定是一个表节点 或者 null。
表节点存储结构选择好了，那么如何来构造广义表呢？（比如：LS = ((),a,b,(a,b,c),(a,(a,b),c))）， 根据以下规则，构造出来的广义表如下图：
header表示表头 ， 带圈的指针表示由该符号创建的对应的节点（为了图片清晰有些节点没有画）。
对于一个广义表总有一个header节点指向该表的表节点，一个node表示当前正在操作的节点。
< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+tbHT9rW9oa4ooa8gyrG5udTs0ru49rHtvdq146OssqLH0r2ruMO3+7rF0bnVu2NoYXJTdGFja6OsyOe5+9W71tC1xMr9vt2zpLbIID4gMSCjrCCx7cP3uePS5bHttcTJ7rbIvNPJ7tK7suMgo6y0y8qxvau4w73atePRucjr1btub2RlU3RhY2ujrLKix9LIw25vZGW1xHBIvdq149a4z/LQwrm51Oy1xL3ateOho8bktPrC68jnz8KjujwvcD4KPHA+PC9wPgo8cHJlIGNsYXNzPQ=="brush:java;">if (ts.charAt(i) == mStartSymb) { tmpNode = new Node(null, null, TAG_TABLE, null); // tableNode = tableNode.mPt; symbStack.push(ts.charAt(i)); if (symbStack.size() > 1) { nodeStck.push(tableNode); tableNode.mPh = tmpNode; tableNode = tableNode.mPh; } else { tableNode.mPt = tmpNode; tableNode = tableNode.mPt; } } 其中mStartSymb 表示广义表的 '表起始指示符' ， symbStack.push(ts.charAt(i));将 '表起始指示符压栈' ， 接下来判断symbStack栈的大小，代码：
nodeStck.push(tableNode); tableNode.mPh = tmpNode; tableNode = tableNode.mPh;将当前的表节点压栈 ， 接着表头指向新的node ， 当前节点向前滑动一个位置。
当遇到原子节点符号(如：’a‘) 时，则创建一个原子节点，并且让表头指向该节点，其代码如下：
else {
itemNode = new Node(null, null, TAG_ITEM, ts.charAt(i));
tableNode.mPh = itemNode;
}
当遇到符号 ’,‘ 时构造一个表节点，让当前节点的表尾指向新的节点，其代码如下：
else if (ts.charAt(i) == ',') {
tableNode.mPt = new Node(null, null, TAG_TABLE, null);
tableNode = tableNode.mPt;
}
当遇到符号 ')' 时，做两件事
1、如果 symbStack 的长度 > 1 , 表明此时并没有回到表的最外层，肯定存在一个nodeStack中的节点需要出栈，接着让与之对应的 ’(‘ 符号出栈，其代码如下：
else if (ts.charAt(i) == mEndSymb) {
if (symbStack.isEmpty()) {
throw new IllegalArgumentException(
"IllegalArgumentException in constructor GeneralizedTable!...");
}
if (symbStack.size() > 1) {
tableNode = nodeStck.pop();
}
symbStack.pop();
}
当表字符串结束，切symStack的长度为0时，表明是一个格式正确的表字符串，否则说明该表字符串的格式错误，不予处理。
至此，一个广义表就构造OK了。根据上述原理，构造一个广义表的完整代码如下：
public GeneralizedTable(String genTable) {
if (genTable == null) {
throw new NullPointerException(
"genTable is null in constructor GeneralizedTable!...");
}
initTable(genTable);
}
private void initTable(String genTable) {
String ts = genTable.replaceAll("\\s", "");
int len = ts.length();
Stack
symbStack = new Stack
(); Stack
nodeStck = new Stack
(); 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); // tableNode = tableNode.mPt; symbStack.push(ts.charAt(i)); if (symbStack.size() > 1) { nodeStck.push(tableNode); tableNode.mPh = tmpNode; tableNode = tableNode.mPh; } else { tableNode.mPt = tmpNode; tableNode = tableNode.mPt; } } else if (ts.charAt(i) == mEndSymb) { if (symbStack.isEmpty()) { throw new IllegalArgumentException( "IllegalArgumentException in constructor GeneralizedTable!..."); } if (symbStack.size() > 1) { tableNode = nodeStck.pop(); } symbStack.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 (!symbStack.isEmpty()) { throw new IllegalArgumentException( "IllegalArgumentException in constructor GeneralizedTable!..."); } } private 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"); } }
注释：本代码中支持 ( , ) , { , } , [ , ] 为"广义表标示符"的广义表字符串（默认是()）。
求广义表的长度： 根据广义表长度的定义，该表的长度，等于原子节点或表节点的个数，即 header.pT != null 的个数 ， 其代码如下：
public int length() { // 广义表的长度
if (mGenTable == null || mGenTable.mPt == null) {
return -1;
}
int tLen = 0;
Node node = mGenTable;
while (node.mPt != null) {
node = node.mPt;
if (node.mPh == null && node.mPt == null) {
break;
}
tLen++;
}
return tLen;
}
广义表的深度：因为广义表由 表头 和 表尾 组成 ， 所以 ， 广义表的深度是 表头、表尾中的最大深度。由此定义，得到如下代码：
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.mTag == TAG_ITEM) {
return 0;
}
int depHeader = 0, depTear = 0;
depHeader = 1 + depth(node.mPh);
depTear = depth(node.mPt);
return depHeader > depTear depHeader : depTear;
}
广义表的表头：广义表的第一项称为表头，表头可能是一个原子项和广义表。但是不管如何，他都是第一个的pH指向的内容：其代码如下：
public GeneralizedTable getHeader() {
if (isEmpty())
return null;
Node node = mGenTable.mPt;
GeneralizedTable gt = new GeneralizedTable();
gt.mGenTable.mPt = node.mPh;
return gt;
}
广义表的表尾：广义表的表尾必定是一个广义表，但不管由什么子表组成，都是广义表的pT所指向的内容：求解广义表表尾的代码如下：
public GeneralizedTable getTear() {
if (isEmpty())
return null;
Node node = mGenTable.mPt;
GeneralizedTable gt = new GeneralizedTable();
gt.mGenTable.mPt = node.mPt;
return gt;
}
打印广义表的内容：这里打印广义表内容是指，打印所有原子项中的数据，一个深度优先打印的代码如下：
public void print() {
print(mGenTable);
}
private void print(Node node) {
if (node == null) {
return;
}
if (node.mTag == 0) {
System.out.print(node.mData.toString() + " \t");
}
print(node.mPh);
print(node.mPt);
}
下面是整个广义表操作的代码：
import java.util.Stack;
/**
* 广义表操作：
* 1、广义表的构造 ：
* 1.1 构造一个空的广义表
* 1.2 根据现有的广义表，构造一个新的广义表
* 1.3 根据广义表字符串构造一个广义表
* 2、广义表的深度
* 3、广义表的长度
* 4、按照深度优先顺序打印广义表
* 5、求广义表表头
* 6、求广义表表尾
*
*/
public class GeneralizedTable {
public static final int TAG_ITEM = 0; // 原子节点
public static final int TAG_TABLE = 1; // 表节点
/*
* 广义表支持的符号包括'(' , ')' , '{' , '}' , '[' , ']'
* 广义表表示符号,使用字符串构造广义表时第一个字符必须是'(', '{' , '[' 之一 并以')' , '}' , ']' 之一结束，
* 并且各符号相对应
*/
private char mStartSymb = '(';
private char mEndSymb = ')';
private Node mGenTable;
public GeneralizedTable() {
mGenTable = new Node(null, null, TAG_TABLE, null);
}
// 使用广义表 src 构造一个新的广义表
public GeneralizedTable(GeneralizedTable src) {
if (src != null) {
mGenTable = src.mGenTable;
}
}
/**
* @param genTable
*/
public GeneralizedTable(String genTabl