SimplyExpress first release code

Example code:



/*
<Copyright Header>
Copyright (c) 2012 Jordan "Earlz/hckr83" Earls  <http://lastyearswishes.com>
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:

1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.
3. The name of the author may not be used to endorse or promote products
   derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

</Copyright Header>
*/
using System;
using System.Collections.Generic;

namespace SimplyExpress
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            List<ExpressionToken> tokens=new List<ExpressionToken>();
            ExpressionToken t=new ExpressionToken();

            t.IsOperation=true;
            t.Op=new IncrementOperation();
            tokens.Add(t);
            t=new ExpressionToken();
            t.IsOperation=false;
            t.Value=new MyValue(){Value=5};
            tokens.Add(t);
            t=new ExpressionToken();
            t.IsOperation=true;
            t.Op=new AddOperation();
            tokens.Add(t);
            t=new ExpressionToken();
            t.IsOperation=false;
            t.Value=new MyValue(){Value=10};
            tokens.Add(t);
            t=new ExpressionToken();
            t.IsOperation=true;
            t.Op=new MultiplyOperation();
            tokens.Add(t);
            t=new ExpressionToken();
            t.IsOperation=false;
            t.Value=new MyValue(){Value=2};
            tokens.Add(t);
            t=new ExpressionToken();

            List<Associativity> map=new List<Associativity>();
            map.Add(Associativity.LeftToRight); //not used
            map.Add(Associativity.LeftToRight); //not used
            map.Add(Associativity.RightToLeft);
            map.Add(Associativity.LeftToRight);
            map.Add(Associativity.LeftToRight);
            var express=new SimplyExpress(map);

            MyValue tmp=(MyValue)express.Evaluate(tokens);
            System.Console.WriteLine("tmp is "+tmp.Value.ToString());
        }


    }
    class MyValue : ExpressionValue
    {
        public int Value;
    }
    class AddOperation : Operation{
        public AddOperation(){
            Name="Binary Addition";
            OpType=OperationType.LeftRightOp;
            Precedence=4;
        }
        public override ExpressionValue Execute (ExpressionValue left, ExpressionValue right)
        {
            var l=(MyValue)left;
            var r=(MyValue)right;
            var res=new MyValue();
            res.Value=l.Value+r.Value;
            return res;
        }
    }
    class SubtractOperation : Operation{
        public SubtractOperation(){
            Name="Binary Subtraction";
            OpType=OperationType.LeftRightOp;
            Precedence=4;
        }
        public override ExpressionValue Execute (ExpressionValue left, ExpressionValue right)
        {
            var l=(MyValue)left;
            var r=(MyValue)right;
            var res=new MyValue();
            res.Value=l.Value-r.Value;
            return res;
        }
    }
    class MultiplyOperation : Operation{
        public MultiplyOperation(){
            Name="Binary Multiplication";
            OpType=OperationType.LeftRightOp;
            Precedence=3;
        }
        public override ExpressionValue Execute (ExpressionValue left, ExpressionValue right)
        {
            var l=(MyValue)left;
            var r=(MyValue)right;
            var res=new MyValue();
            res.Value=l.Value*r.Value;
            return res;
        }
    }
    class IncrementOperation : Operation{
        public IncrementOperation(){
            Name="Prefix Increment";
            OpType=OperationType.RightOp;
            Precedence=2;
        }
        public override ExpressionValue Execute (ExpressionValue left, ExpressionValue right)
        {
            var r=(MyValue)right;
            var res=new MyValue();
            res.Value=++r.Value;
            return res;
        }
    }
    class MinusOperation : Operation{
        public MinusOperation(){
            Name="Unary Minus";
            OpType=OperationType.RightOp;
            Precedence=2;
        }
        public override ExpressionValue Execute (ExpressionValue left, ExpressionValue right)
        {
            var r=(MyValue)right;
            var res=new MyValue();
            res.Value=-r.Value;
            return res;
        }
    }



}


SimplyExpress class code:


/*
<Copyright Header>
Copyright (c) 2012 Jordan "Earlz/hckr83" Earls  <http://lastyearswishes.com>
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:

1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.
3. The name of the author may not be used to endorse or promote products
   derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

</Copyright Header>
*/
using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace SimplyExpress
{
    public class SimplyExpress
    {
        List<Associativity> PrecedenceMap;
        public SimplyExpress (List<Associativity> map)
        {
            PrecedenceMap=map;
        }
        protected List<Node> ParseToTree(List<ExpressionToken> tokens){
            List<Node> tree=new List<Node>();
            for(int i=0;i<tokens.Count;i++){
                var token=tokens[i];
                if(token.IsOperation){
                    var op =new OperationNode();
                    op.Op=token.Op;
                    tree.Add(op);
                }else{
                    var val=new ValueNode();
                    val.Value=token.Value;
                    tree.Add(val);
                }
            }
            //now hook up left and right
            Node last=null;
            for(int i=0;i<tree.Count;i++){
                var node=tree[i];

                if(node is OperationNode){
                    var op=node as OperationNode;
                    if(last==null){
                        if(op.Op.OpType==OperationType.LeftOp || op.Op.OpType==OperationType.LeftRightOp){
                            throw new ApplicationException("parse error");
                        }
                    }
                    if(op.Op.OpType==OperationType.LeftRightOp && last is OperationNode){
                        //is this ok?
                        //throw new ApplicationException("parse exception");
                    }
                    op.Left=last;
                    if(last!=null){
                        last.Right=op;
                    }
                }else if(node is ValueNode){
                    if(last!=null && last is ValueNode){
                        throw new ApplicationException("parse error");
                    }
                    if(last !=null){
                        var oplast=last as OperationNode;
                        oplast.Right=node;
                        node.Left=oplast;
                    }

                }else{
                    throw new NotSupportedException();
                }
                last=node;
            }

            return tree;
        }
        public ExpressionValue Evaluate(List<ExpressionToken> tokens){
            List<Node> tree=ParseToTree(tokens);
            for(int i=0;i<PrecedenceMap.Count;i++){
                ReduceTree(i,ref tree);
            }
            if(tree.Count>1){
                throw new ApplicationException("Tree not completely reduced! more than 1 node");
            }
            Debug.Assert(tree.Count!=0);
            return ((ValueNode)tree[0]).Value;
        }
        void ReduceTree(int precedence, ref List<Node> tree){
            bool end=false;
            int i;
            if(PrecedenceMap[precedence]==Associativity.LeftToRight){
                i=0;
            }else{
                i=tree.Count-1;
            }
            while(!end){
                Node n=tree[i];
                if(n is OperationNode && ((OperationNode)n).Op.Precedence==precedence){
                    OperationNode op=n as OperationNode;
                    if(op.Op.OpType==OperationType.LeftOp){
                        var temp=new ValueNode();
                        if(op.Left==null || !(op.Left is ValueNode)){
                            throw new ApplicationException("Parse error. No left value");
                        }
                        temp.Value=op.Op.Execute(((ValueNode)op.Left).Value, null);
                        op.Right.Left=temp; //set to new result
                        tree[i]=temp;
                        if(i==0){
                            throw new ApplicationException("syntax/parse error. no left value(internal)");
                        }
                        if(tree[i-1].Left!=null){
                            tree[i-1].Left.Right=temp;
                        }
                        tree.RemoveAt(i-1);
                    }else if(op.Op.OpType == OperationType.RightOp){
                        var temp=new ValueNode();
                        if(op.Right==null || !(op.Right is ValueNode)){
                            throw new ApplicationException("Parse error. No right value");
                        }
                        temp.Value=op.Op.Execute(null,((ValueNode)op.Right).Value);
                        if(op.Left!=null){
                            op.Left.Right=temp;
                        }
                        tree[i]=temp;
                        if(i==tree.Count){
                            throw new ApplicationException("syntax/parse error. no right value(internal)");
                        }
                        if(tree[i+1].Right!=null){
                            tree[i+1].Right.Left=temp;
                        }
                        tree.RemoveAt(i+1);
                    }else if(op.Op.OpType == OperationType.LeftRightOp){
                        var temp=new ValueNode();
                        if(op.Right==null || !(op.Right is ValueNode)){
                            throw new ApplicationException("Parse error. No right value");
                        }
                        if(op.Left==null || !(op.Left is ValueNode)){
                            throw new ApplicationException("Parse error. No left value");
                        }
                        temp.Value=op.Op.Execute(((ValueNode)op.Left).Value,((ValueNode)op.Right).Value);
                        if(op.Left.Left!=null){
                            op.Left.Left.Right=temp;
                        }
                        if(op.Right.Right!=null){
                            op.Right.Right.Left=temp;
                        }
                        if(i==0){
                            throw new ApplicationException("syntax/parse error. no left value(internal)");
                        }
                        if(i==tree.Count){
                            throw new ApplicationException("syntax/parse error. no right value(internal)");
                        }
                        tree[i]=temp;
                        tree.RemoveAt(i+1);
                        tree.RemoveAt(i-1);
                    }else{
                        throw new ApplicationException();
                    }


                }
                if(PrecedenceMap[precedence]==Associativity.LeftToRight){
                    i=i+1;
                    if(i>=tree.Count){
                        end=true;
                    }

                }else{
                    if(i<=0){
                        end=true;
                    }
                    i=i-1;
                }
            }

        }
        protected class OperationNode : Node
        {
            public Operation Op;

        }
        protected class Node{
            public Node Left;
            public Node Right;
        }
        protected class ValueNode : Node
        {
            public ExpressionValue Value;
        }
    }
    public class ExpressionToken{
        public bool IsOperation;
        public ExpressionValue Value;
        public Operation Op;
    }
    public enum OperationType{
        Value,
        LeftOp,
        RightOp,
        LeftRightOp
    };
    public enum Associativity{
        RightToLeft,
        LeftToRight
    };
    public abstract class Operation
    {
        public OperationType OpType;
        public string Name;
        public int Precedence; //lower precendences are executed first
        public abstract ExpressionValue Execute(ExpressionValue left, ExpressionValue right);
    }


    public abstract class ExpressionValue
    {
    }


}