precedenceClimbing.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Linq;
using System.Text;

namespace PrecedenceClimbing
{
    internal enum TokenType
    {
        Plus,
        Minus,
        Div,
        Mul,
        Number,
        Id,
        Eof
    }

    [DebuggerDisplay("{TokenType} [{Source}]")]
    internal class Token
    {
        public TokenType TokenType { get; set; }
        public string Source { get; set; }

        private static readonly Dictionary<TokenType, int> precedence = new Dictionary<TokenType, int>
        {
            {TokenType.Plus, 1},
            {TokenType.Minus, 1},
            {TokenType.Div, 2},
            {TokenType.Mul, 2}
        };

        public Token(TokenType tokenType)
        {
            TokenType = tokenType;
        }

        public Token(TokenType tokenType, string source)
        {
            TokenType = tokenType;
            Source = source;
        }

        public bool IsNumber()
        {
            return TokenType == TokenType.Number;
        }

        public bool IsOperator()
        {
            return precedence.Keys.Contains(TokenType);
        }

        public int Precedence()
        {
            return precedence[TokenType];
        }

        public bool IsEof()
        {
            return TokenType == TokenType.Eof;
        }
    }

    internal class Program
    {
        private static List<Token> tokenize(string str)
        {
            List<Token> tokens = new List<Token>();

            Func<string, int, Func<Char, bool>, string> Accum = (inputStr, index, cond) =>
            {
                StringBuilder buf = new StringBuilder();
                while (index < inputStr.Length && cond(inputStr[index]))
                {
                    buf.Append(inputStr[index++]);
                }

                return buf.ToString();
            };

            for (int i = 0; i < str.Length; i++)
            {
                if (Char.IsWhiteSpace(str, i))
                    continue;

                if (Char.IsDigit(str, i))
                {
                    string source = Accum(str, i, Char.IsDigit);
                    tokens.Add(new Token(TokenType.Number, source));
                    i += source.Length - 1;
                    continue;
                }

                if (Char.IsLetter(str, i))
                {
                    string source = Accum(str, i, Char.IsLetter);
                    tokens.Add(new Token(TokenType.Id, source));
                    i += source.Length - 1;
                    continue;
                }

                switch (str[i])
                {
                    case '+':
                        tokens.Add(new Token(TokenType.Plus, "+"));
                        break;
                    case '-':
                        tokens.Add(new Token(TokenType.Minus, "-"));
                        break;
                    case '/':
                        tokens.Add(new Token(TokenType.Div, "/"));
                        break;
                    case '*':
                        tokens.Add(new Token(TokenType.Mul, "*"));
                        break;
                }
            }

            tokens.Add(new Token(TokenType.Eof));

            return tokens;
        }


        private class Evaluator
        {
            private readonly List<Token> tokens;
            private int index;

            public Evaluator(List<Token> tokens)
            {
                this.tokens = tokens;
            }

            private Token computeAtom()
            {
                Token tok = currentToken();

                if (!tok.IsNumber())
                    throw new Exception("Number was expected");

                nextToken();
                return tok;
            }

            private Token currentToken()
            {
                return tokens[index];
            }

            private void nextToken()
            {
                index++;
            }

            private Token computeOperator(Token lhs, Token rhs, Token op)
            {
                if (!lhs.IsNumber() || !rhs.IsNumber())
                    throw new Exception("Only numbers can be computed");

                if (!op.IsOperator())
                    throw new Exception("Operator is expected");

                int left = int.Parse(lhs.Source);
                int right = int.Parse(rhs.Source);

                switch (op.TokenType)
                {
                    case TokenType.Plus:
                        return new Token(TokenType.Number, (left + right).ToString(CultureInfo.CurrentCulture));
                    case TokenType.Minus:
                        return new Token(TokenType.Number, (left - right).ToString(CultureInfo.CurrentCulture));
                    case TokenType.Mul:
                        return new Token(TokenType.Number, (left*right).ToString(CultureInfo.CurrentCulture));
                    case TokenType.Div:
                        return new Token(TokenType.Number, (left/right).ToString(CultureInfo.CurrentCulture));
                    default:
                        throw new Exception("Unknown operation");
                }
            }

            public Token eval(int minPrec = 0)
            {
                var result = computeAtom();

                while (currentToken().IsOperator() && currentToken().Precedence() >= minPrec)
                {
                    Token op = currentToken();
                    nextToken();

                    int nextMinPrec = op.Precedence() + 1;
                    var rhs = eval(nextMinPrec);
                    result = computeOperator(result, rhs, op);
                }

                return result;
            }
        }

        private static void Main()
        {
            List<Token> tokens = tokenize("3 + 5 * 2");
            Evaluator evaluator = new Evaluator(tokens);
            var resultToken = evaluator.eval();
            var resultStr = resultToken.Source;
            Console.WriteLine("Result: " + resultStr);
            Console.WriteLine("end");
        }
    }
}