12,632,198 members (25,797 online)
Add your own
alternative version

40.8K views
197 downloads
20 bookmarked
Posted

# Implementing C# custom expression evaluator through RPN

, 23 Aug 2004
 Rate this:
Please Sign up or sign in to vote.
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}`"

## 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

## About the Author

 Web Developer Ukraine
No Biography provided

## You may also be interested in...

 Pro Pro

## Comments and Discussions

 First Prev Next
 Re: Formatting issue Sébastien Lorion10-Sep-04 4:10 Sébastien Lorion 10-Sep-04 4:10
 Formatting issue Sébastien Lorion3-Sep-04 6:42 Sébastien Lorion 3-Sep-04 6:42
 Re: Formatting issue nemes10-Sep-04 0:40 nemes 10-Sep-04 0:40
 Last Visit: 31-Dec-99 19:00     Last Update: 8-Dec-16 10:40 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.161208.2 | Last Updated 24 Aug 2004
Article Copyright 2004 by nemes
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid