1

I'm going to write a program that calculate the zeros of a given function. I decided to write a parser to parse that function (I have never written one before). It's a real-valued function of a real variable like "sin(1/x)+exp(x)". I want to use root finding methods like Bisection and Newton. Since these methods are iterative I want to avoid evaluating the function each time in a loop for each point x. So before I make an effort to write my own parser I want to know that is it possible to parse just once and evaluate the function f at points x0, x2, ..., xn without re-parsing f for each x?

Dante
  • 611
  • 1
  • 7
  • 21

3 Answers3

2

There are two standard approaches to this problem:

  1. Parse the formula into what is called an "abstract syntax tree" (AST). This is a compiler data structure that represents the structure of the formula, and it can be inspected quickly by code. It is also possible to evaluate the AST as a formula relatively quickly. See my SO answer on building recursive descent parsers that support the above tasks: Is there an alternative for flex/bison that is usable on 8-bit embedded systems?

  2. Somehow compile the formula into your programming language. This often involves first building the AST, and then translating the AST into your programming lanuage terms, running your compiler on that result, and then loading the compiled result. This may be awkward with a compiled language such as C because the absence of dynamic linking; it is easier with languages such as Java or C# because they sort of encourage dynamic loading. As you can guess, this approach is more effort, but the payoff is that the formula can now be evaluated as quickly as your programming language can do it. You can do this by ad hoc (e.g., recursive descent) parsing and translation, or you do tackle this in a more regular manner using a tool that "rewrites" one syntax into another: https://softwarerecs.stackexchange.com/a/31379/101

Community
  • 1
  • 1
Ira Baxter
  • 93,541
  • 22
  • 172
  • 341
  • I cannot get the second part, you mean parse the function into Java code, put it into a class, save it as `.java` file, compile it and then load it? – Dante Apr 22 '16 at 18:44
  • 1
    Yep.. to be picky, you don't "parse the function into Java code". You parse the formula to build data structures (ASTs) representing what it says. Then you build a mini-translator that walks those data structures and emit Java code equivalents. (or C, or whatever your programming language is). – Ira Baxter Apr 22 '16 at 18:59
1

As Ira has already pointed out, you parse your expression to an abstract syntax tree. An abstract syntax tree fitting your would look similar to this:

interface AstNode {
  double eval(double x);
}

class ConstantNode implements AstNode {
  double value;

  double eval(double x) {
    return value;
  }
}

class VariableNode implements AstNode {
  double eval(double x) {
    return x;
  }
}

class OperatorNode implements AstNode {
  char op;
  AstNode left;
  AstNode right;

  double eval(double x) {
    switch (op) {
      case '+': return left.eval(x) + right.eval(x);
      case '-': return left.eval(x) - right.eval(x);
      case '/': return left.eval(x) / right.eval(x);
      case '*': return left.eval(x) * right.eval(x);
      case '^': return Math.pow(left.eval(x), right.eval(x));
      default:
        throw new RuntimeException("Invalid op " + op);
    }
  }
}

class Function implements AstNode {
  ...

After you have parsed your expression to the tree, you can just call eval() with the values you are interested in.

Stefan Haustein
  • 18,427
  • 3
  • 36
  • 51
0

Maybe you can do that with Java Scripting Support. For example, it should be possible to evaluate the function in Javascript (Nashorn).

Pro: you don't need to parse the function yourself. Just serve the scripting API.

Ingo
  • 36,037
  • 5
  • 53
  • 100