Boldface = additions to the bare parser.
/* TreeReadWrite.java: read and write binary trees * grammar for binary tree representation: * bintree ---> tree '#' * tree ---> '0' | '(' letter tree tree ')' * letter ---> 'a' | 'b' | 'c' | ... */ public class TreeReadWrite { private char next; // holds next input char private class tnode { // typical binary tree node char ch; tnode left; tnode right; }; private GetNext getNext = new GetNext(); private void bintree() { // binary tree, ends with # scan(); tnode root = tree(); if (next != '#') error(1); treePrint(root); System.out.println("#"); } private tnode tree() { tnode p; if (next == '0') { scan(); p = null; } else { p = new tnode(); if (next == '(') scan(); else error(2); if (Character.isLetter(next)) { p.ch = next; scan(); } else error(3); p.left = tree(); p.right = tree(); if (next == ')') scan(); else error(4); } return p; } private void scan() { // next char, ignore whitespace while (Character.isWhitespace(next = getNext.getNextChar())) ; } private void error(int n) { System.out.println("\n*** ERROR: " + n); System.exit(1); } // treePrint: recursive inorder print of tree p private void treePrint(tnode p) { if (p == null) System.out.print("0"); else { // turn lowercase into uppercase System.out.print("( " + Character.toUpperCase(p.ch) + " "); treePrint(p.left); System.out.print(" "); treePrint(p.right); System.out.print(" )"); } } public static void main(String[] args) { TreeReadWrite tree = new TreeReadWrite(); tree.bintree(); } }Output of sample runs:
// GetNext.java: fetch the next char or int from standard input import java.io.*; public class GetNext { // in: reader for reading input data private static Reader in = new InputStreamReader(System.in); // ch: holds the next character read private static char ch; public static char getNextChar() { try { ch = (char)in.read(); } catch (Exception exception) { System.out.println("Error reading character"); ch = ' '; } return ch; } }
ten60% javac -deprecation TreeReadWrite.java ten60% java TreeReadWrite (a 0 0) # ( A 0 0 )# ten60% java TreeReadWrite (a (b 0 0) (c 0 0) ) # ( A ( B 0 0 ) ( C 0 0 ) )# ten60% java TreeReadWrite (a (b (d 0 0) 0) (c (e 0 0) (f 0 0))) # ( A ( B ( D 0 0 ) 0 ) ( C ( E 0 0 ) ( F 0 0 ) ) )# ten60% java TreeReadWrite (m (f (a 0 (d 0 0)) (j 0 0)) (t (s (o (n 0 0) 0) 0) (w 0 0)))# ( M ( F ( A 0 ( D 0 0 ) ) ( J 0 0 ) ) ( T ( S ( O ( N 0 0 ) 0 ) 0 ) ( W 0 0 ) ) )#