Reverse Polish Expression Parser in C#

Posted on Updated on

There comes a time in every programmers life when she needs a parser. More so if that programmer works for an accounting company. Its not enough to just do the obvious and use the Java Script expression evaluator, or some other third party library for that matter. After all you can do it yourself, with all the custom trimmings that you require for your current project. The key concept in any mathematical parser is the way it interprets the tokens given to it. In this post I will be using reverse polish notation to represent the expression; which will be evaluated and the answer returned. The code is pretty self explanatory so I will not go into details about how it works, remember this is just my first attempt at this so any recommendations or suggestions will be welcomed. I have also intentionally left out some features in the hopes that this will spur suggestions and recommendations.

Snippets

public struct Token{
        public int _class;
        public string repr;
    }

 

private bool RPN(string expression){
            Regex reg = new Regex(@"\[\b[A-Za-z]+\b(?![\d])\]|[\+\-/\*]|[\d]+(\.[\d]+)?|[()]");
            Stack op_stack = new Stack();

            foreach(Match token in reg.Matches(expression)){
                Token tok = new Token();
                string value = token.Captures[0].Value;

                if(IsNumeric(value)){
                    tok._class = (int)type.num;
                    tok.repr = value;
                    calc_list.Add(tok);

                }else if(IsOperator(value)){
                    while(op_stack.Count != 0 && op_stack.Peek().repr != "("){
                        if (HasPrecidenceOrEqual(op_stack.Peek().repr, value)){
                            calc_list.Add(op_stack.Pop());
                        }
                        else break;
                    }
                    tok._class = (int)type.op;
                    tok.repr = value;

                    op_stack.Push(tok);
                }else if (IsVariable(value)){
                    tok._class = (int)type.var;
                    tok.repr = value;
                    calc_list.Add(tok);

                }else if(value == "("){
                    tok._class = (int)type.var;
                    tok.repr = value;

                    op_stack.Push(tok);
                }else if(value == ")"){
                   while(op_stack.Count != 0 && op_stack.Peek().repr != "("){
                       calc_list.Add(op_stack.Pop());
                    }
                   if (op_stack.Count != 0) op_stack.Pop();
                }
            }
            while(op_stack.Count != 0){
                calc_list.Add(op_stack.Pop());
            }

            return true;
        }

Full source code listing at github

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s