Click here to Skip to main content
15,867,308 members
Articles / Programming Languages / C#
Article

C# Expression Parser using RPN

Rate me:
Please Sign up or sign in to vote.
4.57/5 (26 votes)
17 Jan 20045 min read 210.2K   7.4K   85   32
Design & implementation of an Expression Parser using RPN in C#.

Introduction

The aim of this article is to demonstrate an interface-based programming paradigm in the design and implementation of a simple Expression Parser & Evaluator using RPN in C#. The intended audience skill set would be Beginner to Intermediate.

Background

For introduction about Expressions & Reverse Polish Notation, refer to this article - Expression Evaluator: using RPN by lallous, in the C++/MFC section.

Design Description

(All code referred here is inside RPNParser.cs file.)

Interfaces

Every expression is made of operands and operators. These are reflected in the interfaces - IOperand and IOperator.

  • IArithmeticOperations defines methods for binary arithmetic operators (+, -, *, \, %).
  • IComparisonOperations defines methods for all comparison operators (>, >=, <, <=, ==, !=).
  • ILogicalOperations defines methods for logical operators (&& , ||).

The idea behind these interfaces is as follows -

Each Operand supports a set of Operations and the Operators evaluate a pair of Operands using the Operations supported by the two Operands.

E.g. A Long Operand supports Arithmetic and Comparison Operations, whereas a String might support only Comparison Operations. Boolean Operands support only the Logical Operations.

An Operator like + needs only to know that it has to call the Plus method on an IOperand implementing the IArithmeticOperations interface. This keeps the algorithm of expression parsing & evaluation (in this case the RPN sequencing) separated from the data type that does the actual evaluations and hence makes it very extensible to newer data types.

Operands

Operand class is an abstract base class implementing the IOperand interface and additionally providing data storage.

LongOperand is an Operand class specific to Long & Int (Int64 and Int32) types of operands and implements the IArithmeticOperations, IComparisonOperations interfaces.

BoolOperand is an Operand class specific to bool type of operands and implements only the ILogicalOperations interface.

OperandHelper is a static class providing object factory functionality to create appropriate Operand objects based on the Type passed to it (OperandHelper.CreateOperand).

For new types of Operands like Decimal/String or user-defined types, e.g. a Matrix, this factory method would have to be extended.

Operators

IOperator defines one method called Eval and is used to evaluate the LHS and RHS of the expression.

Operator is an abstract base class implementing this interface and provides data storage for the operator.

ArithmeticOperator, ComparisonOperator, LogicalOperator are operator classes to support IArithmeticOperations, IComparisonOperations, ILogicalOperations respectively.

OperatorHelper is a helper class providing object factory functionality for creation of appropriate Operator objects (OperatorHelper.CreateOperator). This class provides services to determine operator-precedence. This is based on the relative indexes of the operators defined in the m_AllOps variable. It also provides Regular Expressions used during parsing of the input expression string. E.g. The regex [=<>!]{1,2} is used to parse for Comparison operators.

Expression Parsing

The Tokenizer class provides functionality of parsing the input expression string using regular expressions.

The TokenEnumerator class supports the IEnumerator interface and is used to loop through the various tokens in the input expression string. The tokens in the expression are returned to the caller as Token objects.

The given expression can be parsed as either Arithmetic or Logical or Comparison Expression Types. This is controlled by the enums ExpressionType::ET_ARITHMETIC, ExpressionType::ET_COMPARISON and ExpressionType::ET_LOGICAL. A combination of these enum types can also be given.

E.g. To parse the expression as all of these, pass ExpressionType.ET_ARITHMETIC| ExpressionType.ET_COMPARISON|ExpressionType.ET_LOGICAL to the Tokenizer c'tor.

The generation of the RPN sequence is in the RPNParser::GetPostFixNotation method and it uses the algorithm as described in the above mentioned C++ article. The return value is an ArrayList consisting of Operands and Operators in the RPN sequence.

This method takes an argument bFormula that determines if the expression being parsed is a formula (in the form of x+y*z/t) or has direct values (3+6*7/2). If the expression is not a formula, then the values are extracted by this method and stored in the Token object for later evaluation. If the expression is a formula, then the values for the corresponding variables need to be passed separately as a hashtable for evaluation.

Expression Evaluation

RPNParser::EvaluateRPN is the method performing actual evaluation of the RPN generated by the RPNParser::GetPostFixNotation method and is again based on the algorithm described in the above mentioned C++ article. This method takes as input the ArrayList with the RPN sequence and if the expression is a formula, a hashtable with values for the variables in the expression.

Usage

A typical usage of the parser would be as follows -

C#
RPNParser parser = new RPNParser();

string szExpression = @"((2+3)*2<10 || 1!=1) && 2*2==4";

parser.EvaluateExpression( szExpression, 
    Type.GetType("System.Int64" ), false, null );

The attached code contains a small form-based application to test the logic.

It uses the RPN_Parser::Convert2String() method to get a string representation of the RPN sequence.

Extensibility

The Parser can be easily extended to support new Operand types and Operators by subclassing the Operand and Operator classes. Since the Parsing and Evaluation logic works totally on interfaces, typically nothing would have to be changed there. Of course, the factory classes need to be extended to support the new types and if adding new operators, the regular expressions used & their precedence information present inside the Operatorhelper class would have to be modified accordingly.

Hope someone out there finds this useful.

Current Shortcomings

  1. Unary operators (+,-,!) not handled.
  2. Does not yet support expressions having mixture of variables and values (e.g. x+y/3*z%2 ).
  3. Bitwise & and | not handled.
  4. Does not handle a combo expression with multiple braces as just one of the ExpressionTypes?

    // E.g. ((2+3)*2<10 || 1!=1) && 2*2==4 as just a logical expression cannot be done.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Web Developer
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionGiving some examples Pin
Member 139396026-Aug-18 12:47
Member 139396026-Aug-18 12:47 
Questionpossibility to reuse the source code? Pin
Member 1228813111-Apr-16 5:48
Member 1228813111-Apr-16 5:48 
QuestionDivide error Pin
Imanloo27-May-14 22:00
Imanloo27-May-14 22:00 
GeneralMy vote of 5 Pin
stofel9-Sep-13 1:51
stofel9-Sep-13 1:51 
GeneralVB eqivalent Pin
coarist20-Jun-13 2:48
coarist20-Jun-13 2:48 
QuestionConditional operator Pin
Member 89200266-Aug-12 21:17
Member 89200266-Aug-12 21:17 
Hello

I am not able to parse string with condtional operator.



ex - ((3+4>5)? 5 : 8

Please guide we can implement this .

Thanks
GeneralMy vote of 4 Pin
staarkannan20-Dec-10 23:05
staarkannan20-Dec-10 23:05 
GeneralHere is the updated code for unary operator Not(!). [modified] Pin
staarkannan20-Dec-10 23:02
staarkannan20-Dec-10 23:02 
GeneralYou did great job !!! Pin
actyrol24-Aug-10 5:32
actyrol24-Aug-10 5:32 
QuestionAny restriction to use this code? Pin
sree1234518-Mar-10 10:44
sree1234518-Mar-10 10:44 
AnswerRe: Any restriction to use this code? Pin
Member 122881318-Apr-16 0:15
Member 122881318-Apr-16 0:15 
QuestionAdding Exponent Operator Pin
Azra sultana7-Jun-09 4:12
Azra sultana7-Jun-09 4:12 
GeneralDecimal Value Cannot Evaluate Pin
RobertChan20003-May-09 12:51
RobertChan20003-May-09 12:51 
Questionsome bugs? Pin
Canic23-Apr-09 16:31
Canic23-Apr-09 16:31 
GeneralOperator Precedence Pin
cmptrkemist13-Dec-07 19:48
cmptrkemist13-Dec-07 19:48 
GeneralMinus unary operator support + string comparison [modified] Pin
zitun21-Jun-06 22:08
zitun21-Jun-06 22:08 
GeneralUnary operator support Pin
stuallenii5-May-06 5:59
stuallenii5-May-06 5:59 
GeneralBug Pin
Ihor Bobak12-Feb-06 9:44
Ihor Bobak12-Feb-06 9:44 
GeneralRe: Bug Pin
stuallenii5-May-06 5:53
stuallenii5-May-06 5:53 
GeneralSome changes for String comparing.... Pin
neuralc10-Nov-04 5:31
neuralc10-Nov-04 5:31 
GeneralRe: Some changes for String comparing.... Pin
zitun15-May-06 1:51
zitun15-May-06 1:51 
GeneralUPDATE : Some changes for String comparing.... Pin
zitun30-May-06 0:08
zitun30-May-06 0:08 
GeneralDecimal numbers Pin
Gian7-May-04 1:30
Gian7-May-04 1:30 
GeneralRe: Decimal numbers Pin
Ciprian Talaba22-Aug-06 23:43
Ciprian Talaba22-Aug-06 23:43 
GeneralRe: Decimal numbers Pin
asmgx16-May-07 16:22
asmgx16-May-07 16:22 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.