Download Source Code
Introduction
A requirement that comes up from time to time is the ability to evaluate an expression provided by the user. Although languages like C# can evaluate complex expressions within your code, being able to evaluate an expression from a string is another matter. While I've seen a few strange tricks to accomplish this task, as usual, my approach is simply to write my own code from scratch.
The Eval Class
Listing 1 shows my Eval class. This class is designed to evaluate numeric expressions. It supports four binary operators (+, -, *, /), two unary operators (+, -), parentheses to control evaluation order, and even provides support for expressions that contain symbols (variables or constants) and functions.
The Execute() method takes a string argument that contains the expression to be evaluated. It starts by calling TokenizeExpression(), which breaks the expression into distinct tokens. These tokens are stored in a list in Reverse Polish Notation (RPN) order.
RPN, which is also known as Postfix notation, puts the operands first, followed by the operators. For example, "3 + 4" (which is considered Infix notation) would be rewritten as "3 4 +". It is much easier to write code to evaluate an expression that uses Postfix notation than it is to evaluate one that uses Infix notation.
RPN does not include any parentheses. If any parentheses existed in the original expression, TokenizeExpression() uses them to determine the correct RPN order and then discards them. This method uses a stack to help track tokens while converting from Infix to Postifx ordering.
Once the expression is tokenized in RPN order, the ExecuteTokens() method is called to evaluate those tokens. Compared to TokenizeExpression(), this method is very simple. It returns the result of the expression as a double.
The Eval class defines its own custom exception class, EvalException, which includes support for tracking the column position where the exception occurred. This information can be used to help the user identify the cause of the error.
Listing 1: Eval Class
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SoftCircuits
{
/// <summary>
/// Custom exception for evaluation errors
/// </summary>
public class EvalException : Exception
{
/// <summary>
/// Zero-base position in expression where exception occurred
/// </summary>
public int Column { get; set; }
/// <summary>
/// Constructor
/// </summary>
/// <param name="message">Message that describes this exception</param>
/// <param name="position">Position within expression where exception occurred</param>
public EvalException(string message, int position)
: base(message)
{
Column = position;
}
/// <summary>
/// Gets the message associated with this exception
/// </summary>
public override string Message
{
get
{
return String.Format("{0} (column {1})", base.Message, Column + 1);
}
}
}
public enum SymbolStatus
{
OK,
UndefinedSymbol,
}
// ProcessSymbol arguments
public class SymbolEventArgs : EventArgs
{
public string Name { get; set; }
public double Result { get; set; }
public SymbolStatus Status { get; set; }
}
public enum FunctionStatus
{
OK,
UndefinedFunction,
WrongParameterCount,
}
// ProcessFunction arguments
public class FunctionEventArgs : EventArgs
{
public string Name { get; set; }
public List<double> Parameters { get; set; }
public double Result { get; set; }
public FunctionStatus Status { get; set; }
}
/// <summary>
/// Expression evaluator class
/// </summary>
public class Eval
{
// Event handers
public delegate void ProcessSymbolHandler(object sender, SymbolEventArgs e);
public delegate void ProcessFunctionHandler(object sender, FunctionEventArgs e);
public event ProcessSymbolHandler ProcessSymbol;
public event ProcessFunctionHandler ProcessFunction;
// Token state enums
protected enum State
{
None = 0,
Operand = 1,
Operator = 2,
UnaryOperator = 3
}
// Error messages
protected string ErrInvalidOperand = "Invalid operand";
protected string ErrOperandExpected = "Operand expected";
protected string ErrOperatorExpected = "Operator expected";
protected string ErrUnmatchedClosingParen = "Closing parenthesis without matching open parenthesis";
protected string ErrMultipleDecimalPoints = "Operand contains multiple decimal points";
protected string ErrUnexpectedCharacter = "Unexpected character encountered \"{0}\"";
protected string ErrUndefinedSymbol = "Undefined symbol \"{0}\"";
protected string ErrUndefinedFunction = "Undefined function \"{0}\"";
protected string ErrClosingParenExpected = "Closing parenthesis expected";
protected string ErrWrongParamCount = "Wrong number of function parameters";
// To distinguish it from a minus operator,
// we'll use a character unlikely to appear
// in expressions to signify a unary negative
protected const string UnaryMinus = "\x80";
//
public Eval()
{
}
/// <summary>
/// Evaluates the given expression and returns the result
/// </summary>
/// <param name="expression">The expression to evaluate</param>
/// <returns></returns>
public double Execute(string expression)
{
return ExecuteTokens(TokenizeExpression(expression));
}
/// <summary>
/// Converts a standard infix expression to list of tokens in
/// postfix order.
/// </summary>
/// <param name="expression">Expression to evaluate</param>
/// <returns></returns>
protected List<string> TokenizeExpression(string expression)
{
List<string> tokens = new List<string>();
Stack<string> stack = new Stack<string>();
State state = State.None;
int parenCount = 0;
string temp;
TextParser parser = new TextParser(expression);
while (!parser.EndOfText)
{
if (Char.IsWhiteSpace(parser.Peek()))
{
// Ignore spaces, tabs, etc.
}
else if (parser.Peek() == '(')
{
// Cannot follow operand
if (state == State.Operand)
throw new EvalException(ErrOperatorExpected, parser.Position);
// Allow additional unary operators after "("
if (state == State.UnaryOperator)
state = State.Operator;
// Push opening parenthesis onto stack
stack.Push(parser.Peek().ToString());
// Track number of parentheses
parenCount++;
}
else if (parser.Peek() == ')')
{
// Must follow operand
if (state != State.Operand)
throw new EvalException(ErrOperandExpected, parser.Position);
// Must have matching open parenthesis
if (parenCount == 0)
throw new EvalException(ErrUnmatchedClosingParen, parser.Position);
// Pop all operators until matching "(" found
temp = stack.Pop();
while (temp != "(")
{
tokens.Add(temp);
temp = stack.Pop();
}
// Track number of parentheses
parenCount--;
}
else if ("+-*/".Contains(parser.Peek()))
{
// Need a bit of extra code to support unary operators
if (state == State.Operand)
{
// Pop operators with precedence >= current operator
int currPrecedence = GetPrecedence(parser.Peek().ToString());
while (stack.Count > 0 && GetPrecedence(stack.Peek()) >= currPrecedence)
tokens.Add(stack.Pop());
stack.Push(parser.Peek().ToString());
state = State.Operator;
}
else if (state == State.UnaryOperator)
{
// Don't allow two unary operators together
throw new EvalException(ErrOperandExpected, parser.Position);
}
else
{
// Test for unary operator
if (parser.Peek() == '-')
{
// Push unary minus
stack.Push(UnaryMinus);
state = State.UnaryOperator;
}
else if (parser.Peek() == '+')
{
// Just ignore unary plus
state = State.UnaryOperator;
}
else
{
throw new EvalException(ErrOperandExpected, parser.Position);
}
}
}
else if (Char.IsDigit(parser.Peek()) || parser.Peek() == '.')
{
if (state == State.Operand)
{
// Cannot follow other operand
throw new EvalException(ErrOperatorExpected, parser.Position);
}
// Parse number
temp = ParseNumberToken(parser);
tokens.Add(temp);
state = State.Operand;
continue;
}
else
{
double result;
// Parse symbols and functions
if (state == State.Operand)
{
// Symbol or function cannot follow other operand
throw new EvalException(ErrOperatorExpected, parser.Position);
}
if (!(Char.IsLetter(parser.Peek()) || parser.Peek() == '_'))
{
// Invalid character
temp = String.Format(ErrUnexpectedCharacter, parser.Peek());
throw new EvalException(temp, parser.Position);
}
// Save start of symbol for error reporting
int symbolPos = parser.Position;
// Parse this symbol
temp = ParseSymbolToken(parser);
// Skip whitespace
parser.MovePastWhitespace();
// Check for parameter list
if (parser.Peek() == '(')
{
// Found parameter list, evaluate function
result = EvaluateFunction(parser, temp, symbolPos);
}
else
{
// No parameter list, evaluate symbol (variable)
result = EvaluateSymbol(temp, symbolPos);
}
// Handle negative result
if (result < 0)
{
stack.Push(UnaryMinus);
result = Math.Abs(result);
}
tokens.Add(result.ToString());
state = State.Operand;
continue;
}
parser.MoveAhead();
}
// Expression cannot end with operator
if (state == State.Operator || state == State.UnaryOperator)
throw new EvalException(ErrOperandExpected, parser.Position);
// Check for balanced parentheses
if (parenCount > 0)
throw new EvalException(ErrClosingParenExpected, parser.Position);
// Retrieve remaining operators from stack
while (stack.Count > 0)
tokens.Add(stack.Pop());
return tokens;
}
/// <summary>
/// Parses and extracts a numeric value at the current position
/// </summary>
/// <param name="parser">TextParser object</param>
/// <returns></returns>
protected string ParseNumberToken(TextParser parser)
{
bool hasDecimal = false;
int start = parser.Position;
while (Char.IsDigit(parser.Peek()) || parser.Peek() == '.')
{
if (parser.Peek() == '.')
{
if (hasDecimal)
throw new EvalException(ErrMultipleDecimalPoints, parser.Position);
hasDecimal = true;
}
parser.MoveAhead();
}
// Extract token
string token = parser.Extract(start, parser.Position);
if (token == ".")
throw new EvalException(ErrInvalidOperand, parser.Position - 1);
return token;
}
/// <summary>
/// Parses and extracts a symbol at the current position
/// </summary>
/// <param name="parser">TextParser object</param>
/// <returns></returns>
protected string ParseSymbolToken(TextParser parser)
{
int start = parser.Position;
while (Char.IsLetterOrDigit(parser.Peek()) || parser.Peek() == '_')
parser.MoveAhead();
return parser.Extract(start, parser.Position);
}
/// <summary>
/// Evaluates a function and returns its value. It is assumed the current
/// position is at the opening parenthesis of the argument list.
/// </summary>
/// <param name="parser">TextParser object</param>
/// <param name="name">Name of function</param>
/// <param name="pos">Position at start of function</param>
/// <returns></returns>
protected double EvaluateFunction(TextParser parser, string name, int pos)
{
double result = default(double);
// Parse function parameters
List<double> parameters = ParseParameters(parser);
// We found a function reference
FunctionStatus status = FunctionStatus.UndefinedFunction;
if (ProcessFunction != null)
{
FunctionEventArgs args = new FunctionEventArgs();
args.Name = name;
args.Parameters = parameters;
args.Result = result;
args.Status = FunctionStatus.OK;
ProcessFunction(this, args);
result = args.Result;
status = args.Status;
}
if (status == FunctionStatus.UndefinedFunction)
throw new EvalException(String.Format(ErrUndefinedFunction, name), pos);
if (status == FunctionStatus.WrongParameterCount)
throw new EvalException(ErrWrongParamCount, pos);
return result;
}
/// <summary>
/// Evaluates each parameter of a function's parameter list and returns
/// a list of those values. An empty list is returned if no parameters
/// were found. It is assumed the current position is at the opening
/// parenthesis of the argument list.
/// </summary>
/// <param name="parser">TextParser object</param>
/// <returns></returns>
protected List<double> ParseParameters(TextParser parser)
{
// Move past open parenthesis
parser.MoveAhead();
// Look for function parameters
List<double> parameters = new List<double>();
parser.MovePastWhitespace();
if (parser.Peek() != ')')
{
// Parse function parameter list
int paramStart = parser.Position;
int parenCount = 1;
while (!parser.EndOfText)
{
if (parser.Peek() == ',')
{
// Note: Ignore commas inside parentheses. They could be
// from a parameter list for a function inside the parameters
if (parenCount == 1)
{
parameters.Add(EvaluateParameter(parser, paramStart));
paramStart = parser.Position + 1;
}
}
if (parser.Peek() == ')')
{
parenCount--;
if (parenCount == 0)
{
parameters.Add(EvaluateParameter(parser, paramStart));
break;
}
}
else if (parser.Peek() == '(')
{
parenCount++;
}
parser.MoveAhead();
}
}
// Make sure we found a closing parenthesis
if (parser.Peek() != ')')
throw new EvalException(ErrClosingParenExpected, parser.Position);
// Move past closing parenthesis
parser.MoveAhead();
// Return parameter list
return parameters;
}
/// <summary>
/// Extracts and evaluates a function parameter and returns its value. If an
/// exception occurs, it is caught and the column is adjusted to reflect the
/// position in original string, and the exception is rethrown.
/// </summary>
/// <param name="parser">TextParser object</param>
/// <param name="paramStart">Column where this parameter started</param>
/// <returns></returns>
protected double EvaluateParameter(TextParser parser, int paramStart)
{
try
{
// Extract expression and evaluate it
string expression = parser.Extract(paramStart, parser.Position);
return Execute(expression);
}
catch (EvalException ex)
{
// Adjust column and rethrow exception
ex.Column += paramStart;
throw ex;
}
}
/// <summary>
/// This method evaluates a symbol name and returns its value.
/// </summary>
/// <param name="name">Name of symbol</param>
/// <param name="pos">Position at start of symbol</param>
/// <returns></returns>
protected double EvaluateSymbol(string name, int pos)
{
double result = default(double);
// We found a symbol reference
SymbolStatus status = SymbolStatus.UndefinedSymbol;
if (ProcessSymbol != null)
{
SymbolEventArgs args = new SymbolEventArgs();
args.Name = name;
args.Result = result;
args.Status = SymbolStatus.OK;
ProcessSymbol(this, args);
result = args.Result;
status = args.Status;
}
if (status == SymbolStatus.UndefinedSymbol)
throw new EvalException(String.Format(ErrUndefinedSymbol, name), pos);
return result;
}
/// <summary>
/// Evaluates the given list of tokens and returns the result.
/// Tokens must appear in postfix order.
/// </summary>
/// <param name="tokens">List of tokens to evaluate.</param>
/// <returns></returns>
protected double ExecuteTokens(List<string> tokens)
{
Stack<double> stack = new Stack<double>();
double tmp, tmp2;
foreach (string token in tokens)
{
// Is this a value token?
int count = token.Count(c => Char.IsDigit(c) || c == '.');
if (count == token.Length)
{
stack.Push(double.Parse(token));
}
else if (token == "+")
{
stack.Push(stack.Pop() + stack.Pop());
}
else if (token == "-")
{
tmp = stack.Pop();
tmp2 = stack.Pop();
stack.Push(tmp2 - tmp);
}
else if (token == "*")
{
stack.Push(stack.Pop() * stack.Pop());
}
else if (token == "/")
{
tmp = stack.Pop();
tmp2 = stack.Pop();
stack.Push(tmp2 / tmp);
}
else if (token == UnaryMinus)
{
stack.Push(-stack.Pop());
}
}
// Remaining item on stack contains result
return (stack.Count > 0) ? stack.Pop() : 0.0;
}
/// <summary>
/// Returns a value that indicates the relative precedence of
/// the specified operator
/// </summary>
/// <param name="s">Operator to be tested</param>
/// <returns></returns>
protected int GetPrecedence(string s)
{
switch (s)
{
case "+":
case "-":
return 1;
case "*":
case "/":
return 2;
case "^":
return 3;
case UnaryMinus:
return 10;
}
return 0;
}
}
}
Using the Class
To evaluate an expression, create an instance of the Eval class and call the Execute() method. This method takes a string expression as an argument and returns the result as a double.
Supporting Symbols in Expressions
If you need to support variables or constants (symbols) within your expression, the Eval class allows that.
By default, any symbols that appear within an expression generate an "Undefined symbol" exception. To add support for symbols, you must attach an event handler to the class's ProcessSymbol event.
This event is called for each symbol encountered in an expression. By default, if you handle this event, all symbols will return a value of zero. In your ProcessSymbol event handler, you can return a different value or signify that the current symbol is undefined.
Listing 2: A ProcessSymbol Event Handler
// Implement expression symbols
protected void ProcessSymbol(object sender, SymbolEventArgs e)
{
if (String.Compare(e.Name, "pi", true) == 0)
{
e.Result = Math.PI;
}
// Unknown symbol name
else e.Status = SymbolStatus.UndefinedSymbol;
}
Supporting Functions in Expressions
In addition to symbols, expressions can also support functions. The code identifies a function when it encounters a symbol followed by opening and closing parentheses. Like C#, the parentheses are used to provide optional function parameters, which can themselves be complex expressions that include symbols or functions.
As with symbols, by default any functions that appears within an expression generate an "Undefined function" exception. To add support for functions, you must attach an event handler to the class's ProcessFunction event.
This event is called for each function encountered in an expression. By default, if you handle this event, all functions will return a value of zero. In your ProcessFunction event handler, you can return a different value, signify that the current function is undefined, or signify that the current function has an invalid number of arguments.
Listing 3: A ProcessFunction Event Handler
// Implement expression functions
protected void ProcessFunction(object sender, FunctionEventArgs e)
{
if (String.Compare(e.Name, "abs", true) == 0)
{
if (e.Parameters.Count == 1)
e.Result = Math.Abs(e.Parameters[0]);
else
e.Status = FunctionStatus.WrongParameterCount;
}
else if (String.Compare(e.Name, "pow", true) == 0)
{
if (e.Parameters.Count == 2)
e.Result = Math.Pow(e.Parameters[0], e.Parameters[1]);
else
e.Status = FunctionStatus.WrongParameterCount;
}
else if (String.Compare(e.Name, "round", true) == 0)
{
if (e.Parameters.Count == 1)
e.Result = Math.Round(e.Parameters[0]);
else
e.Status = FunctionStatus.WrongParameterCount;
}
else if (String.Compare(e.Name, "sqrt", true) == 0)
{
if (e.Parameters.Count == 1)
e.Result = Math.Sqrt(e.Parameters[0]);
else
e.Status = FunctionStatus.WrongParameterCount;
}
// Unknown function name
else e.Status = FunctionStatus.UndefinedFunction;
}
Conclusion
And that wraps up this article. To put this article together, I started by porting some old VB6 code but then had to make a lot of changes to get it working how I wanted. If you find any bugs, please let me know.
End-User License
Use of this article and any related source code or other files is governed
by the terms and conditions of
.
Author Information
Jonathan Wood
I'm a software/website developer working out of the greater Salt Lake City area in Utah. I've developed many websites including Black Belt Coder, Insider Articles, and others.