I successfully created an expression evaluator in C#, and I would like to know if it works well, and what I can do to improve it.
class ExpressionEvaluator2
{
public enum Token
{
None,
Literal,
Variable,
Operator,
Function,
FunctionArgumentSeparator,
LeftParanthesis,
RightParanthesis
};
private List<KeyValuePair<Token, string>> tokens = new List<KeyValuePair<Token, string>> ();
private List<KeyValuePair<Token, string>> output = new List<KeyValuePair<Token, string>> ();
private Dictionary<string, double> variables = new Dictionary<string, double>();
public List<KeyValuePair<Token, string>> Tokens { get { return tokens; } }
public List<KeyValuePair<Token, string>> Output { get { return output; } }
public Dictionary<string, double> Variables { get { return variables; } }
public ExpressionEvaluator2()
{
Variables.Add("pi", Math.PI);
Variables.Add("e", Math.E);
}
public string Expression { get; set; }
public void Tokenize()
{
tokens.Clear();
for (int i = 0; i < Expression.Length; i++)
{
if (char.IsWhiteSpace(Expression[i])) continue;
if (IsOperator(Expression[i]))
{
// Unary minus
if (Expression[i] == '-' && (tokens.Count == 0 || tokens.Last().Key == Token.LeftParanthesis || tokens.Last().Key == Token.Operator))
tokens.Add(new KeyValuePair<Token, string>(Token.Operator, "!-"));
// Any other operator
else tokens.Add(new KeyValuePair<Token, string>(Token.Operator, Expression[i].ToString()));
}
else if (Expression[i] == '(')
tokens.Add(new KeyValuePair<Token, string>(Token.LeftParanthesis, Expression[i].ToString()));
else if (Expression[i] == ')')
tokens.Add(new KeyValuePair<Token, string>(Token.RightParanthesis, Expression[i].ToString()));
else if (Expression[i] == ',')
tokens.Add(new KeyValuePair<Token, string>(Token.FunctionArgumentSeparator, Expression[i].ToString()));
else if (Char.IsDigit(Expression[i]))
tokens.Add(new KeyValuePair<Token, string>(Token.Literal, GetLiteral(Expression, ref i)));
else if (Char.IsLetter(Expression[i]))
{
if (IsFunction(Expression, i)) tokens.Add(new KeyValuePair<Token, string>(Token.Function, GetVariable(Expression, ref i)));
else tokens.Add(new KeyValuePair<Token, string>(Token.Variable, GetVariable(Expression, ref i)));
}
else throw new Exception("Unrecognized character found!");
}
}
public void ShuntingYard()
{
Stack<KeyValuePair<Token, string>> stack = new Stack<KeyValuePair<Token, string>>();
foreach (var i in Tokens) switch (i.Key)
{
case Token.Variable:
case Token.Literal: output.Add(i); break;
case Token.Function: stack.Push(i); break;
case Token.FunctionArgumentSeparator:
while (stack.Peek().Key != Token.LeftParanthesis) {
output.Add(stack.Pop());
if (stack.Count == 0) throw new Exception("Syntax error!");
}
break;
case Token.Operator:
if (IsLeftAssociative(i.Value)) {
while (stack.Count != 0 && Precedence(i.Value) <= Precedence(stack.Peek().Value))
output.Add(stack.Pop());
}
else {
while (stack.Count != 0 && Precedence(i.Value) < Precedence(stack.Peek().Value))
output.Add(stack.Pop());
}
stack.Push(i);
break;
case Token.LeftParanthesis: stack.Push(i); break;
case Token.RightParanthesis:
while (stack.Peek().Key != Token.LeftParanthesis) {
output.Add(stack.Pop());
if (stack.Count == 0) throw new Exception("Mismatched parantheses!");
}
stack.Pop(); // Pop paranthesis
if (stack.Peek().Key == Token.Function) output.Add(stack.Pop()); // Pop function
break;
}
while (stack.Count > 0)
{
if (stack.Peek().Key == Token.LeftParanthesis) throw new Exception("Mismatched parantheses!");
output.Add(stack.Pop());
}
}
public double Evaluate()
{
Stack<double> stack = new Stack<double>();
foreach (var i in Output)
switch (i.Key)
{
case Token.Variable:
if (!Variables.ContainsKey(i.Value)) throw new Exception("Variable missing: " + i.Value);
stack.Push(Variables[i.Value]);
break;
case Token.Literal: stack.Push(double.Parse(i.Value)); break;
case Token.Operator:
switch (i.Value)
{
case "!-": stack.Push(stack.Pop() * -1); break;
case "+": stack.Push(stack.Pop() + stack.Pop()); break;
case "-": {
double b = stack.Pop();
double a = stack.Pop();
stack.Push(a - b);
} break;
case "*": stack.Push(stack.Pop() * stack.Pop()); break;
case "/": {
double b = stack.Pop();
double a = stack.Pop();
stack.Push(a / b);
} break;
case "%": {
double b = stack.Pop();
double a = stack.Pop();
stack.Push(a % b);
} break;
case "^": {
double b = stack.Pop();
double a = stack.Pop();
stack.Push(Math.Pow(a,b));
} break;
}
break;
case Token.Function:
EvaluateFunction(i.Value, ref stack);
break;
}
return stack.Pop();
}
void EvaluateFunction(string func, ref Stack<double> stack)
{
switch (func)
{
case "sin": stack.Push(Math.Sin(stack.Pop())); break;
case "cos": stack.Push(Math.Cos(stack.Pop())); break;
case "tan": stack.Push(Math.Tan(stack.Pop())); break;
case "ctan": stack.Push(1 / Math.Tan(stack.Pop())); break;
case "arcsin": stack.Push(Math.Asin(stack.Pop())); break;
case "asin": stack.Push(Math.Asin(stack.Pop())); break;
case "arccos": stack.Push(Math.Acos(stack.Pop())); break;
case "acos": stack.Push(Math.Acos(stack.Pop())); break;
case "arctan": stack.Push(Math.Atan(stack.Pop())); break;
case "atan": stack.Push(Math.Atan(stack.Pop())); break;
case "int": stack.Push(Math.Truncate(stack.Pop())); break;
case "abs": stack.Push(Math.Abs(stack.Pop())); break;
case "max": stack.Push(Math.Max(stack.Pop(), stack.Pop())); break;
case "min": stack.Push(Math.Min(stack.Pop(), stack.Pop())); break;
case "sqrt": stack.Push(Math.Sqrt(stack.Pop())); break;
case "cbrt": stack.Push(Math.Pow(stack.Pop(), 1.0 / 3.0)); break;
case "lg": stack.Push(Math.Log10(stack.Pop())); break;
case "log": stack.Push(Math.Log(stack.Pop(), stack.Pop())); break;
case "ln": stack.Push(Math.Log(stack.Pop(), Math.E)); break;
default: throw new Exception("Unknown function " + func);
}
}
#region Helper routines
private static bool IsLeftAssociative (string op)
{
return (op != "^");
}
private static int Precedence(string op)
{
switch (op)
{
case "+":
case "-": return 1;
case "*":
case "/":
case "%": return 2;
case "^": return 3;
case "!-": return 10;
default: return 0;
}
}
private static bool IsOperator(char c)
{
const string operators = "+-*/%^";
return operators.Contains(c);
}
private static bool IsFunction(string s, int index)
{
// Skip function/variable name
while (index < s.Length && char.IsLetterOrDigit(s[index])) index++;
while (index < s.Length && char.IsWhiteSpace(s[index])) index++;
// End of string? Than it's a variable
if (index >= s.Length) return false;
// If an operator, function separator, or ), variable
if (s[index] == '(') return true;
return false;
}
private static string GetVariable(string s, ref int index)
{
StringBuilder str = new StringBuilder();
while (index < s.Length && (char.IsLetterOrDigit(s[index])))
str.Append(s[index++]);
index -= 1;
return str.ToString();
}
private static string GetLiteral(string s, ref int index)
{
StringBuilder str = new StringBuilder();
while (index < s.Length && (char.IsDigit(s[index]) || s[index] == '.'))
str.Append (s[index++]);
index -= 1;
return str.ToString();
}
#endregion
}
To evaluate an expression, first the expression needs to be tokenized using the Tokenize method. After that, apply the ShuntingYard algorithm to prepare the expression. In the end, it can evaluate the expression (assuming you give values to all the input variables).
I didn't manage to test it very thoroughly, and I don't even know how to test for large expressions that I can't calculate in my head.
