Custom operators

MPOperator

Any operator is to be derived from the abstract class MPOperator. The derived class should override the following methods:

/// <summary>
/// Returns -1 if the operator doesn't match. Else it returns the length of the matched string.
/// </summary>
/// <param name="expression">The expression</param>
/// <param name="previousToken">The previous expression</param>
/// <returns></returns>
public abstract int Match(string expression, object previousToken);

/// <summary>
/// Returns an object while altering the stack
/// </summary>
/// <param name="output"></param>
/// <returns></returns>
public abstract void Execute(Stack<object> output);

The method Match() will return -1 if the start of expression is not recognized.
The object previoustoken can be used to determine if a unary operator can be expected in the same way as for data types.

The method Execute() will do whatever it is supposed to do using the output stack. This stack contains the operands for the operator, and the result should be pushed back on the stack.

An example implementation can be found here for the unary operator +:

using System;
using System.Text.RegularExpressions;
using System.Collections.Generic;

namespace MultiParse.Default
{
    public class MPPositive : MPOperator
    {
        /// <summary>
        /// Constructor
        /// </summary>
        public MPPositive()
            : base("+", PrecedenceUnary, false)
        {
        }

        /// <summary>
        /// Find unary positive
        /// </summary>
        /// <param name="expression"></param>
        /// <param name="previousToken"></param>
        /// <returns></returns>
        public override int Match(string expression, object previousToken)
        {
            if (!IsUnary(previousToken))
                return -1;
            if (Regex.IsMatch(expression, @"^\+(?![\+\=])"))
                return 1;
            return -1;
        }

        /// <summary>
        /// Execute unary positive
        /// </summary>
        /// <param name="output"></param>
        public override void Execute(Stack<object> output)
        {
            // Pop object from the stack
            object top = PopOrGet(output);
            Positive(output, top);
        }

        /// <summary>
        /// Positive
        /// </summary>
        /// <param name="output"></param>
        /// <param name="operand"></param>
        public void Positive(Stack<object> output, object operand)
        {
            TypeCode tc = Type.GetTypeCode(operand.GetType());
            switch (tc)
            {
                case TypeCode.Byte: output.Push(+(Byte)operand); return;
                case TypeCode.Char: output.Push(+(Char)operand); return;
                case TypeCode.Decimal: output.Push(+(Decimal)operand); return;
                case TypeCode.Double: output.Push(+(Double)operand); return;
                case TypeCode.Int16: output.Push(+(Int16)operand); return;
                case TypeCode.Int32: output.Push(+(Int32)operand); return;
                case TypeCode.Int64: output.Push(+(Int64)operand); return;
                case TypeCode.SByte: output.Push(+(SByte)operand); return;
                case TypeCode.Single: output.Push(+(Single)operand); return;
                case TypeCode.UInt16: output.Push(+(UInt16)operand); return;
                case TypeCode.UInt32: output.Push(+(UInt32)operand); return;
                case TypeCode.UInt64: output.Push(+(UInt64)operand); return;
            }

            // Invalid operation
            throw new InvalidOperatorTypesException("+", operand);
        }
    }
}

The constructor assigns the right precedence and associativity to the operator via the base constructor. The static variable PrecedenceUnary contains the standard precedence level for unary operations. It is specified to be right-associative, meaning that ++8 = +(+8), as ((+)+)8 would not make sense. Note that C# also recognizes ++ as an operator, so for C# this expression is invalid.

To match the expression, the operator first determines whether or not the operator is unary. If it isn't, then it is probably the addition operator, which is binary.

Executing the operator is done by first popping the operands off the stack. Because the evaluation is stack based, they need to be popped in reverse order for binary operators (i.e. first the right operator, then the left operator). But because this operator is unary, it doesn't matter. Popping the operand from the stack is done by the method PopOrGet(). This method also checks whether or not the object implements the IMPGettable interface. If it does, then it calls the method Get() and returns that object instead.

The method Positive() will first convert the object to its respective type, based on its type code. This introduces a small decrease in performance, because an object is constantly casted to its actual type. But in return, we get a very powerful and versatile expression parser!

Example - Complex number

There are in total 7 operators that will be defined for being able to work with complex numbers. These are:
  • Binary +: addition
  • Binary -: subtraction
  • Binary *: multiplication
  • Binary /: division
  • Unary +: positive of a number
  • Unary -: negative of a number
  • Binary ^: power of numbers

In this case, the unary + will not have any effect on the answers (+var = var). The sole purpose of this operator is to be able to parse it. If this operator is not added, then it is impossible to parse expressions like 1+(+3)*+i. It would not recognize +3 and +i. The unary operators will not be discussed in this tutorial, and are left to the reader.

To save ourselves from a lot of work, we can implement each of these operators simply by deriving their respective default operators MPAddition(), MPSubtraction(), MPMultiplication(), MPDivision(), MPPositive() and MPNegative(). That way we don't have to implement the string matching algorithms, and we only need to override the Execute() method.

Complex addition

The complex addition is implemented as follows:

/// <summary>
/// The complex addition is an extension on the standard addition
/// </summary>
public class ComplexAddition : MultiParse.Default.MPAddition
{
    /// <summary>
    /// Complex addition
    /// </summary>
    /// <param name="output"></param>
    public override void Execute(Stack<object> output)
    {
        // Pop the operands off the stack
        object right = PopOrGet(output);
        object left = PopOrGet(output);
        double d;

        if (left is Complex && right is Complex)
            Add(output, (Complex)left, (Complex)right);
        else if (left is Complex && CastImplicit(right, out d))
            Add(output, (Complex)left, d);
        else if (right is Complex && CastImplicit(left, out d))
            Add(output, d, (Complex)right);
        else

            // Attempt a standard addition
            base.Add(output, left, right);
    }

    // Addition
    public void Add(Stack<object> output, Complex left, Complex right)
    {
        output.Push(new Complex(left.Real + right.Real, left.Imag + right.Imag));
    }
    public void Add(Stack<object> output, double left, Complex right)
    {
        output.Push(new Complex(left + right.Real, right.Imag));
    }
    public void Add(Stack<object> output, Complex left, double right)
    {
        output.Push(new Complex(left.Real + right, left.Imag));
    }
}

The operands are popped in reverse order, first right then left. If both objects are Complex objects, then we invoke the method for two complex objects.
Another possibility is to have the complex number being added to a double. If we were to use the line

else if (left is Complex && right is Double)

then the addition would only work for the combination of Complex+double. It would be nice to also allow for implicit conversions. E.g. an integer can be implicitly converted to a double. So by means of implicit conversion, the addition will also work for Complex+double, Complex+int, Complex+uint, Complex+long, Complex+ulong, Complex+byte, Complex+sbyte, etc.

To accommodate for this, helper methods are provided that can implicitly cast an object to a native type. If the implicit cast is successful, then CastImplicit() returns True. The second parameter will then contain the implicitly converted variable, in our example the double d.
Finally, the combination of double+Complex is implemented as well. If any of these fail (they are not a combination Complex and a type that can be cast to a double), then the base method is called. This method will perform the addition for any of the native types, and throw an error if the addition still fails.

This operator is finally added to the MultiParse expression object.

Expression e = new Expression(MPDefault.DataTypes.Double);
e.DataTypes.Add(new ComplexDataType());
e.Operators.Add(new ComplexAddition());

The operators -, * and / are completely analogous.

Complex subtraction

public override void Execute(Stack<object> output)
{
    object right = output.Pop();
    object left = output.Pop();
    double d;
    if (left is Complex && right is Complex)
        Subtract(output, (Complex)left, (Complex)right);
    else if (left is Complex && CastImplicit(right, out d))
        Subtract(output, (Complex)left, d);
    else if (CastImplicit(left, out d) && right is Complex)
        Subtract(output, d, (Complex)right);
    else
        base.Execute(output);
}

// Complex subtraction
public void Subtract(Stack<object> output, Complex left, Complex right)
{
    output.Push(new Complex(left.Real - right.Real, left.Imag - right.Imag));
}
public void Subtract(Stack<object> output, Complex left, double right)
{
    output.Push(new Complex(left.Real - right, left.Imag));
}
public void Subtract(Stack<object> output, double left, Complex right)
{
    output.Push(new Complex(left - right.Real, -right.Imag));
}

Complex multiplication

/// <summary>
/// Complex multiplication
/// </summary>
/// <param name="output"></param>
public override void Execute(Stack<object> output)
{
    // Find the operands
    object right = output.Pop();
    object left = output.Pop();
    double d;

    if (left is Complex && right is Complex)
        Multiply(output, (Complex)left, (Complex)right);
    else if (left is Complex && CastImplicit(right, out d))
        Multiply(output, (Complex)left, d);
    else if (right is Complex && CastImplicit(left, out d))
        Multiply(output, d, (Complex)right);
    else

        // Attempt a standard addition
        base.Multiply(output, left, right);
}

// Complex multiplication
public void Multiply(Stack<object> output, Complex left, Complex right)
{
    output.Push(new Complex(left.Real * right.Real - left.Imag * right.Imag, left.Real * right.Imag + left.Imag * right.Real));
}
public void Multiply(Stack<object> output, Complex left, double right)
{
    output.Push(new Complex(left.Real * right, left.Imag * right));
}
public void Multiply(Stack<object> output, double left, Complex right)
{
    output.Push(new Complex(left * right.Real, left * right.Imag));
}

Complex division

public override void Execute(Stack<object> output)
{
    object right = output.Pop();
    object left = output.Pop();
    double d;
    if (left is Complex && right is Complex)
        Divide(output, (Complex)left, (Complex)right);
    else if (left is Complex && CastImplicit(right, out d))
        Divide(output, (Complex)left, d);
    else if (CastImplicit(left, out d) && right is Complex)
        Divide(output, d, (Complex)right);
    else
        base.Execute(output);
}

// Complex / Complex division
public void Divide(Stack<object> output, Complex left, Complex right)
{
    double abssq = right.Real * right.Real + right.Imag * right.Imag;
    output.Push(new Complex((left.Real * right.Real + left.Imag * right.Imag) / abssq, (right.Real * left.Imag - right.Imag * left.Real) / abssq));
}
public void Divide(Stack<object> output, Complex left, double right)
{
    output.Push(new Complex(left.Real / right, left.Imag / right));
}
public void Divide(Stack<object> output, double left, Complex right)
{
    double abssq = right.Real * right.Real + right.Imag * right.Imag;
    output.Push(new Complex(left * right.Real / abssq, -left * right.Imag / abssq));
}

Complex exponentiation

The complex exponentiation will need a little bit different of an approach for the following reasons
  • The operator ^ is by default the XOr operator, not the exponent operator
  • The default XOr operator is left-associative a^b^c = (a^b)^c and not right-associative like exponentiation a^b^c = a^(b^c)
  • The default XOr operator has a low precedence, whereas exponentiation has a higher precedence than multiplication

These three reasons make this situation a little bit different. We will still derive the operator from the default binary ^ operator, because it still allows us to use the default expression matching algorithm. But we will need to change the precedence and associativity of the operator.

The complete code is given:

public class ComplexPower : MultiParse.Default.MPLogicalXOr
{
    /// <summary>
    /// Constructor
    /// </summary>
    public ComplexPower()
        : base()
    {
        // Promote this operator to a higher precedence (execute before multiplication)
        this.precedence = PrecedenceMultiplicative + 1;
        this.leftAssociative = false;
    }

    /// <summary>
    /// Execute power
    /// </summary>
    /// <param name="output"></param>
    public override void Execute(Stack<object> output)
    {
        // Get operands
        object right = output.Pop();
        object left = output.Pop();

        double ld, rd;
        if (CastImplicit(left, out ld) && CastImplicit(right, out rd))
            Power(output, ld, rd);
        else if (left is Complex && CastImplicit(right, out rd))
            Power(output, (Complex)left, rd);
        else
            throw new MultiParse.InvalidArgumentTypeException("^", left, right);
    }

    /// <summary>
    /// double ^ double power
    /// </summary>
    /// <param name="output"></param>
    /// <param name="left"></param>
    /// <param name="right"></param>
    public void Power(Stack<object> output, double left, double right)
    {
        output.Push(Math.Pow(left, right));
    }

    /// <summary>
    /// Complex ^ double exponentiation
    /// </summary>
    /// <param name="output"></param>
    /// <param name="left"></param>
    /// <param name="right"></param>
    public void Power(Stack<object> output, Complex left, double right)
    {
        // Convert to polar form
        double abssq = left.Real * left.Real + left.Imag * left.Imag;
        double argument = Math.Atan2(left.Imag, left.Real);

        // Calculate the polar form of the exponentiated complex number
        double powAbs = Math.Pow(abssq, right * 0.5);
        double powArg = argument * right;

        // Convert back to conventional complex number
        output.Push(new Complex(powAbs * Math.Cos(powArg), powAbs * Math.Sin(powArg)));
    }
}

The constructor is now specified in order to assign the correct precedence and associativity.
Adding all these functions finally look like this:

using System;
using MultiParse;
using MultiParse.Default;
using Tutorials.Complex;

namespace Tutorials
{
    class Program
    {
        static void Main(string[] args)
        {
            // Create a MultiParse Expression object
            Expression e = new Expression(MPDefault.DataTypes.Double | MPDefault.DataTypes.Int);
            e.DataTypes.Add(new ComplexDataType());
            e.Operators.Add(new ComplexAddition());
            e.Operators.Add(new ComplexSubtraction());
            e.Operators.Add(new ComplexMultiplication());
            e.Operators.Add(new ComplexDivision());
            e.Operators.Add(new ComplexPower());

            // Evaluate the expression
            object result = e.Evaluate("(1+3*i)^2/(1-i)");
            Console.WriteLine(result + " " + result.GetType().ToString()); // returns -7+i*-1 Tutorials.Complex.Complex
            Console.ReadKey();
        }
    }
}

That is all for operators! On to Custom functions!

Last edited Jan 5, 2014 at 2:15 PM by SBoulang, version 4