If you’ve tried to write your own calculator (something in the style of gcalctool) you’ve probably had to build a simple converter for your mathematical expressions from infix notation to  RPN (Reverse Polish Notation).

Inspired by this classical SPOJ challenge I wanted to write my own simplified version of an expression converter. If this topic is new for you, or you need to refresh your memory please don’t skip the following paragraph.

Infix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on (e.g. 2 + 5). Unfortunately what seems natural for us, is not as simple to parse by computers as prefix or RPN notations.

RPN also known as the Reverse Polish Notation is mathematical notation wherein every operator (eg. + – * %) follows all of its operands. Examples:

Infix notation Reverse Polish Notation
A + B A B +
A ^ 2 + 2 * A * B + B ^ 2 A 2 ^ 2 A * B * + B 2 ^ +
( ( 1  + 2 ) / 3 ) ^ 4 1  2 + 3 / 4 ^
( 1 + 2 ) * ( 3 / 4 ) ^ ( 5 + 6 ) 1 2 + 3 4 / 5 6 + ^ *

In order to parse and convert a given infix mathematical expression to RPN we will use the shunting-yard algorithm . Just like the evaluation of RPN, the algorithm is stack-based . For the conversion we will use two buffers (one for input, and one for output). Additionally we will use a stack for operators that haven’t been yet added to the output.

A simplified version of the Shunting-yard algorithm (complete version)
  • For all the input tokens [S1]:
    • Read the next token [S2];
    • If token is an operator (x) [S3]:
      • While there is an operator (y) at the top of the operators stack and either (x) is
        left-associative and its precedence is less or equal to that of (y), or (x) is right-associative
        and its precedence is less than (y) [S4]:

        • Pop (y) from the stack [S5];
        • Add (y) output buffer [S6];
      • Push (x) on the stack [S7];
    • Else If token is left parenthesis, then push it on the stack [S8];
    • Else If token is a right parenthesis [S9]:
      • Until the top token (from the stack) is left parenthesis, pop from the stack to the output buffer [S10];
      • Also pop the left parenthesis but don’t include it in the output buffer [S11];
    • Else add token to output buffer [S12].
  • While there are still operator tokens in the stack, pop them to output [S13]

Note: [SN] Relate with code.

I) Java Implementation

The following implementation of the shunting-yard algorithm does not impose any validations. The input should be a valid mathematical expression or else the program may end abruptly or perform incorrectly.

Step 1 : Declaring and defining operators

Step 2 : Parsing expression

The input in this case should an array of strings, where every little string is a token. The output will also be an array of strings but in RPN order. (Take a look at the code comments, and the algorithm references [Sn]).

Step 3 : Testing the working converter

And the output:

Step 4 : Putting all togheter

II) Python Implementation

The python implementation is a complete “translation” of the previous Java implementation (only the syntax was changed … in better).

Step 1 : Declaring and defining operators

Step 2 : Parsing expression

Just like in the previous example, the algorithm does not impose any validation. The input expression should be composed of valid tokens, or else the program may malfunction or end abruptly.

Step 3 : Testing the converter

And the output:

Putting all togheter:

17 thoughts on “Converting infix to RPN (shunting-yard algorithm)

  1. Pingback: RPN Calculator (using Scala, python and Java) « andreINC.net

  2. HI,
    I have a C# implementation of this algorithm. If you are interested and want to publish, let me know and I will email you the code.

    Reply
  3. @Tom

    Of course you can email me the code if you want, and I’ll publish the code (ofcourse giving you the credits).

    Reply
  4. Here’s a Javascript implementation ripped straight from your Java one. Scouring through t’interwebs there are previous little Javascript implementations that are any good out there, so hopefully this will be useful to others and save them the couple of hours I spent first looking for an existing one then hacking this one together.

    Reply
    • Thanks for your comment and implementation. I’ve almost deserted this site. Recently I’ve decided to “revive” it, so that’s the reason for this very late reply.

      Reply
  5. Pingback: » AdvancedFilter: Parsing the Search String Spreadsheet Budget and Consulting

  6. Pingback: Memorized my reading ;) « Parnurzeal’s Weblog

  7. Pingback: Interesting sites | Latoto

    • The if-then-else, can be implemented as a 3-ary usual (function) operator, i.e “inline if”, provided the RPN implementation can parse (custom) functions

      There was a similar project implementation as a sub-project for another project i was working on, some time ago, but decided to build a generic xpresion tool (in various platforms, currently js,python,php,actionscript) with variables and custom functions/operators support

      here:

      https://github.com/foo123/Xpresion

      Although it can be already covered by existing implementation, thought if adding, custom infix operators as well (additonaly to custom prefix/postfix operators, aka functions)

      Reply
  8. Hey, just wanted to say thanks for the implementation you’ve posted, it has been of tremendous help (specifically the Python version).

    Reply

Leave a reply

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url=""> 

required

Are we human, or are we dancer *