2

I am looking for a java library that could convert a logical expression wirtten in polish/prefix notation into an abstract syntax tree object and back. This is the syntax used by the SMT-LIB standard and CVC4 and I am trying to create some complex constraints. I don't want to evaluate the expression in any kind of way. For example

(and (> Money 500) (= Name "Smith"))

should become

             and
        /          \
      >             =
    /    \        /    \
  Money 500   Name   "Smith"

Additional features required or extendable to achieve:

  1. Reading a prefix notation, it must be possible to react on the operator type i.e. some operators are chainable (+ a b c) represents a+b+c. This can easily be handled by using (+ (+ a b) c) . But another operator is (distinct a b c) which means a,b,c pairwise distinct. This would however require a non-binary tree I suppose.
  2. Traverse Tree object and change Node content

I don't really know anything about grammars which makes it harder to understand some questions about the topic.

Thanks for every thought and hint!

Here is what I found until now.

Questions on how to write it yourself:

Wonderful Answer on how to achieve this kind of conversion in general: https://stackoverflow.com/a/7867104/5451007

About Trees and Prefix (Polish) Notation?

Would be great to hear if some of this could help me:

Might be a similar problem but in c#: Implementing a prefix notation expression parser using Irony

Maybe writing a parser and lexer using ANTRL or JavaCC is an option? https://stackoverflow.com/a/4590027/5451007

ANTLR: Parsing an arithmetic expression and building a tree from it in Java

Questions concerning problems while programming something equivalent: Prefix to expression tree Build binary expression tree from prefix notation?

Postfix to expression tree Converting a Postfix Notation to an ExpressionTree

string to abstract syntax tree

General algorithm ideas:

Postfix to tree: Postfix notation to expression tree

Community
  • 1
  • 1
Koronis
  • 49
  • 5
  • 1
    Well done on your research but unfortunately "I am looking for a java library" makes your question [off-topic for Stack Overflow](http://stackoverflow.com/help/on-topic). – Jongware Oct 23 '15 at 08:23
  • That explains why I could not find anything on the matter here. Sorry. I will try to focus on the additional feature 1) and ask another question hoping for it to be on topic. Will this question get closed automatically? – Koronis Oct 23 '15 at 09:23
  • @Koronis You might consider [Software Recommendatations SE](http://softwarerecs.stackexchange.com/) (though I don't know if you'll get an answer there either). – svick Oct 29 '15 at 16:19

0 Answers0