Problem with recursion


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 3 of 3

Thread: Problem with recursion

  1. #1
    Join Date
    Oct 2004
    Posts
    2

    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)

  2. #2
    Join Date
    Mar 2004
    Posts
    635
    link doesn't work.

  3. #3
    Join Date
    Oct 2004
    Posts
    2
    ***********************************************
    //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( );
    }

    }

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center