Expression evaluation

Expression evaluation is a common programming task, required in spreadsheets, programming language implementations or as a convenience feature of very various tools.

Run Review after Robert Breidecker * Alone

A software calculator that uses open sorce JEval library

Mathematical expressions, as written by human, are relatively challenging to evaluate:

• Not all operations can just be executed from left to right; the order of precedence must be respected. For instance, 2 + 3 * 2 must be evaluated into 8, not 12. Even more, the power operation must be executed from right to left ( 2^3^4 is intuitively understood as 2^(3^4) . Boolean operations also have order of precedence (not must be computed before and and and must be computed before or). Actually some very simple evaluators, as found in assembly language of first amateur computers (like Radio86RK) were not respecting this order, simply stating this fact in the documentation. Other languages like Lisp propose alternative notations that are easier for a machine to understand.
• The order of precedence can also be altered using parenthesis that indirectly introduce the concept of the stack. The current scope must be placed aside, an expression inside parentheses must be computed, and then it must be merged the previously saved expression.
• While most of the operations take two parameters, at least two common and frequent operations (negation (-) and logical not) take one.
• Expressions may also contain complex and matrix data types but usually only specialised tools support these. However complex values may appear and disappear somewhere in the middle of the computation when both all input and the computed result are real numbers (like in (sqrt(-1)^2 = -1 ). This sometimes makes analytically derived formula, while formally correct, useless on the platforms without at least any complex data type support.

Difficulties of straightforward implementation at one time marked expression evaluation as "elite" feature, something that not every programmer knows how to implement. However currently this is less an issue as many open source libraries appeared.

The tree

The human written expression is actually the tree, not a list. In this tree, the final constants or variables are leaves, and the operations are nodes. One of the ways to evaluate the expression is to build this tree data structure first, and then evaluate it using recursion. It is always trivial to evaluate the deepest level operations that only have leaves (constants and variables) as they parameters. After evaluation, the node of the operation can be replaced by the single leaf, the computed value. This makes higher level operations possible to compute, while at the end all tree transforms into a single leaf, the value of the expression. For instance, 2 * (2 + 3 * 2 + 2 * 5) is first transformed into 2 * (2 + 6 + 10), then into 2 * 18 and then into 36, the final result.

Operation stack and operand stack

The alternative approach (also used in the provided applet) is to replace the tree by operation stack and operand stack. Both stacks can be built by parsing the expression from left to right. The complete stacks represent the clear sequence of operations that is already easy to evaluate. Some hardware calculators in the past implemented human-operable stacks to facilitate the computation of complex expressions.

Optimizations

Industrial implementation may contain additional optimizations to avoid evaluating parts that have no impact on the result. For instance, in c and (a or b) neither a nor b has any impact on the result if c = false.