Calculator.cs

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Diagnostics.Contracts;

namespace Calculator
{
    enum SyntaxKind
    {
        Plus,
        Minus,
        Star,
        Carot,
        BinOp,
        OpenBracket,
        CloseBracket,
        Number,
        End,
    }

    struct Token
    {
        public Token(SyntaxKind kind, object value)
        {
            Kind = kind;
            Value = value;
        }

        public SyntaxKind Kind { get; }
        public object Value { get; }
    }

    public class EvalException : Exception
    {
        public EvalException() { }
    }

    enum Association
    {
        Left, Right,
    }

    public static class Calculator
    {
        public static int Eval(string expr)
        {
            var tokens = Tokenize(expr).GetEnumerator();
            int EatNumber()
            {
                //TODO: there must be a better way.
                var token = tokens.Current;
                int sign = 1;
                switch (token.Kind)
                {
                    case SyntaxKind.Minus:
                        sign = -1;
                        goto case SyntaxKind.Plus;
                    case SyntaxKind.Plus:
                        if (!tokens.MoveNext())
                            ThrowEval();
                        token = tokens.Current;
                        if (token.Kind == SyntaxKind.Number)
                        {
                            goto case SyntaxKind.Number;
                        }
                        if (token.Kind == SyntaxKind.OpenBracket)
                        {
                            goto case SyntaxKind.OpenBracket;
                        }
                        break;
                    case SyntaxKind.Number:
                        return checked(sign * (int)token.Value);
                    case SyntaxKind.OpenBracket:
                        if (!tokens.MoveNext())
                            ThrowEval();
                        return checked(sign * EvalImpl(0, SyntaxKind.CloseBracket));
                    default:
                        throw new EvalException();
                }

                throw new EvalException();
            }

            bool IsOP(SyntaxKind kind)
            {
                return kind < SyntaxKind.BinOp;
            }

            int GetPred(SyntaxKind kind)
            {
                Contract.Requires(IsOP(kind));
                switch (kind)
                {
                    case SyntaxKind.Plus:
                    case SyntaxKind.Minus:
                        return 1;
                    case SyntaxKind.Star:
                        return 2;
                    case SyntaxKind.Carot:
                        return 3;
                    default:
                        Debug.Assert(false);
                        break;
                }
                int fuckCSharp = 0;
                return fuckCSharp;
            }

            int Pow(int left, int right)
            {
                int result = 1;
                for (int i = 0; i < right; ++i)
                    result = checked(result * left);
                return result;
            }

            int CalculateBinOp(int left, int right, SyntaxKind op)
            {
                Contract.Requires(IsOP(op));
                switch (op)
                {
                    case SyntaxKind.Plus:
                        return checked(left + right);
                    case SyntaxKind.Minus:
                        return checked(left - right);
                    case SyntaxKind.Star:
                        return checked(left * right);
                    case SyntaxKind.Carot:
                        return Pow(left, right);
                    default:
                        throw new EvalException();
                }
            }

            Association GetAssociation(SyntaxKind kind)
            {
                Contract.Requires(IsOP(kind));
                switch (kind)
                {
                    case SyntaxKind.Carot:
                        return Association.Right;
                    default:
                        return Association.Left;
                }
            }

            void ThrowEval()
            {
                throw new EvalException();
            }

            int EvalImpl(int pred, SyntaxKind endToken)
            {
                var left = EatNumber();
                if (!tokens.MoveNext())
                    ThrowEval();
                while (true)
                {
                    var token = tokens.Current;
                    if (token.Kind == endToken)
                        return left;

                    if (token.Kind == SyntaxKind.End
                            && SyntaxKind.End != endToken)
                    {
                        ThrowEval();
                    }

                    var curPred = GetPred(token.Kind);
                    if (curPred >= pred)
                    {
                        int nextPred = curPred;
                        if (GetAssociation(token.Kind) == Association.Left)
                            nextPred = curPred + 1;

                        if (!tokens.MoveNext())
                            ThrowEval();
                        var right = EvalImpl(nextPred, endToken);
                        left = CalculateBinOp(left, right, token.Kind);
                    }
                    else
                        return left;
                }
            }

            if (!tokens.MoveNext())
                ThrowEval();
            return EvalImpl(0, SyntaxKind.End);
        }

        static IEnumerable<Token> Tokenize(string expr)
        {
            int current = 0;
            void SkipSpace()
            {
                while (char.IsWhiteSpace(expr[current]))
                {
                    ++current;
                }
            }

            Token ParseNumber()
            {
                var stringBuilder = new StringBuilder(20);
                while (current < expr.Length && char.IsDigit(expr[current]))
                {
                    stringBuilder.Append(expr[current]);
                    ++current;
                }
                --current;
                return new Token(SyntaxKind.Number, int.Parse(stringBuilder.ToString()));
            }

            while (current < expr.Length)
            {
                SkipSpace();
                switch (expr[current])
                {
                    case '+':
                        yield return new Token(SyntaxKind.Plus, '+');
                        break;
                    case '-':
                        yield return new Token(SyntaxKind.Minus, '-');
                        break;
                    case '*':
                        yield return new Token(SyntaxKind.Star, '*');
                        break;
                    //case '/'
                    case '^':
                        yield return new Token(SyntaxKind.Carot, '^');
                        break;
                    case '(':
                        yield return new Token(SyntaxKind.OpenBracket, '(');
                        break;
                    case ')':
                        yield return new Token(SyntaxKind.CloseBracket, ')');
                        break;
                    case '0':
                    case '1':
                    case '2':
                    case '3':
                    case '4':
                    case '5':
                    case '6':
                    case '7':
                    case '8':
                    case '9':
                        yield return ParseNumber();
                        break;
                    default:
                        throw new EvalException();
                }
                ++current;
            }
            yield return new Token(SyntaxKind.End, null);
        }
    }
}