Mathematical expression evaluator.

Question

Code reviews and suggestions to improve coding style are welcome.

using ExpressionEvaluatorLibrary;
namespace ExpressionEvaluator
{
  class Program
  {
    static void Main(string[] args)
    {
       ConsoleKeyInfo cki = new ConsoleKeyInfo();

        Console.WriteLine(" Mathematical Expression Evaluation");
        Console.WriteLine("Maximum length    : 250 characters");
        Console.WriteLine("Allowed Operators : +, -, *, /");

        do
        {
            string strUserInput = "";
            if (args.Length == 0)
            {
                Console.Write("\n\nEnter an Expression: ");
                strUserInput = Console.ReadLine();
            }
            else
            {
                // TO be able to run from command prompt.
                strUserInput = args[0];
            }

            IExpressionModel expressionModel = new ExpressionModel();

            string strValidate = expressionModel.ExpressionValidate(strUserInput);

            if (strValidate == "Valid")
            {
                try
                {
                    string strPostFixExpression = expressionModel.ConvertToPostfix(strUserInput);
                    // Console.WriteLine(strPostFixExpression);

                    string strResult = expressionModel.EvaluateExpression(strPostFixExpression);
                    Console.WriteLine("\n       The result is: " + strResult);
                }
                catch (Exception e)
                {
                    Console.WriteLine(e);
                }                    
            }
            else
            {
                Console.WriteLine(strValidate);
            }

            Console.WriteLine("\nPress any key to continue; press the 'Esc' key to quit.");
            cki = Console.ReadKey(false);

        } while (cki.Key != ConsoleKey.Escape);
    }
 }
}


namespace ExpressionEvaluatorLibrary
{
  public interface IExpressionModel
  {
    string ExpressionValidate(string strUserEntry);
    string ConvertToPostfix(string strValidExpression);
    string EvaluateExpression(string strPostFixExpression);
  }
}


namespace ExpressionEvaluatorLibrary
{
  public class ExpressionModel : IExpressionModel
  {


    public string ExpressionValidate(string strUserEntry)
    {
        strUserEntry = strUserEntry.Trim();

        if (string.IsNullOrEmpty(strUserEntry))
            return "There was no entry.";

        if (strUserEntry.Length > 250) //250 seemed better than 254
            return "More than 250 characters entered.";

        string[] fixes = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" };

        bool boolStartsWith = fixes.Any(prefix => strUserEntry.StartsWith(prefix));
        if (!boolStartsWith)
            return "The expression needs to start with a number.";

        bool boolEndsWith = fixes.Any(postfix => strUserEntry.EndsWith(postfix));
        if (!boolEndsWith)
            return "The expression needs to end with a number.";

        if (!Regex.IsMatch(strUserEntry, "^[-0-9+*/ ]+$"))
            return "There were characters other than Numbers, +, -, * and /.";

        if (!Regex.IsMatch(strUserEntry, "[-+*/]"))
            return "Not a mathematical expression";

        string[] strOperator = Regex.Split(strUserEntry, @"\d+");
        for (int i = 1; i < strOperator.Length - 1; i++) //the first and last elements of the array are empty
        {
            if (strOperator[i].Trim().Length > 1)
                return "Expression cannot have operators together '" + strOperator[i] + "'.";
        }

        return "Valid";
    }



    public string ConvertToPostfix(string strValidExpression)
    {

        StringBuilder sbPostFix = new StringBuilder();
        Stack<Char> stkTemp = new Stack<char>();

        for (int i = 0; i < strValidExpression.Length; i++)
        {
            char chExp = strValidExpression[i];

            if (chExp == '+' || chExp == '-' || chExp == '*' || chExp == '/')
            {
                sbPostFix.Append(" ");

                if (stkTemp.Count <= 0)
                    stkTemp.Push(chExp);
                else if (stkTemp.Peek() == '*' || stkTemp.Peek() == '/')
                {
                    sbPostFix.Append(stkTemp.Pop()).Append(" ");
                    i--;
                }
                else if (chExp == '+' || chExp == '-')
                {
                    sbPostFix.Append(stkTemp.Pop()).Append(" ");
                    stkTemp.Push(chExp);
                }
                else
                {
                    stkTemp.Push(chExp);
                }
            }
            else
            {
                sbPostFix.Append(chExp);
            }
        }

        for (int j = 0; j <= stkTemp.Count; j++)
        {
            sbPostFix.Append(" ").Append(stkTemp.Pop());
        }

        string strPostFix = sbPostFix.ToString();
        strPostFix = Regex.Replace(strPostFix, @"[ ]{2,}", @" ");
        return strPostFix;
    }

    public string EvaluateExpression(string strPostFixExpression)
    {
        Stack<string> stkTemp = new Stack<string>();
        string strOpr = "";
        string strNumLeft = "";
        string strNumRight = "";

        List<String> lstPostFix = strPostFixExpression.Split(' ').ToList();

        for (int i = 0; i < lstPostFix.Count; i++)
        {
            stkTemp.Push(lstPostFix[i]);
            if (stkTemp.Count >= 3)
            {
                Func<string, bool> myFunc = (c => c == "+" || c == "-" || c == "*" || c == "/");
                bool isOperator = myFunc(stkTemp.Peek());

                if (isOperator)
                {
                    strOpr = stkTemp.Pop();
                    strNumRight = stkTemp.Pop();
                    strNumLeft = stkTemp.Pop();

                    double dblNumLeft, dblNumRight;
                    bool isNumLeft = double.TryParse(strNumLeft, out dblNumLeft);
                    bool isNumRight = double.TryParse(strNumRight, out dblNumRight);

                    if (isNumLeft && isNumRight)
                    {
                        double dblTempResult;
                        switch (strOpr)
                        {
                            case ("+"):
                                dblTempResult = dblNumLeft + dblNumRight;
                                stkTemp.Push(dblTempResult.ToString());
                                break;
                            case ("-"):
                                dblTempResult = dblNumLeft - dblNumRight;
                                stkTemp.Push(dblTempResult.ToString());
                                break;
                            case ("*"):
                                dblTempResult = dblNumLeft * dblNumRight;
                                stkTemp.Push(dblTempResult.ToString());
                                break;
                            case ("/"):
                                dblTempResult = dblNumLeft / dblNumRight;
                                stkTemp.Push(dblTempResult.ToString());
                                break;
                        }
                    }
                }
            }
        }

        return stkTemp.Pop();
     }
  }
}

Answer 1

1. If I'm not mistaken your acceptable input expressions are in infix notation and look like this:

   number [+-*/] number [+-*/] number ....
   

   In that case you can greatly simplify you validation check with a single regular expression:

   ^\d+(\s*[+-*/]\s*\d+)+$
   

   It checks for strings starting with a number composed out of 1 or more digits followed by 1 or more groups of [+-*/] number. The \s* allows any number of white spaces between operators and numbers.

2. When you validate you should not return a string representing the validation result. Two alternative options:

   1. Return a ValidationResult object like this:

      class ValidationResult
      {
          bool readonly IsValid;
          string readonly FailureReason;
      
          private ValidationResult() { }
      
          public static ValidationResult Valid()
          {
              return new ValidationResult { IsValid = true; }
          }
      
          public static ValidationResult Invalid(string reason)
          {
              return new ValidationResult { IsValid = false; FailureReason = reason; }
          }
      }
      

      Use: return ValidationResult.Invalid("some error")

   2. Throw a ValidationException with the message as the failure reason and catch it when calling the validation method and log/display the message to the user.

3. You are doing a lot of parsing and re-parsing by passing everything around as strings. This is not really a good way of doing it and also very inefficient as you are constantly throwing away information and having to reconstruct it via parsing it out of the string.

   Here is how I would split it up:

   • Write a tokenizer which splits the input string into tokens (numbers and operators) and provides the next token to the parser
   • The parser should build the expression tree. The operators should be the nodes and the leaves are the numbers. This way you can traverse it anyway you like infix, postfix, prefix and you retain the information about the parsed input.
   • Evaluating just means to traverse the tree and evaluate the nodes and the operands.

   Some skeleton code:

   The nodes of the tree:

   interface INode
   {
       double Evaluate();
   }
   
   abstract class Operator : INode
   {
       protected readonly INode Left;
       protected readonly INode Right;
   
       protected Operator(INode left, INode right)
       {
           Left = left;
           Right = right;
       }
   
       public abstract double Evaluate();
   
       public static Operator FromString(string op, INode left, INode right)
       {
           switch (op)
           {
               case "+": return new Add(left, right);
               case "-": return new Sub(left, right);
               case "*": return new Mul(left, right);
               case "/": return new Div(left, right);
               default: throw new ArgumentException("Invalid operator", "op");
           }
       }
   }
   
   class Add : Operator
   {
        public Add(INode left, INode right) : base(left, right) {}
   
        public override double Evaluate()
        {
            return Left.Evaluate() + Right.Evaluate();
        }
   }
   
   // ...
   // similar classes for Sub, Mul And Div 
   // ...
   
   class Constant : INode
   {
       private readonly double _Number;
   
       public Constant(double number)
       {
            _Number = number;
       }
   
       public double Evaluate() 
       { 
            return _Number;
       }
   }
   

   Parsing (will only deal with valid input):

   public IEnumerable<string> Tokenize(string input)
   {
       // assuming only spaces or tabs are allowed in the expression
       return string.Split(new [] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
   }
   
   public INode ParseTokens(IEnumerable<string> tokens)
   { 
       INode left = new Constant(Double.Parse(tokens.First()));
   
       tokens = tokens.Skip(1);
   
       // last token of expression is always a number
       if (!tokens.Any()) return left;
   
       var op = tokens.First();
   
       // recursive descending
       INode right = ParseTokens(tokens.Skip(1));
   
       return Operator.FromString(op, left, right);
   }
   

   Actually evaluating the input becomes:

   double EvaluateInput(string input)
   {
       var tokens = Tokenize(input);
       var root ParseToken(tokens);
       return root.Evaluate();
   }
   

   Ideally you actually create a Tokenizer class which gets instantiated with the input string and where you can call Next() on which will return the next token. The tokenizer should be passed to the parse method. I just used simple IEnumerable because it was quicker to show the basic concept.