mikhail42/parsington

Simple yet fancy infix-to-postfix parser for mathematical expressions. :bowtie:

Parsington

Parsington is an infix-to-postfix (or infix-to-syntax-tree) expression parser for mathematical expressions written in Java. It is simple yet fancy, handling (customizable) operators, functions, variables and constants in a similar way to what the Java language itself supports.

Parsington is part of the SciJava project for scientific computing in Java.

Rationale

Expression parsers are as old as the hills; what makes this one different?

• No dependencies.
• Available on Maven Central.
• Permissive BSD-2 license. See LICENSE.txt.
• Separation of concerns. Parsington is a parser, not an evaluator. Once you have the postfix queue and/or syntax tree, what you do with it is your business (though there is a small evaluation API in the eval subpackage if that appeals to you). In general, there is no assumption that your variables will consist of any particular data type, numerical or otherwise.
• Clean, well-commented codebase with unit tests. 'Nuff said!

History

The ImageJ Ops project needed an expression parser so that it could be more awesome. But not one limited to primitive doubles, or one that conflated parsing with evaluation, or one licensed in a restrictive way. Just a simple infix parser: a nice shunting yard implementation, or maybe some lovely recursive descent. Something on GitHub, with no dependencies, available on Maven Central. But surprisingly, there was only tumbleweed. So Parsington was born, and all our problems are now over!

Usage

In your POM <dependencies>:

<dependency>
  <groupId>org.scijava</groupId>
  <artifactId>parsington</artifactId>
  <version>1.0.0</version>
</dependency>

Postfix queues

To parse an infix expression to a postfix queue:

LinkedList<Object> queue = new ExpressionParser().parsePostfix("a+b*c^f(1,2)'");
// queue = [a, b, c, f, 1, 2, (2), <Fn>, ^, ', *, +]

Syntax trees

To parse an infix expression to a syntax tree:

SyntaxTree tree = new ExpressionParser().parseTree("a+b*c^f(1,2)'");

       +-------+
       |   +   |
       +---+---+
           |
    +------+------+
    |             |
+---+---+     +---+---+
|   a   |     |   *   |
+-------+     +---+---+
                  |
           +------+------+
           |             |
       +---+---+     +---+---+
       |   b   |     |   '   |
       +-------+     +---+---+
                         |
                         |
                     +---+---+
                     |   ^   |
                     +---+---+
                         |
                  +------+------+
                  |             |
              +---+---+     +---+---+
              |   c   |     | <Fn>  |
              +-------+     +---+---+
                                |
                         +------+------+
                         |             |
                     +---+---+     +---+---+
                     |   f   |     |  (2)  |
                     +-------+     +---+---+
                                       |
                                +------+------+
                                |             |
                            +---+---+     +---+---+
                            |   1   |     |   2   |
                            +-------+     +-------+

Evaluation

To evaluate an expression involving basic types:

Object result = new DefaultEvaluator().evaluate("6.5*7.8^2.3");

Interactive console

There is also an interactive console shell you can play with.

Run it easily using jrun:

jrun org.scijava:parsington

Or run from source, after cloning this repository:

mvn
java -jar target/parsington-*-SNAPSHOT.jar

> 6.5*7.8^2.3
732.3706691398969
> postfix('6.5*7.8^2.3')
6.5
7.8
2.3
^
*
> tree('6.5*7.8^2.3')
 '*'
 - '6.5'
 - '^'
  -- '7.8'
  -- '2.3'

> 2*3,4
      ^
Misplaced separator or mismatched groups at index 4