Problem with recursion
hi. I am writing some code to build an expression tree.
Unfortunately it's not working. I have spent days testing and it's just not working and to make things worse, it only appears to be a simple error.
Anyone who wants to have a quick look is welcome to:
http://www.pastebin.com/106673
Thanking you in advance.
btw.
It reads expressions from a arbituary named file of the form (3+6)*5-(2*15)
***********************************************
//Main Driver
import java.util.*;
import java.io.*;
public class Calculator {
public static void main (String [] args) throws IOException {
BufferedReader reader;
String curLine = null;
StringTokenizer st;
ExpBT ebt;
if (args.length > 0) {
reader = new BufferedReader(new FileReader(args[0]));
}
else {
throw new IOException("No input Detected!");
}
//Everything done inside this look
while((curLine = reader.readLine()) != null) {
st = new StringTokenizer(curLine);
String theExp = "";
while(st.hasMoreElements())
theExp = theExp + st.nextToken();
theExp = theExp + "$";
System.out.println(theExp);
try {
TestExpBuildTree bt = new TestExpBuildTree(theExp);
ebt = bt.getTree();
ebt.printInOrder();
}
catch (ParseError e) {
System.out.println("Parse Error: " + e.getMessage());
}
}
}
}
***********************************************
The build the tree
import java.util.*;
import java.io.*;
public class TestExpBuildTree {
protected String data;
protected int posn;
protected int peek;
protected char cur;
protected ExpBT tree;
public TestExpBuildTree (String line) throws ParseError {
data = line;
posn = 0;
peek = 1;
tree = expTree();
if (cur != '$')
throw new ParseError("end expected not expected");
}
private void getNext() throws ParseError {
if (posn < data.length() - 1){
cur = data.charAt(posn);
posn++;
peek++;
}
else
throw new ParseError("EOL detected prematurely");
}
private char peek() {
return data.charAt(peek);
}
public ExpBT getTree() {
return tree;
}
public ExpBT expTree() throws ParseError {
ExpBT exp;
exp = termTree();
while(peek() == '+' | peek() == '-') {
char op = cur;
ExpBT nextTerm = termTree();
exp = new ExpBT(op, exp, nextTerm);
}
return exp;
}
public ExpBT termTree() throws ParseError {
ExpBT term;
term = factorTree();
while(peek() == '*' | peek() == '/') {
char op = cur;
ExpBT nextFactor;
nextFactor = factorTree();
term = new ExpBT(op, term, nextFactor);
}
return term;
}
public ExpBT factorTree() throws ParseError {
char tmp;
tmp = peek();
if (Character.isDigit(tmp)) {
char constant = cur;
return new ExpBT(constant);
}
else if (tmp == '('){
// Skip the (
char ignore;
ignore = cur;
ExpBT exp = expTree();
if (peek() != ')') {
throw new ParseError("Missing right ')'");
}
ignore = cur;
return exp;
}
else
throw new ParseError("ParseError");
}
}
***********************************************
ExpBT (Binary Tree) and ExpBT Nodes
public class ExpBT {
protected ExpBTNode root;
/*************************************************************************
* Constructors *
*************************************************************************/
public ExpBT() {
root = null;
}
public ExpBT(char val) {
root = new ExpBTNode(val);
}
public ExpBT(char val, ExpBT l, ExpBT r) {
root = new ExpBTNode(val, l.root, r.root);
}
// End Constructors
public boolean hasLeft(ExpBTNode n) {
return (n.getLftChild() != null);
}
public boolean hasRight(ExpBTNode n) {
return (n.getRtChild() != null);
}
// Do we have a non-leaf node
public boolean nonLeaf(ExpBTNode n) {
return (hasLeft(n) || hasRight(n));
}
// Do we have a leaf node
public boolean isLeaf(ExpBTNode n) {
return !(nonLeaf(n));
}
// InOrder traversal of the tree
public void printInOrder() {
if (root != null) {
root.printInOrder();
}
}
public ExpBTNode getRoot() {
return root;
}
}
//The Nodes
public class ExpBTNode {
/**********************************************************************
* Define the nodes
* *******************************************************************/
private char val;
private ExpBTNode lftChild;
private ExpBTNode rtChild;
private ExpBTNode parent;
public ExpBTNode(char val, ExpBTNode lftChild, ExpBTNode rtChild){
this.val = val;
this.lftChild = lftChild;
this.rtChild = rtChild;
this.parent = null;
}
public ExpBTNode(char val) {
this.val = val;
this.lftChild = null;
this.rtChild = null;
this.parent = null;
}
// The Additional (Possibly useful) methods
public ExpBTNode getParent() {
return parent;
}
public void setParent(ExpBTNode newParent) {
parent = newParent;
}
public ExpBTNode getLftChild() {
return lftChild;
}
public void setLftChild(ExpBTNode lc) {
lftChild = lc;
}
public boolean hasLftChild(ExpBTNode n) {
return n.getLftChild() != null;
}
public ExpBTNode getRtChild() {
return rtChild;
}
public void setRtChild(ExpBTNode rc) {
lftChild = rc;
}
public boolean hasRtChild(ExpBTNode n) {
return n.getRtChild() != null;
}
public char getVal() {
return val;
}
public void printInOrder( ) {
if( lftChild != null )
lftChild.printInOrder( );
System.out.print(val);
if( rtChild != null )
rtChild.printInOrder( );
}
}