java - Looking for advice on project. Parsing logical expression -

i'm looking advice on school project. supposed create program takes logical expression , outputs truth table it. creating of truth table me not difficult @ , i've wrote methods in java it. know if there classes in java use parse expression me , put stack. if not i'm looking on parsing expression. it's parentheses me whenever try , think through. if easier in other language open doing in that. perl next best language.

some examples (p && q) -> r

(p || q || r) && ((p -> r) -> q)

if you're allowed use parser generator tool antlr, here's how started. grammar simple logic-language this:

grammar logic;  parse   :  expression eof   ;  expression   :  implication   ;  implication   :  or ('->' or)*   ;  or   :  , ('||' and)*   ;  ,   :  not ('&&' not)*   ;  not   :  '~' atom   |  atom   ;  atom   :  id   |  '(' expression ')'   ;  id    : ('a'..'z' | 'a'..'z')+; space : (' ' | '\t' | '\r' | '\n')+ {$channel=hidden;}; 

however, if you'd parse input (p || q || r) && ((p -> r) -> q) parser generated grammar above, parse tree contain parenthesis (something you're not interested in after parsing expression) , operators not root of each sub-trees, doesn't make life easier if you're interested in evaluating expression.

you'll need tell antlr omit tokens ast (this can done placing ! after token/rule) , make tokens/rules root of (sub) tree (this can done placing ^ after it). finally, need indicate in options section of grammar want proper ast created instead of simple parse tree.

so, grammar above this:

// save in file called logic.g grammar logic;  options {   output=ast; }  // parser/production rules start lower case letter parse   :  expression eof!    // omit eof token   ;  expression   :  implication   ;  implication   :  or ('->'^ or)*    // make `->` root   ;  or   :  , ('||'^ and)*    // make `||` root   ;  ,   :  not ('&&'^ not)*      // make `&&` root   ;  not   :  '~'^ atom    // make `~` root   |  atom   ;  atom   :  id   |  '('! expression ')'!    // omit both `(` , `)`   ;  // lexer/terminal rules start upper case letter id    : ('a'..'z' | 'a'..'z')+; space : (' ' | '\t' | '\r' | '\n')+ {$channel=hidden;}; 

you can test parser following class:

import org.antlr.runtime.*; import org.antlr.runtime.tree.*; import org.antlr.stringtemplate.*;  public class main {   public static void main(string[] args) throws exception {      // expression     string src = "(p || q || r) && ((p -> r) -> q)";      // create lexer & parser     logiclexer lexer = new logiclexer(new antlrstringstream(src));     logicparser parser = new logicparser(new commontokenstream(lexer));      // invoke entry point of parser (the parse() method) , ast     commontree tree = (commontree)parser.parse().gettree();      // print dot representation of ast      dottreegenerator gen = new dottreegenerator();     stringtemplate st = gen.todot(tree);     system.out.println(st);   } } 

now run main class, do:

*nix/macos

java -cp antlr-3.3.jar org.antlr.tool logic.g  javac -cp antlr-3.3.jar *.java java -cp .:antlr-3.3.jar main

windows

java -cp antlr-3.3.jar org.antlr.tool logic.g  javac -cp antlr-3.3.jar *.java java -cp .;antlr-3.3.jar main

which print dot source of following ast:

(image produced graphviz-dev.appspot.com)

now all need evaluate ast! :)