Convert infix expressions to postfix notation

Question

When I saw the title of this closed question, I thought it looked like an interesting code golf challenge. So let me present it as such:

Challenge:

Write a program, expression or subroutine which, given an arithmetical expression in infix notation, like 1 + 2, outputs the same expression in postfix notation, i.e. 1 2 +.

(Note: A similar challenge was posted earlier in January. However, I do feel the two tasks are sufficiently different in detail to justify this separate challenge. Also, I only noticed the other thread after typing up everything below, and I'd rather not just throw it all away.)

Input:

The input consists of a valid infix arithmetical expression consisting of numbers (non-negative integers represented as sequences of one or more decimal digits), balanced parentheses to indicate a grouped subexpression, and the four infix binary operators +, -, * and /. Any of these may be separated (and the entire expression surrounded) by an arbitrary number of space characters, which should be ignored.¹

For those who like formal grammars, here's a simple BNF-like grammar that defines valid inputs. For brevity and clarity, the grammar does not include the optional spaces, which may occur between any two tokens (other than digits within a number):

expression     := number | subexpression | expression operator expression
subexpression  := "(" expression ")"
operator       := "+" | "-" | "*" | "/"
number         := digit | digit number
digit          := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

_{¹ The only case where the presence of spaces may affect the parsing is when they separate two consecutive numbers; however, since two numbers not separated by an operator cannot occur in a valid infix expression, this case can never happen in valid input.}

Output:

The output should be a postfix expression equivalent to the input. The output expression should consist only of numbers and operators, with a single space character between each pair of adjacent tokens, as in the following grammar (which does include the spaces)²:

expression  := number | expression sp expression sp operator
operator    := "+" | "-" | "*" | "/"
number      := digit | digit number
digit       := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
sp          := " "

_{² Again for simplicity, the number production in this grammar admits numbers with leading zeros, even though they're forbidden in the output by the rules below.}

Operator precedence:

In the absence of parentheses, the following precedence rules apply:

• The operators * and / have higher precedence than + and -.
• The operators * and / have equal precedence to each other.
• The operators + and - have equal precedence to each other.
• All operators are left-associative.

For example, the following two expressions are equivalent:

1 + 2 / 3 * 4 - 5 + 6 * 7
((1 + ((2 / 3) * 4)) - 5) + (6 * 7)

and they should both yield the following output:

1 2 3 / 4 * + 5 - 6 7 * +

(These are the same precedence rules as in the C language and in most languages derived from it. They probably resemble the rules you were taught in elementary school, except possibly for the relative precedence of * and /.)

Miscellaneous rules:

• If the solution given is an expression or a subroutine, the input should be supplied and the output returned as a single string. If the solution is a complete program, it should read a line containing the infix expression from standard input and print a line containing the postfix version to standard output.

• Numbers in the input may include leading zeros. Numbers in the output must not have leading zeros (except for the number 0, which shall be output as 0).

• You are not expected to evaluate or optimize the expression in any way. In particular, you should not assume that the operators necessarily satisfy any associative, commutative or other algebraic identities. That is, you should not assume that e.g. 1 + 2 equals 2 + 1 or that 1 + (2 + 3) equals (1 + 2) + 3.

• You may assume that numbers in the input do not exceed 2³¹ − 1 = 2147483647.

These rules are intended to ensure that the correct output is uniquely defined by the input.

Examples:

Here are some valid input expressions and the corresponding outputs, presented in the form "input" -> "output":

"1"                  ->  "1"
"1 + 2"              ->  "1 2 +"
" 001  +  02 "       ->  "1 2 +"
"(((((1))) + (2)))"  ->  "1 2 +"
"1+2"                ->  "1 2 +"
"1 + 2 + 3"          ->  "1 2 + 3 +"
"1 + (2 + 3)"        ->  "1 2 3 + +"
"1 + 2 * 3"          ->  "1 2 3 * +"
"1 / 2 * 3"          ->  "1 2 / 3 *"
"0102 + 0000"        ->  "102 0 +"
"0-1+(2-3)*4-5*(6-(7+8)/9+10)" -> "0 1 - 2 3 - 4 * + 5 6 7 8 + 9 / - 10 + * -"

(At least, I hope all these are correct; I did the conversion by hand, so mistakes might have crept in.)

Just to be clear, the following inputs are all invalid; it does not matter what your solution does if given them (although, of course, e.g. returning an error message is nicer than, say, consuming an infinite amount of memory):

""
"x"
"1 2"
"1 + + 2"
"-1"
"3.141592653589793"
"10,000,000,001"
"(1 + 2"
"(1 + 2)) * (3 / (4)"

Answer 1

Shell utils -- 60 chars

bc -c|sed -re's/[@iK:Wr]+/ /g;s/[^0-9]/ &/g;s/ +/ /g;s/^ //'

Fixed the various problems, but it got a lot longer :(

Answer 2

C, 250 245 236 193 185 chars

char*p,b[99];f(char*s){int t=0;for(;*p-32?
*p>47?printf("%d ",strtol(p,&p,10)):*p==40?f(p++),++p:
t&&s[t]%5==2|*p%5-2?printf("%c ",s[t--]):*p>41?s[++t]=*p++:0:++p;);}
main(){f(p=gets(b));}

Here's a readable version of the ungolfed source, that still reflects the basic logic. It's actually a rather straightforward program. The only real work it has to do is to push a low-associativity operator onto a stack when a high-associativity operator is encountered, and then pop it back off at the "end" of that subexpression.

#include <stdio.h>
#include <stdlib.h>

static char buf[256], stack[256];
static char *p = buf;

static char *fix(char *ops)
{
    int sp = 0;

    for ( ; *p && *p != '\n' && *p != ')' ; ++p) {
        if (*p == ' ') {
            continue;
        } else if (*p >= '0') {
            printf("%ld ", strtol(p, &p, 10));
            --p;
        } else if (*p == '(') {
            ++p;
            fix(ops + sp);
        } else {
            while (sp) {
                if ((ops[sp] == '+' || ops[sp] == '-') &&
                        (*p == '*' || *p == '/')) {
                    break;
                } else {
                    printf("%c ", ops[sp--]);
                }
            }
            ops[++sp] = *p;
        }
    }
    while (sp)
        printf("%c ", ops[sp--]);
    return p;
}

int main(void)
{
    fgets(buf, sizeof buf, stdin);
    fix(stack);
    return 0;
}

Answer 3

Python 2, 290 272 268 250 243 238 bytes

Now finally shorter than the JS answer!

This is a full program which uses a basic implementation of the shunting yard algorithm. Input is given as a quoted string, and the result is printed to STDOUT.

import re
O=[];B=[]
for t in re.findall('\d+|\S',input()):exec("O=[t]+O","i=O.index('(');B+=O[:i];O=O[i+1:]","while O and'('<O[0]and(t in'*/')<=(O[0]in'*/'):B+=O.pop(0)\nO=[t]+O","B+=`int(t)`,")[(t>'/')+(t>')')+(t>'(')]
print' '.join(B+O)

Try it online!

---

Explanation:

The first thing we need to do is convert the input into tokens. We do this using by finding all matches of the regex \d+|\S, roughly translated to "any group of digits, and any non-space character". This removes whitespace, parses adjacent digits as single tokens, and parses operators seperately.

For the shunting yard algorithm, there are 4 distinct token types we need to handle:

• ( - Left parenthesis
• ) - Right parenthesis
• +-*/ - Operators
• 9876543210 - Numeric literals

Thankfully, the ASCII codes of these are all grouped in the order shown, so we can use the expression (t>'/')+(t>')')+(t>'(') to calculate the token type. This results in 3 for digits, 2 for operators, 1 for a right parenthesis and 0 for a left parenthesis.

Using these values, we index into the large tuple after exec to get the corresponding snippet to execute, based on the token type. This is different for each token and is the backbone of the shunting yard algorithm. Two lists are used (as stacks): O (operation stack) and B (output buffer). After all the tokens have been run, the remaining operators on the O stack are concatenated with the output buffer, and the result is printed.

Answer 4

Bash w/ Haskell w/ C preprocessor sed, 180 195 198 275

echo 'CNumO+O-O*fromInteger=show
CFractionalO/
main=putStr$'$*|sed 's/C\([^O]*\)/instance \1 String where /g
s/O\(.\?\)/a\1b=unwords\[a,b,\"\1\"];/g'|runghc -XFlexibleInstances 2>w

At last, it's not longer than the C solution anymore. The crucial Haskell part is almost as lazy as the bc solution...

Takes input as command-line parameters. A file w with some ghc warning messages will be created, if you don't like this change to runghc 2>/dev/null.

Answer 5

Prolog (SWI-Prolog), 113 bytes

c(Z,Q):-Z=..[A,B,C],c(B,S),c(C,T),concat_atom([S,T,A],' ',Q);term_to_atom(Z,Q).
p(X,Q):-term_to_atom(Z,X),c(Z,Q).

Try it online!

SWI Prolog has a much better set of builtins for this than GNU Prolog does, but it's still held back somewhat by the verbosity of Prolog's syntax.

Explanation

term_to_atom will, if run backwards, parse an infix-notation expression (stored as an atom) into a parse tree (obeying the usual precedence rules, and deleting leading zeroes and whitespace). We then use the helper predicate c to do a structural recursion over the parse tree, converting into postfix notation in a depth-first way.

Answer 6

Javascript (ES6), 244 bytes

f=(s,o={'+':1,'-':1,'*':2,'/':2},a=[],p='',g=c=>o[l=a.pop()]>=o[c]?g(c,p+=l+' '):a.push(l||'',c))=>(s.match(/[)(+*/-]|\d+/g).map(c=>o[c]?g(c):(c==')'?eval(`for(;(i=a.pop())&&i!='(';)p+=i+' '`):c=='('?a.push(c):p+=+c+' ')),p+a.reverse().join` `)

Example:
Call: f('0-1+(2-3)*4-5*(6-(7+8)/9+10)')
Output: 0 1 - 2 3 - 4 * + 5 6 7 8 + 9 / - 10 + * - (with a trailing space)

Explanation:

f=(s,                                                     //Input string
    o={'+':1,'-':1,'*':2,'/':2},                          //Object used to compare precedence between operators
    a=[],                                                 //Array used to stack operators
    p='',                                                 //String used to store the result
    g=c=>                                                 //Function to manage operator stack
        o[l=a.pop()]>=o[c]?                               //  If the last stacked operator has the same or higher precedence
            g(c,p+=l+' '):                                //  Then adds it to the result and call g(c) again
            a.push(l||'',c)                               //  Else restack the last operator and adds the current one, ends the recursion.
)=>                                                       
    (s.match(/[)(+*/-]|\d+/g)                             //Getting all operands and operators
    .map(c=>                                              //for each operands or operators
        o[c]?                                             //If it's an operator defined in the object o
            g(c)                                          //Then manage the stack
            :(c==')'?                                     //Else if it's a closing parenthese
                eval(`                                    //Then
                    for(;(i=a.pop())&&i!='(';)            //  Until it's an opening parenthese
                        p+=i+' '                          //  Adds the last operator to the result
                `)                                        
                :c=='('?                                  //Else if it's an opening parenthese
                    a.push(c)                             //Then push it on the stack
                    :p+=+c+' '                            //Else it's an operand: adds it to the result (+c removes the leading 0s)
        )                                                 
    )                                                     
    ,p+a.reverse().join` `)                               //Adds the last operators on the stack to get the final result

Answer 7

R, 142 bytes

R is able to parse itself, so rather than re-invent the wheel, we just put the parser to work, which outputs prefix notation, and use a recursive function to switch it to postfix notation.

f=function(x,p=1){
if(p)x=match.call()[[2]]
if((l=length(x))>1){
f(x[[2]],0)
if(l>2)f(x[[3]],0)
if((z=x[[1]])!="(")cat(z,"")
}else cat(x,"")
}

The p argument is to control the use of non-standard evaluation (the bane of R programmers everywhere), and there are a few extra ifs in there to control the outputting of brackets (which we want to avoid).

Input: (0-1+(2-3)*4-5*(6-(7+8)/9+10))

Output: 0 1 - 2 3 - 4 * + 5 6 7 8 + 9 / - 10 + * -

Input: (((((1))) + (2)))

Output: 1 2 +

As a bonus, it works with arbitrary symbols, and any pre-defined functions with up to two arguments:

Euler's identity

Input: e^(i*pi)-1

Output: e i pi * ^ 1 -

Dividends of 13 between 1 and 100

Input: which(1:100 %% 13 == 0)

Output: 1 100 : 13 %% 0 == which

Linear regression of baby chicken weight as a function of time

Input: summary(lm(weight~Time, data=ChickWeight))

Output: weight Time ~ ChickWeight lm summary

The last example is perhaps a little outside the scope of the OP, but it does use postfix notation, so...

Answer 8

Perl 5, 177 bytes

Exploiting Perl operator overloading:

sub{use overload nomethod=>sub{bless[@_[3,0,1]]};sub new{shift;bless[0,@_]}sub p{$_[0][0]?join$",(map$_[0][$_]->p,1,2),$_[0][0]:$_[0][1]}eval(pop=~s/0*(\d+)/new main($1)/gr)->p}

Try it online!