#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    10
    Rep Power
    0

    Help me with expression tree


    hi everyone,
    i have done expression tree however i have problem which is if user input ((a-4)-(b-3))
    tostring method should print the expression like this
    (a-4)-(b-3)
    this is my code
    Code:
    public class ExpTree {
        private int kind;
        private Object value;
        private ExpTree lChild, rChild;
        public static final int numNode =0, idNode= 1, opNode=2, cNode=3, coNode=4,dNode=5;
        //add extra node kind for colon, comma, and definition node
         public ExpTree (int knd, Object val, ExpTree l, ExpTree r)
         {
             kind =knd;
             value =val;
             lChild= l;
             rChild = r;
    
         }
    
        public void preOreder()
        {
            if(value.equals(':')){
                System.out.println(value);
                if (lChild!= null)
                 lChild.preOreder();
           }
            else {
             System.out.println(value);
             if (lChild!= null)
                 lChild.preOreder();
            if(rChild != null)
                rChild.preOreder();
            }
    
        }
        public int evalEX()
        {
    
            int res = 0;
            if (kind == dNode)
                res = rChild.evalEX();
            if(kind==numNode)
                res=(Integer)value;
            else
            if(kind==idNode)
                res=(Character)value-'a';
           else
    
            {
            int l = lChild.evalEX();
            int r = rChild.evalEX();
                 switch ((Character)value)
                 {
                     case '+':
                         res= l + r;
                         break;
                     case '-':
                         res = l-r;
                         break;
                     case '*':
                         res = l * r;
                         break;
                     case '%':
                         res = l%r;
                         break;
                     case '^':
                         if( r < 0)
                         throw new ArithmeticException("can not apply to negative number");
                         else
                         res = l^r;
                         break;
                     case '/':
                         if( r == 0)
                             throw new ArithmeticException("can not divide by zero");
                         else
                         res = l/r;
                         break;
    
    }                }
        return res;
        }
        public String toString() {
            if (kind==idNode || kind == numNode)
    
                return value.toString();
            String s1 = lChild.toString();
            String s2 = rChild.toString();
    
             if(value.equals('-')){
               return "("+s1+")"+value+s2;
             }
           return s1+value+s2;
        }
    
    }
    the main file is
    Code:
    import java.util.HashMap;
    import java.util.Scanner;
    
    public class ***2 {
    
        public static void main(String args[])
        {
    
            char c ;
            do {
                Scanner s = new Scanner(System.in);
    
                  System.out.println("Please type an expression: " );
                    ExpTree myTree = new Parser().parseLine();
                  System.out.println("Pre-order:" );
                    myTree.preOreder();
                 System.out.println("In-order: " + myTree);
    
                 try
                 {
                     System.out.println("Evaluation the expression: " + myTree.evalEX());
    
                 } catch (Exception e)
                 {
                     System.out.println("Error"+e);
                 }
                System.out.println("Another expression (y/n)?");
                c = s.next().charAt(0);
            }while(c == 'y');
        }
    }
    anybody help me ???
    thanks in advance
  2. #2
  3. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,711
    Rep Power
    347
    tostring method should print the expression like this
    (a-4)-(b-3)
    Can you post what the program does print out?
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    10
    Rep Power
    0
    The program output is a-(3)-(b-(4)) is put braket for every right child
  6. #4
  7. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,711
    Rep Power
    347
    The posted code does not compile without errors: missing class definitions.
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    10
    Rep Power
    0
    Originally Posted by NormR
    The posted code does not compile without errors: missing class definitions.
    sorry I forget to put this file
    Code:
    
    import java.io.*;
    
    public class Parser
    { private Lexer lex;
    
      public Parser()
      { lex = new Lexer();
      }
    
      public ExpTree parseLine()
      { lex.getToken();
        ExpTree result = parseExp(true);
        if (lex.token==Lexer.colon)
        { lex.getToken();
          ExpTree defs = parseDefList();
          ExpTree res = result;
    	  result = makeColonTree(result, defs);
          if (result==null) result = res;
    	}
        if (lex.token!=Lexer.semico)
        { error("semicolon expected");
        }
        return result;
      }
    
      private ExpTree parseExp(boolean idsAllowed)
      { ExpTree result = parseTerm(idsAllowed);
        { while (lex.token==Lexer.plus || lex.token==Lexer.minus)
          { int op = lex.token;
            lex.getToken();
            if (op==Lexer.plus)
              result = makePlusTree(result, parseTerm(idsAllowed));
            else
              result = makeMinusTree(result, parseTerm(idsAllowed));
    	  }
        }
        return result;
      }
    
      private ExpTree parseTerm(boolean idsAllowed)
      { ExpTree result = parsePow(idsAllowed);
        { while (lex.token==Lexer.times || lex.token==Lexer.div || lex.token==Lexer.mod)
          { int op = lex.token;
            lex.getToken();
            if (op==Lexer.times)
              result = makeTimesTree(result, parseOpd(idsAllowed));
            else if (op==Lexer.div)
              result = makeDivideTree(result, parseOpd(idsAllowed));
            else
              result = makeModTree(result, parseOpd(idsAllowed));
    	  }
        }
        return result;
      }
    
      private ExpTree parsePow(boolean idsAllowed)
      { ExpTree result = parseOpd(idsAllowed);
        if (lex.token==Lexer.pow)
        { lex.getToken();
          result = makePowerTree(result, parsePow(idsAllowed));
        }
        return result;
      }
    
      private ExpTree parseOpd(boolean idsAllowed)
      { ExpTree result;
        switch(lex.token)
        { case Lexer.num:
            result = makeNumberLeaf(lex.numval);
            lex.getToken();
            return result;
          case Lexer.id:
            if (!idsAllowed)
              error("identifier not allowed in identifier defintion");
            result = makeIdLeaf(lex.idval);
            lex.getToken();
            return result;
          case Lexer.lp:
            lex.getToken();
            result = parseExp(idsAllowed);
            if (lex.token!=Lexer.rp)
              error("right parenthesis expected");
            lex.getToken();
            return result;
          default:
            error("invalid operand");
            return null;
        }
      }
    
      private ExpTree parseDefList()
      { ExpTree result = parseDef();
    	while (lex.token==Lexer.comma)
        { lex.getToken();
          result = makeCommaTree(result, parseDef());
        }
    	return result;
      }
    
      private ExpTree parseDef()
      { if (lex.token!=Lexer.id)
          error("definition must start with identifier");
        char id = lex.idval;
        lex.getToken();
        if (lex.token!=Lexer.eq)
          error("definition must start with identifier");
        lex.getToken();
        return makeDefTree(id, parseExp(false));
      }
    
      private static void error(String s)
      { System.out.println("Invalid expression: "+s);
        System.exit(1);
      }
    
      // the next eight methods need to be modified for part 3 of the assignment
    
      static ExpTree makeNumberLeaf(int n)
      {
          return new ExpTree (ExpTree.numNode, n, null, null);
      }
    
      static ExpTree makeIdLeaf(char c)
      {
          return new ExpTree(ExpTree.idNode, c,null,null);
      }
    
      static ExpTree makePlusTree(ExpTree l, ExpTree r)
      {
          return new ExpTree(ExpTree.opNode,'+',l , r);
    
      }
    
      static ExpTree makeMinusTree(ExpTree l, ExpTree r)
      {
          return new ExpTree(ExpTree.opNode,'-',l , r);
      }
    
      static ExpTree makeTimesTree(ExpTree l, ExpTree r)
      {
          return new ExpTree(ExpTree.opNode,'*',l , r);
      }
    
      static ExpTree makeDivideTree(ExpTree l, ExpTree r)
      {
          return new ExpTree(ExpTree.opNode,'/',l , r);
      }
    
      static ExpTree makeModTree(ExpTree l, ExpTree r)
      {
          return new ExpTree(ExpTree.opNode,'%',l , r);
      }
    
      static ExpTree makePowerTree(ExpTree l, ExpTree r)
      {
          return new ExpTree(ExpTree.opNode,'^',l , r);
      }
    
      // the next three methods need to be modified for part 6 of the assignment - do not modify them if you have not attempted part 6
    
      static ExpTree makeColonTree(ExpTree l, ExpTree r)
      { // remove the following line if you modify this method; leave it here if you do not attempt part 6
        //  System.out.println("Part 6 not attempted");
          return new ExpTree(ExpTree.cNode,':',l , r);
                // this method should return a new colon node with children l and r
      }
    
      static ExpTree makeCommaTree(ExpTree l, ExpTree r)
      {
          return new ExpTree(ExpTree.coNode,',',l , r);    // this method should return a new comma node with children l and r
      }
    
      static ExpTree makeDefTree(char c, ExpTree t)
      {
          return new ExpTree(ExpTree.dNode,c,makeIdLeaf(c), t);
        // this method should return a new definition node with identifier c and child t
        // if your definition nodes have 2 children you should put a new id leaf in the left child and use t as the right child
        }
    }
    
    class Lexer
    { static final int err = 0, num = 1, id = 2, plus = 3, minus = 4, times = 5, div = 6, mod = 7,
                       lp = 8, rp = 9, semico = 10, colon = 11, comma = 12, eq = 13, pow = 14;
      int token;
      char idval;
      int numval;
      private String line = "";
    
      Lexer()
      { BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        do
          try
          { line = buf.readLine().trim();
          }
          catch(Exception e)
          { System.out.println("Error in input");
            System.exit(1);
    	  }
        while (line.length()==0);
      }
    
      void getToken()
      { if (line.length()==0)
          token = err;
        else switch (line.charAt(0))
        { case '+':
            token = plus;
            line = line.substring(1).trim();
            break;
          case '-':
            token = minus;
            line = line.substring(1).trim();
            break;
          case '*':
            token = times;
            line = line.substring(1).trim();
            break;
          case '/':
            token = div;
            line = line.substring(1).trim();
            break;
          case '^':
            token = pow;
            line = line.substring(1).trim();
            break;
          case '%':
            token = mod;
            line = line.substring(1).trim();
            break;
          case '(':
            token = lp;
            line = line.substring(1).trim();
            break;
          case ')':
            token = rp;
            line = line.substring(1).trim();
            break;
          case ';':
            token = semico;
            line = line.substring(1).trim();
            break;
          case ':':
            token = colon;
            line = line.substring(1).trim();
            break;
          case ',':
            token = comma;
            line = line.substring(1).trim();
            break;
          case '=':
            token = eq;
            line = line.substring(1).trim();
            break;
          default:
            if (Character.isDigit(line.charAt(0)))
            { token = num;
              numval = line.charAt(0) - '0';
              int i = 1;
              while (i<line.length()&&Character.isDigit(line.charAt(i)))
              { numval = numval*10+line.charAt(i)-'0';
                i++;
    		  }
              line = line.substring(i).trim();
    		}
    		else if (Character.isLowerCase(line.charAt(0)))
    		{ token = id;
    		  idval = line.charAt(0);
              line = line.substring(1).trim();
    		}
    		else
    		  token = err;
    	}
      }
    }
    with this file it complie with out any error
    so can u solve my problem ??????
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    10
    Rep Power
    0
    Originally Posted by memo0o0
    sorry I forget to put this file
    Code:
    
    import java.io.*;
    
    public class Parser
    { private Lexer lex;
    
      public Parser()
      { lex = new Lexer();
      }
    
      public ExpTree parseLine()
      { lex.getToken();
        ExpTree result = parseExp(true);
        if (lex.token==Lexer.colon)
        { lex.getToken();
          ExpTree defs = parseDefList();
          ExpTree res = result;
    	  result = makeColonTree(result, defs);
          if (result==null) result = res;
    	}
        if (lex.token!=Lexer.semico)
        { error("semicolon expected");
        }
        return result;
      }
    
      private ExpTree parseExp(boolean idsAllowed)
      { ExpTree result = parseTerm(idsAllowed);
        { while (lex.token==Lexer.plus || lex.token==Lexer.minus)
          { int op = lex.token;
            lex.getToken();
            if (op==Lexer.plus)
              result = makePlusTree(result, parseTerm(idsAllowed));
            else
              result = makeMinusTree(result, parseTerm(idsAllowed));
    	  }
        }
        return result;
      }
    
      private ExpTree parseTerm(boolean idsAllowed)
      { ExpTree result = parsePow(idsAllowed);
        { while (lex.token==Lexer.times || lex.token==Lexer.div || lex.token==Lexer.mod)
          { int op = lex.token;
            lex.getToken();
            if (op==Lexer.times)
              result = makeTimesTree(result, parseOpd(idsAllowed));
            else if (op==Lexer.div)
              result = makeDivideTree(result, parseOpd(idsAllowed));
            else
              result = makeModTree(result, parseOpd(idsAllowed));
    	  }
        }
        return result;
      }
    
      private ExpTree parsePow(boolean idsAllowed)
      { ExpTree result = parseOpd(idsAllowed);
        if (lex.token==Lexer.pow)
        { lex.getToken();
          result = makePowerTree(result, parsePow(idsAllowed));
        }
        return result;
      }
    
      private ExpTree parseOpd(boolean idsAllowed)
      { ExpTree result;
        switch(lex.token)
        { case Lexer.num:
            result = makeNumberLeaf(lex.numval);
            lex.getToken();
            return result;
          case Lexer.id:
            if (!idsAllowed)
              error("identifier not allowed in identifier defintion");
            result = makeIdLeaf(lex.idval);
            lex.getToken();
            return result;
          case Lexer.lp:
            lex.getToken();
            result = parseExp(idsAllowed);
            if (lex.token!=Lexer.rp)
              error("right parenthesis expected");
            lex.getToken();
            return result;
          default:
            error("invalid operand");
            return null;
        }
      }
    
      private ExpTree parseDefList()
      { ExpTree result = parseDef();
    	while (lex.token==Lexer.comma)
        { lex.getToken();
          result = makeCommaTree(result, parseDef());
        }
    	return result;
      }
    
      private ExpTree parseDef()
      { if (lex.token!=Lexer.id)
          error("definition must start with identifier");
        char id = lex.idval;
        lex.getToken();
        if (lex.token!=Lexer.eq)
          error("definition must start with identifier");
        lex.getToken();
        return makeDefTree(id, parseExp(false));
      }
    
      private static void error(String s)
      { System.out.println("Invalid expression: "+s);
        System.exit(1);
      }
    
      // the next eight methods need to be modified for part 3 of the assignment
    
      static ExpTree makeNumberLeaf(int n)
      {
          return new ExpTree (ExpTree.numNode, n, null, null);
      }
    
      static ExpTree makeIdLeaf(char c)
      {
          return new ExpTree(ExpTree.idNode, c,null,null);
      }
    
      static ExpTree makePlusTree(ExpTree l, ExpTree r)
      {
          return new ExpTree(ExpTree.opNode,'+',l , r);
    
      }
    
      static ExpTree makeMinusTree(ExpTree l, ExpTree r)
      {
          return new ExpTree(ExpTree.opNode,'-',l , r);
      }
    
      static ExpTree makeTimesTree(ExpTree l, ExpTree r)
      {
          return new ExpTree(ExpTree.opNode,'*',l , r);
      }
    
      static ExpTree makeDivideTree(ExpTree l, ExpTree r)
      {
          return new ExpTree(ExpTree.opNode,'/',l , r);
      }
    
      static ExpTree makeModTree(ExpTree l, ExpTree r)
      {
          return new ExpTree(ExpTree.opNode,'%',l , r);
      }
    
      static ExpTree makePowerTree(ExpTree l, ExpTree r)
      {
          return new ExpTree(ExpTree.opNode,'^',l , r);
      }
    
      // the next three methods need to be modified for part 6 of the assignment - do not modify them if you have not attempted part 6
    
      static ExpTree makeColonTree(ExpTree l, ExpTree r)
      { // remove the following line if you modify this method; leave it here if you do not attempt part 6
        //  System.out.println("Part 6 not attempted");
          return new ExpTree(ExpTree.cNode,':',l , r);
                // this method should return a new colon node with children l and r
      }
    
      static ExpTree makeCommaTree(ExpTree l, ExpTree r)
      {
          return new ExpTree(ExpTree.coNode,',',l , r);    // this method should return a new comma node with children l and r
      }
    
      static ExpTree makeDefTree(char c, ExpTree t)
      {
          return new ExpTree(ExpTree.dNode,c,makeIdLeaf(c), t);
        // this method should return a new definition node with identifier c and child t
        // if your definition nodes have 2 children you should put a new id leaf in the left child and use t as the right child
        }
    }
    
    class Lexer
    { static final int err = 0, num = 1, id = 2, plus = 3, minus = 4, times = 5, div = 6, mod = 7,
                       lp = 8, rp = 9, semico = 10, colon = 11, comma = 12, eq = 13, pow = 14;
      int token;
      char idval;
      int numval;
      private String line = "";
    
      Lexer()
      { BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        do
          try
          { line = buf.readLine().trim();
          }
          catch(Exception e)
          { System.out.println("Error in input");
            System.exit(1);
    	  }
        while (line.length()==0);
      }
    
      void getToken()
      { if (line.length()==0)
          token = err;
        else switch (line.charAt(0))
        { case '+':
            token = plus;
            line = line.substring(1).trim();
            break;
          case '-':
            token = minus;
            line = line.substring(1).trim();
            break;
          case '*':
            token = times;
            line = line.substring(1).trim();
            break;
          case '/':
            token = div;
            line = line.substring(1).trim();
            break;
          case '^':
            token = pow;
            line = line.substring(1).trim();
            break;
          case '%':
            token = mod;
            line = line.substring(1).trim();
            break;
          case '(':
            token = lp;
            line = line.substring(1).trim();
            break;
          case ')':
            token = rp;
            line = line.substring(1).trim();
            break;
          case ';':
            token = semico;
            line = line.substring(1).trim();
            break;
          case ':':
            token = colon;
            line = line.substring(1).trim();
            break;
          case ',':
            token = comma;
            line = line.substring(1).trim();
            break;
          case '=':
            token = eq;
            line = line.substring(1).trim();
            break;
          default:
            if (Character.isDigit(line.charAt(0)))
            { token = num;
              numval = line.charAt(0) - '0';
              int i = 1;
              while (i<line.length()&&Character.isDigit(line.charAt(i)))
              { numval = numval*10+line.charAt(i)-'0';
                i++;
    		  }
              line = line.substring(i).trim();
    		}
    		else if (Character.isLowerCase(line.charAt(0)))
    		{ token = id;
    		  idval = line.charAt(0);
              line = line.substring(1).trim();
    		}
    		else
    		  token = err;
    	}
      }
    }
    with this file it complie with out any error
    so can u solve my problem ??????
    this file have method definition for -/+/*/^/ / /%
  12. #7
  13. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,711
    Rep Power
    347
    How can I put this String into the program as input to the program?
    ((a-4)-(b-3))

    I don't want to have to type it in every time the program is executed for testing.
    Is there a way to pass it to the Parser class from the main() method used for testing?
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    10
    Rep Power
    0
    Originally Posted by NormR
    How can I put this String into the program as input to the program?
    ((a-4)-(b-3))

    I don't want to have to type it in every time the program is executed for testing.
    Is there a way to pass it to the Parser class from the main() method used for testing?

    this program ask user to type expression
    so when he type this expression tostring method (in-oreder)in ExperTree class will output with nessery parenthese....
  16. #9
  17. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,711
    Rep Power
    347
    program ask user to type expression
    How do I put the String into the program and remove having to type anything every time the code is executed? There should be a way to pass a String to the Parser class.

IMN logo majestic logo threadwatch logo seochat tools logo