NB! For some strange reason some sample code for this post was rejected by the server with “BLOCKED EXPRESSION” error. After several attempts to fix the problem, I converted code snippets to images. All three blog posts are combined now in an article that is published at CodeProject.
The first post about symbolic calcutaion in F# showed how to calculate derivatives, and the sequel demonstrated how the algebraic expressions can be simplified. Still, the most natural would be to write expressions in plain text, so the program could take an input like “sin(x ^ 2)” and generate an output “2 * x * cos(x ^ 2)”.
Let’s see how this can be approached with F#. We start with a formatter – formatting is usually easier than parsing. First we define a couple of helper functions to format operators and function names:
Then the rough implementation of the expression formatter does not take many lines of code:
There is only one problem with this code: it always surrounds algebraic operations with parenthesis, and this is only necessary in case the expression is contained in an outer expression. This is an example of redundant parenthesis:
It’s not complicated however to modify the original code, so it does not embrace top-level expressions with parenthesis:
Now we’re getting nice-looking output:
Satisfied with expression formatting, we can now proceed with expression parsing which appeared to be a more challenging tasks. First we need a tokenizer that would convert an input string into a list of tokens – atoms that will be building blocks of the resulting expression. Here is a simple tokenizer:
The tokenizer includes one rule that is specific for processing exponential functions (e ^ x). Unlike other functions (log, sin, cos), the exponent uses power operator notation, so adding proper support for it would devote large part of the post series just to this specific case. So I made a light constraint on use of exponent: its argument is always enclosed in parenthesis (so the input string should look like “e ^ (x)”, not “e ^ x”, and during the tokenization process the expression is converted into notation similar to other functions: e(x). So when proceeding with expression parsing, we won’t need to handle exponential functions in a special way.
Next step is to eleminate parenthesis and divide tokens into groups, each group representing a trivial expression construct. For example, an expression “(2 + x) * (5 – x) can be split into groups containing expressions “2 + x”, “5 – x” and the operator “*” binding them together. We achive this in a few steps: first by assigning each token a level (incremented with each opening parentheses and decremeneted with a closing parentheses), and then by putting contiguous tokens with the same level in a list. Here is the code that handles these operations and an example of its use:
We will also need some auxilliary functions: to test if a string represent an operator or a function, a couple of active pattern definitions to match numeric constants and variables, and methods to apply parsed operators or functions to expressions that they bind:
With supporting stuff in place, here’s the code that converts text input into expression trees:
Now it’s just to test how this all works:
So we’re done: we can now enter math expressions in plain text and obtain results of symbolic derivative calculation also in plain text. All in F#!