13,000,469 members (60,991 online)
alternative version

#### Stats

41.5K views
20 bookmarked
Posted 23 Aug 2004

# Implementing C# custom expression evaluator through RPN

, 23 Aug 2004
 Rate this:
Implementing C# custom expression evaluator through RPN (Stack)

## Introduction

While studying applied math, I had never thought one day I’ll happen to use RPN in my professional developments. However, by the power of all-existent Murphy’s Law, I’ve got such a chance and here I’d like to share some results of the case.

## Problem definition

To keep it simple, let’s assume we have a string containing arithmetic expression, where each operand is defined as (1), and available set of operations is defined as (2):

1. ^[{](\d+|\d+[\.]\d+){1}[}]\$
2. ^[+|-|*|/]\$

The order of computation can change by putting some braces.

There is a need to evaluate the string and get some numeric result. The original problem (real life) was based upon following suggestions: having template string e.g. {sum1}-({sum2} + {sum3} / {sum4}) and appropriate sumN values, calculate the expression.

## Implementation snippets

The overall idea of implementation is to use Reverse Polish Notation algorithm through stack. So the realization steps can be divided onto:

1. getting RPN representation of the string (it will contain ‘{‘ & ‘}’ as number boundaries delimiters)
2. calculating RPN expression preserving operations precedence

The code attached to article contains algorithm implementation as part of simple console project aimed to test evaluation functionality.

Here I’ll put some focus on selected code blocks (since details are much easily seen within context, IMHO it’s always a better way investigating a complete code):

1. the operations’ precedence is defined in `IsLeftWeaker `and `IsLeftStronger` code blocks as follows:
```private static bool IsLeftWeaker(char lop, char rop) {
return ((lop=='+' || lop=='-') && (rop=='/' || rop=='*'));
}
private static bool IsLeftStronger(char lop, char rop) {
return (((lop=='/' || lop=='*') &&
(rop=='+' || rop=='-')) || rop=='(');
}
```
2. the actual RPN realization:
```private static string GetRPN(string expression) {
Stack stOps = new Stack();
StringBuilder sbRpn = new StringBuilder();
for(int i=0; i<expression.Length; i++) {
if(IsOperand(expression[i])) {
sbRpn.Append(expression[i]);
}else
if(IsOperation(expression[i])) {
if(stOps.Count==0) {
stOps.Push(expression[i]);
}else{
if(CompareOperations(expression[i],
(char)stOps.Peek())) {
sbRpn.Append((char)stOps.Pop());
}
stOps.Push(expression[i]);
}
}else
if(IsBracket(expression[i])) {
if(expression[i]=='(') {
stOps.Push('(');
}else{
while(stOps.Count>0 && (char)stOps.Peek()!='(') {
sbRpn.Append((char)stOps.Pop());
}
stOps.Pop();//just like a trash
}
}else{
throw new ArgumentOutOfRangeException("expression",
"Wrong parameter value!");
}
}
while(stOps.Count>0) {
sbRpn.Append((char)stOps.Pop());
}
return sbRpn.ToString();
}
```
3. and evaluation itself:
```public static double Eval(string expression) {
string rpn = GetRPN(expression);
Console.WriteLine("rpn: " + rpn);
Stack stVals = new Stack();
RPNEnumerator rpnEnum = new RPNEnumerator(rpn);
while(rpnEnum.MoveNext()) {
RPNValue rpnVal = (RPNValue)rpnEnum.Current;
if(rpnVal.type==RPNValueType.OPERAND) {
stVals.Push(Double.Parse(rpnVal.val,
new CultureInfo("en-US")));
}else{
double v2 = (double)stVals.Pop();
double v1 = (double)stVals.Pop();
if(rpnVal.val=="+") {
stVals.Push(v1+v2);
}else
if(rpnVal.val=="-") {
stVals.Push(v1-v2);
}else
if(rpnVal.val=="*") {
stVals.Push(v1*v2);
}else
if(rpnVal.val=="/") {
stVals.Push(v1/v2);
}
}
}
return (double)stVals.Pop();
}
```

Please pay attention to mechanism of navigation through RPN string – I’ve integrated custom iterator for moving through ‘{‘/ ‘}‘-braced data and operations, so the `IEnumerator.MoveNext` looks like this:

```public bool MoveNext() {
bool result = false;
if(_rpn.Length>_index) {
string val = String.Empty;
RPNValue rpnVal = new RPNValue();
if(_rpn[_index]=='{') {
_index++;
while(_rpn[_index]!='}') {
val+=_rpn[_index].ToString();
_index++;
}
rpnVal.val = val;
rpnVal.type = RPNValueType.OPERAND;
}else{
rpnVal.val = _rpn[_index].ToString();
rpnVal.type = RPNValueType.OPERATION;
}
_current = rpnVal;
_index++;
result = true;
}
return result;
}
```

## Some results

To illustrate code "in action", you'll have to get a source here (4.15 Kb zip) or just believe in this shot:

This is evaluation result for test expression "`{1.2}+({2}+{3.24}*{2.3})/{5}`"

A list of licenses authors might use can be found here

## Share

 Web Developer Ukraine
No Biography provided

## You may also be interested in...

 Pro

 First Prev Next
 Re: Formatting issue Sébastien Lorion10-Sep-04 3:10 Sébastien Lorion 10-Sep-04 3:10
 Formatting issue Sébastien Lorion3-Sep-04 5:42 Sébastien Lorion 3-Sep-04 5:42
 Re: Formatting issue nemes9-Sep-04 23:40 nemes 9-Sep-04 23:40
 Last Visit: 31-Dec-99 18:00     Last Update: 25-Jun-17 12:46 Refresh 1