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();
}
}
// 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;
}
}
Output of sample runs:
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 ) ) )#