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

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

, 10 Mar 2009
Rate this:
Please Sign up or sign in to vote.
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.

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):

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:

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:

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:

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:

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.)

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)

Share

About the Author

PIEBALDconsult
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
 
---------------
 
"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

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

 
"We learn more from our mistakes than we do from getting it right the first time."
 
My first rule of debugging: "If you get a different error message, you're making progress."
 
My golden rule of database management: "Do not unto others' databases as you would not have done unto yours."
 
My general rule of software development: "Design should be top-down, but implementation should be bottom-up."

Comments and Discussions

 
GeneralGreat except some [modified] PinmvpLuc Pattyn10-Mar-09 18:24 
GeneralRe: Great except some PinmemberPIEBALDconsult11-Mar-09 4:51 
GeneralRe: Great except some PinmvpLuc Pattyn11-Mar-09 5:07 
GeneralRe: Great except some PinmemberPIEBALDconsult11-Mar-09 5:24 
GeneralRe: Great except some PinmemberPIEBALDconsult11-Mar-09 7:21 
GeneralRe: Great except some PinmvpLuc Pattyn11-Mar-09 7:44 
GeneralRe: Great except some PinmemberPIEBALDconsult11-Mar-09 8:00 
GeneralRe: Great except some PinmvpLuc Pattyn11-Mar-09 8:06 
GeneralRe: Great except some PinmemberPIEBALDconsult11-Mar-09 8:31 
Luc Pattyn wrote:
holding some five characters?

 
No, only one so far Big Grin | :-D . "But it's faaassst!" (to quote a developer defending the Caché database)
 
Of course my first thought was to use ( "^".IndexOf ( Op.Character ) != -1 ), but that will slow down as I add operators and it won't work if I support multiple-character operators.
 
I could use a Dictionary<char,delegate> and populate it with all the operators and their equality methods, that would offer the most flexibility. Unsure | :~
 
if ( dic [ Op.Character ] ( Op , this.Peek() ) ...
GeneralRe: Great except some PinmvpLuc Pattyn11-Mar-09 8:46 
GeneralRe: Great except some PinmemberPIEBALDconsult12-Dec-11 4:00 
AnswerRe: Great except some PinmvpLuc Pattyn12-Dec-11 4:27 
GeneralDemo PinmemberPaulC197214-Nov-06 5:42 
GeneralRe: Demo PinmemberPIEBALDconsult14-Nov-06 14:54 

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 | Mobile
Web03 | 2.8.140814.1 | Last Updated 10 Mar 2009
Article Copyright 2006 by PIEBALDconsult
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid