Interview Question: Create a Calculator

September 17, 2012 nateb Interviewing, Technology, 0

For a recent interview question I was asked to write a method that would evaluate a string such as “-2+5*4/2+1″ into the value 9.

My solution was done in 3 parts; first tokenize the string so each block of digits or operator can be addressed at the same time.

public static float Evaluate(string expression)
{
  if (string.IsNullOrEmpty(expression))
    throw new ArgumentNullException("expression");

  //
  //  First tokenize the string
  var tokens = new List<string>();
  var token = string.Empty;
  for (var i = 0; i < expression.Length; i++)
  {
    if (IsOperator(expression[i]))
    {
      //
      //  If the expression starts with a negative number
      if (expression[i] == '-' && tokens.Count == 0 
              && string.IsNullOrEmpty(token))
      {
        token = "-";
        continue;
      }

      if (!string.IsNullOrEmpty(token))
      {
        tokens.Add(token);
        token = string.Empty;
      }

      tokens.Add(expression[i].ToString());

      //
      //  Handle case of negative numbers such as: 2*-3
      if (expression[i + 1] == '-')
      {
        token = "-";
        ++i;
        continue;
      }
    }
    else if (char.IsDigit(expression[i]))
    {
      token += expression[i];
    }
    else if (char.IsWhiteSpace(expression[i]))
    {
      if (!string.IsNullOrEmpty(token))
      {
        tokens.Add(token);
        token = string.Empty;
      }
      continue;
    }
    else
       throw new InvalidOperationException
           ("Invalid char:" + expression[i]);
  }

  if (!string.IsNullOrEmpty(token))
    tokens.Add(token);

Then process all the multiply and divide operations

 
 //
 //  Process any multiple/divide requests
 for (var i = 0; i < tokens.Count; )
 {
   var currentToken = tokens[i];
   if (currentToken == "*" || currentToken == "/")
   {
     var left = tokens[i - 1];
     var right = tokens[i + 1];
     var value = string.Empty;

     if (currentToken == "*")
       value = Convert.ToString
           (float.Parse(left) * float.Parse(right));
     else
       value = Convert.ToString
           (float.Parse(left) / float.Parse(right));

     //
     //  Update the left value and remove the processed operators
     tokens[i - 1] = value;
     tokens.RemoveAt(i + 1);
     tokens.RemoveAt(i);
   }
   else
   i++;
 }

Finally process any add or subtract operations

 //
 //  Process any add/subtract requests
 float finalValue = float.Parse(tokens[0]);
 for (var i = 1; i < tokens.Count; i++)
 {
   var currentToken = tokens[i];
   if (currentToken == "+")
   {
     finalValue += float.Parse(tokens[++i]);
   }
   else
   {
     finalValue -= float.Parse(tokens[++i]);
   }
  }

  //
  //  Return the final value
  return finalValue;
}

For completeness-

static bool IsOperator(char ch)
{
  return new char[] { '+', '-', '/', '*' }.Contains(ch);
}

Win2k12: How to Use Active Directory Certificate Services Interview Question: Process a Binary Tree