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

A Simple, Infix to Reverse Polish Notation Transformer, Written in C#

Rate me:
Please Sign up or sign in to vote.
3.03/5 (10 votes)
10 Mar 2009CPOL3 min read 58.1K   451   12   14
Transforms a mathematical expression from Infix notation to Reverse Polish notation

Introduction

The class presented in this article can be used to transform a mathematical expression from infix notation to Reverse Polish notation. By default, there is no validation of the expression, but some simple validation may be turned on through an Options parameter.

See Shunting yard algorithm for more information.

Background

I needed this for the ParseInfix method for my Rational type.

The class exposes only one public method: the InfixToRpn method.

C#
string result = PIEBALD.Lib.InfixToRpn
(
    source
, 
    PIEBALD.Lib.InfixToRpn.RpnOptions.None
) ;

string result = PIEBALD.Lib.InfixToRpn
(
    source
, 
    PIEBALD.Lib.InfixToRpn.RpnOptions.FailOnMalformedExpression
) ;

The mathematical operators (+, -, *, /, %, ^ (exponentiation)) and parentheses are supported.

Verbatim text (which can be used for terms in Scientific notation) can be specified between the ' (ASCII 96) and ' delimiters.

Supporting Characters

The following items are also in the file:

RpnOptions

This enumeration is used to provide the user the ability to control some optional features of the InfixToRpn method.

RetainWhiteSpace

Retain the whitespace, control characters, and null characters from the source string.

FailOnMismatchedParenthesis

Throw an InfixToRpnFormatException if a mismatched parenthesis is detected.

FailOnMalformedExpression

Throw an InfixToRpnFormatException when various other situations occur.

All

All of the options.

None

None of the options.

InfixToRpnFormatException

If FailOnMismatchedParenthesis and/or FailOnMalformedExpression is specified and such a condition is detected, then an instance of this exception will be thrown. The class has a public readonly field named Position that will contain the (one-based) position of the character that appears to be errant.

OperatorPrecedence

This enumeration is used to associate a precedence with an operator in the following class.

Operator

An instance of the Operator class contains only the operator character and its precedence value.

OperatorStack

An OperatorStack is a Stack<Operator>. It has its own versions of Push and Clear which will append removed Operators directly to the output.

OperatorStackStack

An OperatorStackStack is a Stack<OperatorStack>. The InfixToRpn method uses one of these, which is initialized with one OperatorStack. Each OperatorStack represents one pair of parentheses. Each time a left parenthesis is encountered, a new OperatorStack is instantiated and pushed onto the OperatorStackStack. Each time a right parenthesis is encountered, the top OperatorStack is popped off and cleared (the bottom-most OperatorStack does not get popped off).

ValidatorState

This enumeration defines states for the validator.

NoMoreOpsAllowed

We had a second operator.

OnlyOneOpAllowed

We had a left-parenthesis.

UnaryOpAllowed

We had a first operator.

BinaryOpAllowed

We had a right-parenthesis.

TermBegun

We had a term character.

TermEnded

We had a term-ending whitespace operator.

VerbatimTextBegun

In verbatim text mode.

InfixToRpn

The method is rather lengthy so I won't present the whole thing. It consists primarily of a foreach loop across the characters of the Subject string and a switch. Here are the major pieces (result is a StringBuilder member field):

C#
OperatorStackStack ops = new OperatorStackStack ( new OperatorStack ( 0 ) ) ;

int index = 0 ;

ValidatorState validatorstate = ValidatorState.OnlyOneOpAllowed ;

result.Length = 0 ;

result.EnsureCapacity ( Subject.Length * 2 ) ;

foreach ( char thischar in Subject )
{
    index++ ;

    switch ( thischar )
    {
        // See below
    }

    while ( ops.Count > 0 )
    {
        ops.Pop().Clear() ;
    }

    return ( result.ToString() ) ;
}

Inside the switch are (of course) case statements for the various characters that need to be interpreted. Here is the case for multiplication, division, and modulo:

C#
case '*' :
case '/' :
case '%' :
{

    if ( failonmalformedexpression )
    {
        if
        (
            ( validatorstate == ValidatorState.UnaryOpAllowed )
        ||
            ( validatorstate == ValidatorState.NoMoreOpsAllowed )
        )
        {
            throw ( new InfixToRpnFormatException
            (
                "Too many operators in a row"
            ,
                index
            ) ) ;
        }
    }

    ops.Peek().Push
    (
        new Operator ( thischar , OperatorPrecedence.Medium )
    ) ;

    validatorstate = ValidatorState.UnaryOpAllowed ;

    break ;
}

Here is the case for addition, subtraction, unary positive, and unary negative. Notice that unary operators receive Highest precedence while their binary counterparts receive Low precedence:

C#
case '-' :
case '+' :
{
    if ( failonmalformedexpression )
    {
        if ( validatorstate == ValidatorState.NoMoreOpsAllowed )
        {
            throw ( new InfixToRpnFormatException
            (
                "Too many operators in a row"
            ,
                index
            ) ) ;
        }
    }

    if
    (
        ( validatorstate == ValidatorState.UnaryOpAllowed )
    ||
        ( validatorstate == ValidatorState.OnlyOneOpAllowed )
    )
    {
        /* Unary */
        ops.Peek().Push
        (
            new Operator ( thischar , OperatorPrecedence.Highest )
        ) ;

        validatorstate = ValidatorState.NoMoreOpsAllowed ;
    }
    else
    {
        /* Binary */
        ops.Peek().Push
        (
            new Operator ( thischar , OperatorPrecedence.Low )
        ) ;

        validatorstate = ValidatorState.UnaryOpAllowed ;
    }

    break ;
}

A left-parenthesis causes a new OperatorStack to be pushed onto the OperatorStackStack. Here is the case for left-parenthesis:

C#
case '(' :
{
    if ( failonmalformedexpression )
    {
        if
        (
            ( validatorstate == ValidatorState.TermBegun )
        ||
            ( validatorstate == ValidatorState.TermEnded )
        ||
            ( validatorstate == ValidatorState.BinaryOpAllowed )
        )
        {
            throw ( new InfixToRpnFormatException
            (
                "No operator preceding left-parenthesis"
            ,
                index
            ) ) ;
        }
    }

    ops.Push ( new OperatorStack ( index ) ) ;

    validatorstate = ValidatorState.OnlyOneOpAllowed ;

    break ;
}

A right-parenthesis causes the top OperatorStack to be popped from the OperatorStackStack (unless it's the only OperatorStack) and Cleared. Here is the case for right-parenthesis:

C#
case ')' :
{
    if ( failonmalformedexpression )
    {
        if
        (
            ( validatorstate == ValidatorState.UnaryOpAllowed )
        ||
            ( validatorstate == ValidatorState.NoMoreOpsAllowed )
        )
        {
            throw ( new InfixToRpnFormatException
            (
                "Operator followed by right-parenthesis"
            ,
                index
            ) ) ;
        }

        if ( validatorstate == ValidatorState.OnlyOneOpAllowed )
        {
            throw ( new InfixToRpnFormatException
            (
                "Empty parentheses"
            ,
                index
            ) ) ;
        }
    }

    if ( ops.Count == 1 )
    {
        if ( failonmismatchedparenthesis )
        {
            throw ( new InfixToRpnFormatException
            (
                "Mismatched right-parenthesis"
            ,
                index
            ) ) ;
        }

        ops.Peek().Clear() ;
    }
    else
    {
        ops.Pop().Clear() ;
    }

    validatorstate = ValidatorState.BinaryOpAllowed ;

    break ;
}

The last case I'll show is for the terms of the expression, the operands. A term is basically any consecutive characters that are neither operators nor whitespace. (Verbatim text forms a term, and may contain operator characters and whitespace; but verbatim text has its own special processing and I won't cover it here.)

C#
default :
{
    if ( failonmalformedexpression )
    {
        if ( validatorstate == ValidatorState.BinaryOpAllowed )
        {
            throw ( new InfixToRpnFormatException
            (
                "No operator preceding term"
            ,
                index
            ) ) ;
        }

        if ( validatorstate == ValidatorState.TermEnded )
        {
            throw ( new InfixToRpnFormatException
            (
                "Second consecutive term detected"
            ,
                index
            ) ) ;
        }
    }

    result.Append ( thischar ) ;

    validatorstate = ValidatorState.TermBegun ;

    break ;
}

Using the Code

The zip also contains Rpn.cs, a very simple console program. Compile it and LibRpn.cs with your choice of C# compiler.

Sample output:

C:\>rpn 2+3*4
2 3 4 * +
C:\>rpn a/b-c
a b / c -
C:\>rpn x * -4
x
C:\>rpn "x * -4"
x 0 4 - *
C:\>rpn "x - -4"
x 0 4 - -
C:\>rpn "x - 1/4"
x 1 4 / -
C:\>rpn "x - /4"
Too many operators in a row at position 5
C:\>rpn "x ---4"
Too many operators in a row at position 5

History

  • First posted - 2006-01-16
  • Updated - 2006-11-27
  • Updated - 2009-03-10 - Reworked the article. There are only minor changes to the code, mostly to the comments.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
United States United States
BSCS 1992 Wentworth Institute of Technology

Originally from the Boston (MA) area. Lived in SoCal for a while. Now in the Phoenix (AZ) area.

OpenVMS enthusiast, ISO 8601 evangelist, photographer, opinionated SOB, acknowledged pedant and contrarian

---------------

"I would be looking for better tekkies, too. Yours are broken." -- Paul Pedant

"Using fewer technologies is better than using more." -- Rico Mariani

"Good code is its own best documentation. As you’re about to add a comment, ask yourself, ‘How can I improve the code so that this comment isn’t needed?’" -- Steve McConnell

"Every time you write a comment, you should grimace and feel the failure of your ability of expression." -- Unknown

"If you need help knowing what to think, let me know and I'll tell you." -- Jeffrey Snover [MSFT]

"Typing is no substitute for thinking." -- R.W. Hamming

"I find it appalling that you can become a programmer with less training than it takes to become a plumber." -- Bjarne Stroustrup

ZagNut’s Law: Arrogance is inversely proportional to ability.

"Well blow me sideways with a plastic marionette. I've just learned something new - and if I could award you a 100 for that post I would. Way to go you keyboard lovegod you." -- Pete O'Hanlon

"linq'ish" sounds like "inept" in German -- Andreas Gieriet

"Things would be different if I ran the zoo." -- Dr. Seuss

"Wrong is evil, and it must be defeated." –- Jeff Ello

"A good designer must rely on experience, on precise, logical thinking, and on pedantic exactness." -- Nigel Shaw

“It’s always easier to do it the hard way.” -- Blackhart

“If Unix wasn’t so bad that you can’t give it away, Bill Gates would never have succeeded in selling Windows.” -- Blackhart

"Use vertical and horizontal whitespace generously. Generally, all binary operators except '.' and '->' should be separated from their operands by blanks."

"Omit needless local variables." -- Strunk... had he taught programming

Comments and Discussions

 
GeneralGreat except some [modified] Pin
Luc Pattyn10-Mar-09 18:24
sitebuilderLuc Pattyn10-Mar-09 18:24 
GeneralRe: Great except some Pin
PIEBALDconsult11-Mar-09 4:51
mvePIEBALDconsult11-Mar-09 4:51 
GeneralRe: Great except some Pin
Luc Pattyn11-Mar-09 5:07
sitebuilderLuc Pattyn11-Mar-09 5:07 
GeneralRe: Great except some Pin
PIEBALDconsult11-Mar-09 5:24
mvePIEBALDconsult11-Mar-09 5:24 
GeneralRe: Great except some Pin
PIEBALDconsult11-Mar-09 7:21
mvePIEBALDconsult11-Mar-09 7:21 
GeneralRe: Great except some Pin
Luc Pattyn11-Mar-09 7:44
sitebuilderLuc Pattyn11-Mar-09 7:44 
GeneralRe: Great except some Pin
PIEBALDconsult11-Mar-09 8:00
mvePIEBALDconsult11-Mar-09 8:00 
GeneralRe: Great except some Pin
Luc Pattyn11-Mar-09 8:06
sitebuilderLuc Pattyn11-Mar-09 8:06 
GeneralRe: Great except some Pin
PIEBALDconsult11-Mar-09 8:31
mvePIEBALDconsult11-Mar-09 8:31 
GeneralRe: Great except some Pin
Luc Pattyn11-Mar-09 8:46
sitebuilderLuc Pattyn11-Mar-09 8:46 
GeneralRe: Great except some Pin
PIEBALDconsult12-Dec-11 4:00
mvePIEBALDconsult12-Dec-11 4:00 
Luc Pattyn wrote:
Of course, Contains() will be a slow O(n) operation then.


Not if I sort it and use a binary search.


Ah, re-reading old articles and posts can be fun. Big Grin | :-D
AnswerRe: Great except some Pin
Luc Pattyn12-Dec-11 4:27
sitebuilderLuc Pattyn12-Dec-11 4:27 
GeneralDemo Pin
Paul Conrad14-Nov-06 5:42
professionalPaul Conrad14-Nov-06 5:42 
GeneralRe: Demo Pin
PIEBALDconsult14-Nov-06 14:54
mvePIEBALDconsult14-Nov-06 14:54 

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.