/Expression-Parser

very simple math expression parser in less than 200 lines of Java code

Primary LanguageJava

Expression Parser

This Java class parses simple math expressions, like 2.5+2*(3-7). Expressions may contain brackets ( ), operands *,-,/,+ and numbers with optional decimal point.

Methods

The following methods are provided to parse and evaluate math expressions:

parseExpression(String expr): parses the given expression and returns a binary tree representing the parse expression;

evaluate(Node p): evaluates the binary tree containing an expression;

visit(Node p): visits the binary tree containing an expression;

Syntax Rules

The parser use the following rules to parse math expressions:

<expression> ::= <term> { ("+"|"-") <term> }*
<term> ::= <factor> { ("*"|"/") <factor> }*
<factor> ::= "(" <expression> ")" | "-" <factor> | <number>
<number> ::= { <digit> }+ [ "." { <digit> }* ]
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Example

Parsing the expression 2+3*(4+5) you obtain the following binary tree:

  +
 / \
2   *
   / \
  3   +
     / \
    4   5

The evaluation of this binary tree returns the value 29, as expected.