Formula parser using recursive descent method

Good day, dear Habrovchane!

I want to share with you the implementation of the algorithm "Method of recursive descent" on the example of writing a parser of formulas with support for variables and functions in the Java language
')
This article in (most likely, in any case, I hope :)) will be interesting for beginners, or to apply to someone as a foundation for solving this problem.
Who cares - I ask under the cat

TK

Develop a formula parser that:

• keeps the correct queue of operations
• supports functions
• supports variables

Introduction

The essence of this method is that it is divided into its subtasks. In turn, the subtask should work only with what it can work with, if the conditions are not met to transfer control further. If the conditions are satisfied, we do the calculations and pass the rest of the raw text. Execution occurs as long as the text is still there or if no subtask can handle the current state.

Subtask priority is also important. Changing the priority of the subtask will change the behavior of the parser.
Since we will implement the parser of mathematical formulas, to prioritize, we will be guided by the priorities of mathematical operations:

1. function and variable
2. parentheses
3. multiplication and division
4. addition and subtraction

Flew

Well, now for the cause.
As I have already mentioned above, we will manipulate the remainder of the line, that is, each task bites off what it does in the teeth and passes on what it cannot swallow.
Total we need the following structure:
string variable to hold the rest of the string
and the so-called accumulator, to store the current state of the calculation process
Need to? Let's do it!

class Result { public double acc; public String rest; public Result(double v, String r) { this.acc = v; this.rest = r; } } 

Now let's start the parser itself:
first we will call the subtask with the lowest priority.
Subtasks, in turn, transfer control to subtasks with a higher priority, and after each of their actions that have affected the text, we also transfer control to subtasks with a high priority.
And as mentioned above, program execution will continue until there is something to parse, or we stumble upon an unknown structure or sequence of data.

From the method that performs addition / subtraction, we will cause multiplication / division, and so on.

For a common understanding, let's slightly simplify the task, let's make a parser that only performs addition and subtraction operations:

 public class MatchParserPlusMinus { public MatchParserPlusMinus(){} public double Parse(String s) throws Exception { Result result = PlusMinus(s); if (!result.rest.isEmpty()) { System.err.println("Error: can't full parse"); System.err.println("rest: " + result.rest); } return result.acc; } private Result PlusMinus(String s) throws Exception { Result current = Num(s); double acc = current.acc; while (current.rest.length() > 0) { if (!(current.rest.charAt(0) == '+' || current.rest.charAt(0) == '-')) break; char sign = current.rest.charAt(0); String next = current.rest.substring(1); acc = current.acc; current = Num(next); if (sign == '+') { acc += current.acc; } else { acc -= current.acc; } current.acc = acc; } return new Result(current.acc, current.rest); } private Result Num(String s) throws Exception { int i = 0; int dot_cnt = 0; boolean negative = false; //       if( s.charAt(0) == '-' ){ negative = true; s = s.substring( 1 ); } //      while (i < s.length() && (Character.isDigit(s.charAt(i)) || s.charAt(i) == '.')) { //   ,        ! if (s.charAt(i) == '.' && ++dot_cnt > 1) { throw new Exception("not valid number '" + s.substring(0, i + 1) + "'"); } i++; } if( i == 0 ){ // -       throw new Exception( "can't get valid number in '" + s + "'" ); } double dPart = Double.parseDouble(s.substring(0, i)); if( negative ) dPart = -dPart; String restPart = s.substring(i); return new Result(dPart, restPart); } } 

and when calling:

  MatchParserPlusMinus pm = new MatchParserPlusMinus(); String f = "10-8+2+6"; try{ System.out.println( "PlusMinus: " + pm.Parse(f) ); }catch(Exception e){ System.err.println( "Error while parsing '"+f+"' with message: " + e.getMessage() ); } 

Will bring us:
PlusMinus: 10.0


In this parser, I implemented the following functions (you can expand this list with your functions by adding the corresponding condition in the processFunction ):

• sin
• cos
• tan

I didn’t particularly bother with error handling (so as not to clutter up the “useful” code), otherwise the error handling code may be more than the code for the parser itself :)

Here is the full listing of the class without simplification:

 public class MatchParser { private HashMap<String, Double> variables; public MatchParser() { variables = new HashMap<String, Double>(); } public void setVariable(String variableName, Double variableValue) { variables.put(variableName, variableValue); } public Double getVariable(String variableName) { if (!variables.containsKey(variableName)) { System.err.println( "Error: Try get unexists variable '"+variableName+"'" ); return 0.0; } return variables.get(variableName); } public double Parse(String s) throws Exception { Result result = PlusMinus(s); if (!result.rest.isEmpty()) { System.err.println("Error: can't full parse"); System.err.println("rest: " + result.rest); } return result.acc; } private Result PlusMinus(String s) throws Exception { Result current = MulDiv(s); double acc = current.acc; while (current.rest.length() > 0) { if (!(current.rest.charAt(0) == '+' || current.rest.charAt(0) == '-')) break; char sign = current.rest.charAt(0); String next = current.rest.substring(1); current = MulDiv(next); if (sign == '+') { acc += current.acc; } else { acc -= current.acc; } } return new Result(acc, current.rest); } private Result Bracket(String s) throws Exception { char zeroChar = s.charAt(0); if (zeroChar == '(') { Result r = PlusMinus(s.substring(1)); if (!r.rest.isEmpty() && r.rest.charAt(0) == ')') { r.rest = r.rest.substring(1); } else { System.err.println("Error: not close bracket"); } return r; } return FunctionVariable(s); } private Result FunctionVariable(String s) throws Exception { String f = ""; int i = 0; //      //       while (i < s.length() && (Character.isLetter(s.charAt(i)) || ( Character.isDigit(s.charAt(i)) && i > 0 ) )) { f += s.charAt(i); i++; } if (!f.isEmpty()) { //  -  if ( s.length() > i && s.charAt( i ) == '(') { //      -   Result r = Bracket(s.substring(f.length())); return processFunction(f, r); } else { //  -   return new Result(getVariable(f), s.substring(f.length())); } } return Num(s); } private Result MulDiv(String s) throws Exception { Result current = Bracket(s); double acc = current.acc; while (true) { if (current.rest.length() == 0) { return current; } char sign = current.rest.charAt(0); if ((sign != '*' && sign != '/')) return current; String next = current.rest.substring(1); Result right = Bracket(next); if (sign == '*') { acc *= right.acc; } else { acc /= right.acc; } current = new Result(acc, right.rest); } } private Result Num(String s) throws Exception { int i = 0; int dot_cnt = 0; boolean negative = false; //       if( s.charAt(0) == '-' ){ negative = true; s = s.substring( 1 ); } //      while (i < s.length() && (Character.isDigit(s.charAt(i)) || s.charAt(i) == '.')) { //   ,        ! if (s.charAt(i) == '.' && ++dot_cnt > 1) { throw new Exception("not valid number '" + s.substring(0, i + 1) + "'"); } i++; } if( i == 0 ){ // -       throw new Exception( "can't get valid number in '" + s + "'" ); } double dPart = Double.parseDouble(s.substring(0, i)); if( negative ) dPart = -dPart; String restPart = s.substring(i); return new Result(dPart, restPart); } //     ,       private Result processFunction(String func, Result r) { if (func.equals("sin")) { return new Result(Math.sin(Math.toRadians(r.acc)), r.rest); } else if (func.equals("cos")) { return new Result(Math.cos(Math.toRadians(r.acc)), r.rest); } else if (func.equals("tan")) { return new Result(Math.tan(Math.toRadians(r.acc)), r.rest); } else { System.err.println("function '" + func + "' is not defined"); } return r; } } 

And when calling:

  String[] formulas = new String[] { "2+2*2", "2+X*2", "sin(90)+4-cos(0)", "2--4", "2**3*5-----7", "3.5.6-2" }; MatchParser p = new MatchParser(); p.setVariable("X", 2.0 ); for( int i = 0; i < formulas.length; i++){ try{ System.out.println( formulas[i] + "=" + p.Parse( formulas[i] ) ); }catch(Exception e){ System.err.println( "Error while parsing '"+formulas[i]+"' with message: " + e.getMessage() ); } } 

Displays:
2+2*2=6.0
2+X*2=6.0
sin(90)+4-cos(0)=4.0
2--4=6.0
Error while parsing '2**3*5-----7' with message: can't get valid number in '*3*5-----7'
Error while parsing '3.5.6-2' with message: not valid number '3.5.'


You can download the whole project here (thanks to flexoid for the hint where you can save the archive)
Thanks for attention!