Yet Another Expression Evaluator

• Download source files - 3.81 Kb

Introduction

It was one of the articles on Expression Evaluator that got me thinking, how easy it was to write an expression evaluator in C# with different types. Well thinking is one thing and doing another. So I set about to write an expression evaluator, which could take in data of types long, double, string and boolean.

I am still at learning C#, so I decided to experiment a bit with all kinds of programming constructs. In places where a foreach could have been very useful, I have used a while. Pardon me for this indulgence.

The classes

public class ExpressionEvaluator

Fields

// the tokens of the converted postfix expression 
protected string[] postfix
// the list of operators         
protected string[] operators
// the list of seprarators       
protected string[] separators 
// operator precedence table     
protected Hashtable precedence
// My own stack only for strings     
protected StringStack stack
// Symbol table for identifiers        
protected Hashtable symbol_table
// infix the tokens of the input infix expression  
protected string[]

Constructors

public ExpressionEvaluator(string exp)
public ExpressionEvaluator(string exp, 
                     ref Hashtable sym) : this(exp)

The first constructor receives a string infix expression. It populates the operator precedence table and converts the infix expression to a postfix expression. The second constructor, receives a reference symbol table from the user of the class. Whenever an identifier is found in the expression, the value is either read or updated in the symbol table.

Public methods

public string Solve()

The user of the class, calls this method to solve the expression. Basically this implements the postfix expression evaluation algorithm.

Protected methods

protected string Evaluate(string opr, 
          string operand1, string operand2)

This method, gets the types operand object from the string, checks if the operation opr is valid for the types of operand1 and operand2. If valid it calls the GetResult() method, else throws an InvalidTypeConversionException exception.

protected void InfixToPostfix()

Converts the infix[] tokens to postfix[] token list.

protected bool IsOperator(string str)

Checks if str is an operator.

protected string GetResult(string opr, 
                   object obj1, object obj2)

This function actually applies opr to the objects obj1 and obj2. It returns the result as string.

protected bool IsValidTypeConversion(TypeCode t1, TypeCode t2)

Checks if the type conversion is a valid one.

protected object GetTypedOperand(string operand)

Given a string operand, it returns a typed object. Here I tried to use some regular expressions to identify the typed object to return. If none of the regular expression patterns match, we assume it is an identifier. Here is the source snippet:

string long_pattern = "([0-9])+";

string double_pattern = "(?:[0-9]*\\.)?[0-9]+";

string string_pattern = 
   "\"[^\"\\\\\\r\\n]*(?:\\\\.[^\"\\\\\\r\\n]*)*\"";

string bool_pattern = "(true|false)+";

if (Regex.IsMatch(operand, long_pattern))

    return Int64.Parse(operand);

if (Regex.IsMatch(operand, double_pattern))

    return Double.Parse(operand);

if (Regex.IsMatch(operand, string_pattern))

    return operand.Substring(1,operand.Length-2);

if (Regex.IsMatch(operand.ToLower(), bool_pattern))

    return Boolean.Parse(operand);

return null;

public class MalformedExpException : Exception

When a postfix expression cannot be parsed on the stack, the exception is thrown.

public class InvalidIdentifierException : Exception

When a token in an expression is an identifier, and cannot be found in the symbol table, the exception is thrown.

public class InvalidTypeConversionException : Exception

When a type conversion is invalid, the exception is thrown

public class InvalidOperationOnType : Exception

When an operation cannot be applied to types of operands, the exception is thrown.

Improvements

1. I would like to implement operations like string + long.