Click here to Skip to main content
Click here to Skip to main content

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

Share

About the Author

nemes
Web Developer
Ukraine Ukraine
No Biography provided

Comments and Discussions

 
GeneralRe: Formatting issue PinmemberSébastien Lorion10-Sep-04 4:10 
GeneralFormatting issue PinmemberSébastien Lorion3-Sep-04 6:42 
GeneralRe: Formatting issue Pinmembernemes10-Sep-04 0:40 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin 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.150327.1 | Last Updated 24 Aug 2004
Article Copyright 2004 by nemes
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid