title: Help optimize my RPN evaluation function
body: <p>My parser evaluates PEMDAS expressions by first converting from infix to postfix then uses the standard postfix evaluation rules. I parse the expression and store the tokens in a list. This precompilation is ok for me since I plan on caching the precompiled functions. </p>
  
  <p>I am trying to optimize the evaluate function (See Evaluate04 in code). On my hardware, I can get 1,000,000 evaluations in less than 600ms. Truthfully, this is fast enough I believe. Far faster than the databases access calls to get the expressions. </p>
  
  <p>I wanted to see if you guys can make it faster. Micro-optimization, complete refactoring of classes. It doesn't matter how its done. </p>
  
  <p>This is as fast as I've been able to get it, can you improve it?</p>
  
  <pre><code>using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Windows.Forms;
  
  namespace ParseTest2
  {
      public partial class Form1 : Form
      {
          public Form1()
          {
              InitializeComponent();
          }
  
          enum Operator {Add, Subtract, Multiply, Divide}
  
          enum TokenType { Variable, Value, Add, Subtract, Multiply, Divide };
  
          private class TokenFactory
          {
              public static Token Add
              {
                  get { return new Token(TokenType.Add); }
              }
              public static Token Subtract
              {
                  get { return new Token(TokenType.Subtract); }
              }
              public static Token Multiply
              {
                  get { return new Token(TokenType.Multiply); }
              }
              public static Token Divide
              {
                  get { return new Token(TokenType.Divide); }
              }
              public static Token Val(float value)
              {
                  return new Token(value);
              }
              public static Token Var(string variable)
              {
                  return new Token(variable);
              }  
          }
  
          private class Token
          {
              public readonly TokenType TokenType;
              public float Value;
              public readonly string Variable;
  
              public Token(TokenType tokenType)
              {
                  TokenType = tokenType;
                  //Value = 0;
                  //Variable = null;                
              }
              public Token(float value)
              {
                  TokenType = TokenType.Value;
                  Value = value;
                  //Variable = null;
              }
              public Token(string variable)
              {
                  //TokenType = TokenType.Variable;
                  Variable = variable;
                  //Value = 0;
              }
              public override string ToString()
              {
                  return
                      Expression.IsOperand(this) ?
                      string.Format("{0} {1} {2}", TokenType, Variable ?? "", Value) :
                      string.Format("{0}", TokenType);
              }
          }
  
          class Expression
          {
              List&lt;Token&gt; _tokens;
  
              public Action&lt;Token&gt; SetVariableValue;
  
              public Expression(string expression)
              {
                  //time to convert to postfix from infix
                  var infix = expression.Split(' ');
                  string postfix = string.Empty;
  
                  Action&lt;string&gt; add = s =&gt; {postfix += " " + s;};
                  var ops = new Stack&lt;string&gt;();
  
                  Func&lt;string, int&gt; getPrecedence = value =&gt;
                  {
                      switch(value)
                      {
                          case "*":
                          case "/":
                              return 1;
                          case "+":
                          case "-":
                              return 0;
  
                      }
                      return -1;
                  };
  
                  Func&lt;string, bool&gt; isLowerOrEqualPrecedence = val =&gt; 
                  {
                      if (ops.Count == 0) return false;
                      var op = ops.Peek();
                      int cur = getPrecedence(val);
                      int top = getPrecedence(op);
                      return cur &lt;= top;
                  };
  
                  foreach (string val in infix)
                  {
                      if ("-+*/".Contains(val))
                      {
                          if (ops.Count == 0)
                              ops.Push(val);
                          else
                          {
                              if (!isLowerOrEqualPrecedence(val))
                              {
                                  ops.Push(val);
                              }
                              else
                              {
                                  while (isLowerOrEqualPrecedence(val))
                                  {
                                      add(ops.Pop());
                                  }
                                  ops.Push(val);
                              }
                          }
                      }
                      else if (val == "(")
                          ops.Push(val);
                      else if (val == ")")
                      {
                          while (true)
                          {
                              var op = ops.Pop();
                              if (op == "(") break;
                              add(op);
                          }
                      }
                      else
                      {
                          add(val);
                      }                    
                  }
  
                  while (ops.Count &gt; 0)
                  {
                      add(ops.Pop());
                  }
  
  
                  _tokens = new List&lt;Token&gt;();
                  foreach (string x in postfix.Trim().Split(' '))
                  { 
                      switch(x)
                      {
                          case "*":
                              _tokens.Add(TokenFactory.Multiply);
                              break;
                          case "/":
                              _tokens.Add(TokenFactory.Divide);
                              break;
                          case "+":
                              _tokens.Add(TokenFactory.Add);
                              break;                        
                          case "-":
                              _tokens.Add(TokenFactory.Subtract);
                              break;
                          default:
                              _tokens.Add(TokenFactory.Var(x));
                              break;
                      }
                  }                             
              }
  
              public static bool IsOperand(Token tk)
              {
                  return tk.TokenType == TokenType.Variable || tk.TokenType == TokenType.Value;
              }
  
  
  
              public float Evaluate04()
              {
                  Token[] tokens = _tokens.ToArray();
  
                  int i;
  
                  for (i = tokens.Length - 1; i &gt;= 0; --i)
                      if (tokens[i].TokenType == TokenType.Variable)
                          SetVariableValue(tokens[i]);
  
                  int tokenCount = tokens.Length;
  
                  while (true)
                  {
                      int i1 = 0, i2 = 0, i3 = 0;
                      //i1 = i2 = i3 = -1;
                      int j;
                      Token t1, t2, t3;
  
                      //looking for operator preceded by two operands
                      for (i = 0; i &lt; tokens.Length - 2; ++i)
                      //i = 0;
                      //while( true )
                      {
                          t1 = null;
                          t2 = null;
                          t3 = null;
  
                          j = i;
                          do
                          {
                              t1 = tokens[j];
                              i1 = j++;
                          } while (t1 == null);
  
  
                          do
                          {
                              t2 = tokens[j];
                              i2 = j++;
                          } while (t2 == null);
  
                          do
                          {
                              t3 = tokens[j];
                              i3 = j++;
                          } while (t3 == null);
  
                          //it's a binary operation if t3 is an operator and t2, t1 are operands
                          //if (!IsOperand(t3) &amp;&amp; IsOperand(t2) &amp;&amp; IsOperand(t1))
                          if (
                              !(t3.TokenType == TokenType.Variable || t3.TokenType == TokenType.Value) &amp;&amp;
                               (t2.TokenType == TokenType.Variable || t2.TokenType == TokenType.Value) &amp;&amp;
                               (t1.TokenType == TokenType.Variable || t1.TokenType == TokenType.Value))
                          {
                              float val;
  
                              if (t3.TokenType == TokenType.Add)
                                  val = t1.Value + t2.Value;
                              else if (t3.TokenType == TokenType.Divide)
                                  val = t1.Value / t2.Value;
                              else if (t3.TokenType == TokenType.Subtract)
                                  val = t1.Value - t2.Value;
                              else if (t3.TokenType == TokenType.Multiply)
                                  val = t1.Value * t2.Value;
                              else
                                  val = int.MinValue;
  
                              //we're done, return
                              if (tokenCount == 3)
                                  return val;
  
                              tokenCount -= 2;
  
                              //ok, we are done processing these, null them
                              tokens[i1] = new Token(val);
                              tokens[i2] = null;
                              tokens[i3] = null;
  
                              //break, for loop and repeat until done
                              break;
                          }
                      }
                  }
              }
          }
          private void Form1_Load(object sender, EventArgs e)
          {
  
              Action&lt;Token&gt; setVariableValue = token =&gt;
              {
                  if (token.Variable == "A")
                      token.Value = 4;
                  else if (token.Variable == "B")
                      token.Value = 5;
                  else if (token.Variable == "C")
                      token.Value = 7;
                  else if (token.Variable == "D")
                      token.Value = 2;
              };
  
              //spaces are required because I'm splitting on them.
              //I know it's lame, it's a detail I'll address later...
              var x = new Expression("( A + B ) / ( C + D )");
              x.SetVariableValue = setVariableValue;
              Func&lt;float&gt; eval = x.Evaluate04;
              eval();
              int count = 1000000;
              float res = 0;
  
              var sw = new System.Diagnostics.Stopwatch();
  
              //sw.Start();
              //Parallel.ForEach(Enumerable.Range(1, count), i =&gt;
              //{
              //    res = eval();
              //});
              //sw.Stop();
              //Console.WriteLine("{0} takes: {1}", "parallel", sw.ElapsedMilliseconds);
  
              sw.Reset();
              sw.Start();
  
              //for(int i=0; i&lt;count; ++i)
              foreach (int i in Enumerable.Range(1, count))
              {
                  res = eval();
              }
              sw.Stop();
              Console.WriteLine("{0} takes: {1}", "single thread", sw.ElapsedMilliseconds);
              Console.WriteLine("{0}", res);
  
          }
  
          private void Form1_KeyDown(object sender, KeyEventArgs e)
          {
              if (e.KeyCode == Keys.Escape)
                  Close();
  
          }         
      }
  }
  </code></pre>