Wednesday, September 12, 2012

Basic expression evaluator

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

using ExpressionComputer.Utility;

namespace ExpressionComputer
{   
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("6 == {0}\n", Exp.Compute ("1 + 2 * 3 - 4 + 5 * 6 / 2 - 2 * 3 ^ 2 + ( 5 - 2 ) * 2"));


            Console.WriteLine("19 == {0}\n", Exp.Compute("1 + 2 * 3 ^ 2"));


            Console.WriteLine("{0}\n", Exp.ConvertToRpnString("1 + 2 + 3 + 4 + 5"));

            string orig = "1 + 2 * 3 + 4";
            Console.WriteLine(orig);
            IList<string> rpn = Exp.ConvertToRpn(orig);
            Console.WriteLine(Exp.ConvertRpnToString(rpn));
            int n = Exp.ComputeRpn(rpn);
            Console.WriteLine("11 == {0}\n", n);



            string orig2 = "1 + 2 * ( 3 + 4 )";
            Console.WriteLine(orig2);
            IList<string> rpn2 = Exp.ConvertToRpn(orig2);
            Console.WriteLine("{0}", Exp.ConvertRpnToString(rpn2));
            Console.WriteLine("15 == {0}\n", Exp.ComputeRpn(rpn2));


            Console.WriteLine("23 == {0}", Exp.Compute("1 + 2 * 3 + 4 + 2 * 6"));
            Console.WriteLine("17 == {0}\n", Exp.Compute("1 + 2 * 3 + 4 + 2 * 6 / 2"));


            string orig3 = "1 + 2 * 3 + 4 + 2 * 6 / 2 - 1";
            Console.WriteLine ("{0}",orig3);
            string exp2 = Exp.ConvertToRpnString(orig3);
            Console.WriteLine(exp2);
            Console.WriteLine("16 == {0}", Exp.Compute(orig3));

            
            




            Console.ReadLine();
        }
    }


    public static class Exp
    {

        public static string ConvertRpnToString(IList<string> rpn)
        {
            return string.Join(" ", rpn.ToArray());
        }

        public static string ConvertToRpnString(string exp)
        {
            var rpn = Exp.ConvertToRpn(exp);

            return string.Join(" ", rpn.ToArray());
        }

        public static IList<string> ConvertToRpn(string exp)
        {
            IList<string> output = new List<string>();
            Stack<string> opStack = new Stack<string>();

            string[] tokens = exp.Split(' ');

            foreach (var token in tokens)
            {
                bool isOperator = token.IsOperator();

                if (token == "(" || token == ")")
                {
                    if (token == "(")
                    {
                        opStack.Push(token);
                    }
                    else if (token == ")")
                    {
                        string op = "";
                        while ((op = opStack.Pop()) != "(")
                        {
                            output.Add(op);
                        }

                    }

                }
                else if (!isOperator)
                {
                    output.Add(token);
                }
                else
                {
                    while (opStack.Count > 0 && 
                                (
                                    (token.IsLeftAssociative() && token.OperatorPrecedence() <= opStack.Peek().OperatorPrecedence())
                                    ||
                                    (token.OperatorPrecedence() < opStack.Peek().OperatorPrecedence())
                                )                       
                          )
                    {
                        output.Add(opStack.Pop());
                    }
                    opStack.Push(token);
                }
            }

            while (opStack.Count > 0)
                output.Add(opStack.Pop());


            return output;
        }

        public static int Compute(string expr)
        {
            return ComputeRpn(ConvertToRpn(expr));
        }

        public static int ComputeRpn(IList<string> rpn)
        {
            Stack<string> values = new Stack<string>();

            int n = 0;
            foreach (string token in rpn)
            {
                bool isOperator = token.IsOperator();

                if (isOperator)
                {
                    int opB = int.Parse(values.Pop());
                    int opA = int.Parse(values.Pop());
                    int result = 0;
                    switch (token)
                    {
                        case "*":
                            result = opA * opB;
                            break;
                        case "/":
                            result = opA / opB;
                            break;
                        case "+":
                            result = opA + opB;
                            break;
                        case "-":
                            result = opA - opB;
                            break;
                        case "^":
                            result = (int)Math.Pow((double)opA, (double)opB);
                            break;
                    }
                    values.Push(result.ToString());
                }
                else
                {
                    values.Push(token);
                }
            }

            return int.Parse(values.Pop());
        }
    }

}

namespace ExpressionComputer.Utility
{
    public static class Helper
    {

        public static int OperatorPrecedence(this string op)
        {
            switch (op)
            {
                case "^":
                    return 3;
                case "*":
                case "/":
                    return 2;
                case "+":
                case "-":
                    return 1;
            }
            return 0;
        }

        public static bool HasLowerOrEqualPrecedenceThan(this string opA, string opB)
        {
            return opA.OperatorPrecedence() <= opB.OperatorPrecedence();
        }

        public static bool IsOperator(this string token)
        {
            return new[] { "*", "/", "+", "-", "^" }.Contains(token);
        }

        public static bool IsRightAssociative(this string token)
        {
            return new[] { "^" }.Contains(token);
        }

        public static bool IsLeftAssociative(this string token)
        {
            return !token.IsRightAssociative();
        }
    }


}


This can properly evaluate operator precedence between multiplication, division, addition & subtraction.


Output:
6 == 6

19 == 19

1 2 + 3 + 4 + 5 +

1 + 2 * 3 + 4
1 2 3 * + 4 +
11 == 11

1 + 2 * ( 3 + 4 )
1 2 3 4 + * +
15 == 15

23 == 23
17 == 17

1 + 2 * 3 + 4 + 2 * 6 / 2 - 1
1 2 3 * + 4 + 2 6 * 2 / + 1 -
16 == 16

IDEONE: http://ideone.com/rFVXGT

No comments:

Post a Comment