Evaluating infix expressions

I am planning to extend my tiny fractal renderer towards user-defined formulae for fractals, so I have to learn how to parse and evaluate infix math expressions. To practice and learn, I wrote sillyeval. The source code is here.

How it works

So I need to convert infix expressions to some form that can easily be evaluated from code. Browsing Wikipedia on the topic, I found the shunting-yard algorithm which converts infix notation to postfix, which seemed to be exactly what I need. The german Wikipedia page has pseudocode which one can work along, and this page was also very helpful when it came to dealing with unary operators.

Internally, sillyeval implements a tokenizer (in tokenize.c) which decomposes the input into numbers, brackets, operators and functions. These tokens will be fed into the shunting-yard parser shunting_yard.c which will order and push all the tokens onto a stack (stack.c) in postfix notation, which can then be evaluated (function eval(...) in stack.c). The eval function can be supplied with what I called a context (defined in context.c) i.e. a linked list of variable-value pairs. If the eval function encounters a variable in its input, it'll check if a variable with this name is defined in the context, and if so substitute it. Otherwise it'll abort.

At the time of writing this, sillyeval is essentially a calculator. There's no reason why you should use it - it was just a fun experiment for me.

Compiling

The code comes with a static makefile which contains exactly one rule:

all:
        gcc -o sillyeval sillyeval.c tokenize.c shunting_yard.c stack.c context.c -lm

So you can just make it if you have gcc, or edit the Makefile for your compiler if you don't.

Usage

You can use sillyeval in two modes. Without any arguments, its essentially a calculator. It'll expect an infix expression on stdin, parse it, if succesful evaluate it, and then quit. Here's an example:

$./sillyeval
3 * (2 + 5)
21.000000
$

An alternate mode of operation allows you to use sillyeval to evaluate formulae for multiple values of a parameter: given an arbitrary number of infix expressions as arguments to the executable, the program will wait for the parameters/variables being defined via input on stdin, and then evaluate each expression and print the result(s):

$./sillyeval "x" "sin(x)" "cos(x)"
x = 0;
0.000000 0.000000 1.000000
x = x + .1;
0.100000 0.099833 0.995004
x = x + .1;
0.200000 0.198669 0.980067
x = x + .1;
0.300000 0.295520 0.955336

As you can see, sillyeval will remember variables between evaulations. Variable definitions must end with a semicolon, otherwise they'll be ignored. Multiple variables can be defined, too. Examples of how this mode can be used in fun ways are given below.

Quirks

As it is right now, the syntax is mostly familiar but somewhat awkward in some respects. This especially applies to functions. The mathematical expression sin²(x) has to be written as (sin(x))^2 and not sin(x)^2. The latter rather evaluates to the expression sin(x²). This applies to all operators, not just the power operator. It is best to always encapsulate functions in braces to prevent unexpected strange behaviour. The following demonstrates this behaviour:

$./sillyeval "x" "sin(3 * x)" "sin(x) * 3" "3 * sin(x)" "(sin(x)) * 3"
x = 1.;
1.000000 0.141120 0.141120 2.524413 2.524413

As you can see for x = 1, sin(3 * x) and sin(x) * 3 both evaluate to sin(3x), while 3 * sin(x) and (sin(x)) * 3 both evaluate to 3sin(x).

Some fun with sillyeval

Let's see what we can do:

Solving a differential equation

Let's suppose we want to solve a differential equation of the form

A very simple drift-kick type integrator can be implemented in a few lines of bash, where we integrate the diff. eq. for three different initial amplitudes.

#!/bin/bash

steps=250

init="t=0.;x=1.;v=0.;dt=.1;"
echo -e "$init\n$(yes 't = t + dt; x = x + dt* v; v = v - (sin(x)) * dt;' | head -n $steps)" | ../sillyeval t x v > deq_low.txt

init="t=0.;x=2.;v=0.;dt=.1;"
echo -e "$init\n$(yes 't = t + dt; x = x + dt* v; v = v - (sin(x)) * dt;' | head -n $steps)" | ../sillyeval t x v > deq_med.txt

init="t=0.;x=2.99;v=0.;dt=.1;"
echo -e "$init\n$(yes 't = t + dt; x = x + dt* v; v = v - (sin(x)) * dt;' | head -n $steps)" | ../sillyeval t x v > deq_high.txt

init="t=0.;x=3.13;v=0.;dt=.1;"
echo -e "$init\n$(yes 't = t + dt; x = x + dt* v; v = v - (sin(x)) * dt;' | head -n $steps)" | ../sillyeval t x v > deq_very_high.txt

The result can be plotted with a few lines of gnuplot:

set terminal svg
set output "deq.svg"

set xlabel "time t [sec]"
set ylabel "position x [rad]"
set grid
plot "deq_low.txt" using 1:2 with lines title "low amplitude",\
    "deq_med.txt" using 1:2 with lines title "medium amplitude",\
    "deq_high.txt" using 1:2 with lines title "high amplitude", \
    "deq_very_high.txt" using 1:2 with lines title "very high amplitude"

In the output, which you can see below, the nonlinear and therefore anharmonic nature of a pendulum becomes clearly visible.

For a truly harmonic oscillator the frequency would be independent of the amplitude, and the waveform would be exactly (co)sinusoudal. This is no longer true for a pendulum due to the sin(x) nonlinearity in the force law.

Root finding

I wanted to put some root finding stuff down here but never really got down to it... well, I'm not sure if I ever will!