title: Polish/Prefix Notation logical expression to Expression Tree and back
body: <p>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 <a href="http://smtlib.cs.uiowa.edu/" rel="nofollow noreferrer">SMT-LIB standard</a> and <a href="http://cvc4.cs.nyu.edu/web/" rel="nofollow noreferrer">CVC4</a>  and I am trying to create some complex constraints. I don't want to evaluate the expression in any kind of way. For example</p>
  
  <pre><code>(and (&gt; Money 500) (= Name "Smith"))
  </code></pre>
  
  <p>should become</p>
  
  <pre><code>             and
          /          \
        &gt;             =
      /    \        /    \
    Money 500   Name   "Smith"
  </code></pre>
  
  <p>Additional features required or extendable to achieve:</p>
  
  <ol>
  <li>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.</li>
  <li>Traverse Tree object and change Node content</li>
  </ol>
  
  <p>I don't really know anything about grammars which makes it harder to understand some questions about the topic. </p>
  
  <p>Thanks for every thought and hint!</p>
  
  <p>Here is what I found until now.</p>
  
  <p><strong>Questions on how to write it yourself:</strong></p>
  
  <p>Wonderful Answer on how to achieve this kind of conversion in general:
  <a href="https://stackoverflow.com/a/7867104/5451007">https://stackoverflow.com/a/7867104/5451007</a></p>
  
  <p><a href="https://stackoverflow.com/questions/523957/about-trees-and-prefix-polish-notation">About Trees and Prefix (Polish) Notation?</a></p>
  
  <p><strong>Would be great to hear if some of this could help me:</strong></p>
  
  <p>Might be a similar problem but in c#: <a href="https://stackoverflow.com/questions/13282917/implementing-a-prefix-notation-expression-parser-using-irony">Implementing a prefix notation expression parser using Irony</a></p>
  
  <p>Maybe writing a parser and lexer using ANTRL or JavaCC is an option?
  <a href="https://stackoverflow.com/a/4590027/5451007">https://stackoverflow.com/a/4590027/5451007</a></p>
  
  <p>ANTLR:
  <a href="https://stackoverflow.com/questions/4589951/parsing-an-arithmetic-expression-and-building-a-tree-from-it-in-java">Parsing an arithmetic expression and building a tree from it in Java</a></p>
  
  <p><strong>Questions concerning problems while programming something equivalent:</strong>
  Prefix to expression tree <a href="https://stackoverflow.com/questions/20230687/build-binary-expression-tree-from-prefix-notation">Build binary expression tree from prefix notation?</a></p>
  
  <p>Postfix to expression tree <a href="https://stackoverflow.com/questions/27522131/converting-a-postfix-notation-to-an-expressiontree">Converting a Postfix Notation to an ExpressionTree</a></p>
  
  <p><a href="https://stackoverflow.com/questions/1974236/string-to-abstract-syntax-tree">string to abstract syntax tree</a></p>
  
  <p><strong>General algorithm ideas:</strong></p>
  
  <p>Postfix to tree: <a href="https://stackoverflow.com/questions/423898/postfix-notation-to-expression-tree">Postfix notation to expression tree</a></p>