Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
March 17th, 2013, 10:10 PM
 memo0o0
Registered User

Join Date: Feb 2013
Posts: 10
Time spent in forums: 52 m 13 sec
Reputation 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 ???

#2
March 18th, 2013, 07:14 AM
 NormR
Contributing User

Join Date: Aug 2010
Location: SW Missouri
Posts: 3,593
Time spent in forums: 2 Weeks 3 Days 3 h 35 m 23 sec
Reputation Power: 347
Quote:
 tostring method should print the expression like this (a-4)-(b-3)

Can you post what the program does print out?

#3
March 18th, 2013, 10:01 AM
 memo0o0
Registered User

Join Date: Feb 2013
Posts: 10
Time spent in forums: 52 m 13 sec
Reputation Power: 0
The program output is a-(3)-(b-(4)) is put braket for every right child

#4
March 18th, 2013, 10:23 AM
 NormR
Contributing User

Join Date: Aug 2010
Location: SW Missouri
Posts: 3,593
Time spent in forums: 2 Weeks 3 Days 3 h 35 m 23 sec
Reputation Power: 347
The posted code does not compile without errors: missing class definitions.

#5
March 18th, 2013, 12:18 PM
 memo0o0
Registered User

Join Date: Feb 2013
Posts: 10
Time spent in forums: 52 m 13 sec
Reputation Power: 0
Quote:
 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)
char id = lex.idval;
lex.getToken();
if (lex.token!=Lexer.eq)
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()
do
try
}
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 ??????

#6
March 18th, 2013, 12:19 PM
 memo0o0
Registered User

Join Date: Feb 2013
Posts: 10
Time spent in forums: 52 m 13 sec
Reputation Power: 0
Quote:
 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

this file have method definition for -/+/*/^/ / /%

#7
March 18th, 2013, 12:34 PM
 NormR
Contributing User

Join Date: Aug 2010
Location: SW Missouri
Posts: 3,593
Time spent in forums: 2 Weeks 3 Days 3 h 35 m 23 sec
Reputation 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?

#8
March 18th, 2013, 04:59 PM
 memo0o0
Registered User

Join Date: Feb 2013
Posts: 10
Time spent in forums: 52 m 13 sec
Reputation Power: 0
Quote:
 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....

#9
March 18th, 2013, 05:19 PM
 NormR
Contributing User

Join Date: Aug 2010
Location: SW Missouri
Posts: 3,593
Time spent in forums: 2 Weeks 3 Days 3 h 35 m 23 sec
Reputation Power: 347
Quote:
 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.

 Viewing: Dev Shed Forums > Programming Languages > Java Help > Help me with expression tree