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:
- 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.
- 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
