广义表操作 (ava实现)――广义表深度、广义表长度、打印广义表信息(二)
e) {
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"); } } 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); } 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; } 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 GeneralizedTable getHeader() { if (isEmpty()) return null; Node node = mGenTable.mPt; GeneralizedTable gt = new GeneralizedTable(); gt.mGenTable.mPt = node.mPh; return gt; } public GeneralizedTable getTear() { if (isEmpty()) return null; Node node = mGenTable.mPt; GeneralizedTable gt = new GeneralizedTable(); gt.mGenTable.mPt = node.mPt; return gt; } public boolean isEmpty() { if (mGenTable == null) { return true; } Node node = mGenTable.mPt; return node == null || node.mPh == null; } public class Node {// 广义表节点 Node mPh; // 广义表的表节点 Node mPt; // 广义表表尾节点 int mTag; // mTag == 0 , 院子节点 ; mTag == 1 , 表节点 。 Object mData; // 广义表的数据值 public Node(Node ph, Node pt, int tag, Object data) { mPh = ph; mPt = pt; mTag = tag; mData = data; } } /** * @param args */ public static void main(String[] args) { // String tStr = "((),(a,b,c),a,d,((d,g,(c))),(k,g),c)"; String p = "((),a,b,(a,b,c),(a,(a,b),c))"; String p2 = "((()),2)"; // String space = "()"; String big = "{{a,b},{{a,g},{h},{a,n,f,{a,b,c}}},c}"; String middle = "[[p],[[d,f,[g]]],[h],[2]]"; GeneralizedTable gTab = new GeneralizedTable(middle); // GeneralizedTable hea