[Question]
  [
When I saw the title of [this closed question](https://codegolf.stackexchange.com/questions/5786/converting-infix-expressions-to-postfix-expressions), 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](http://en.wikipedia.org/wiki/Infix_notation), like `1 + 2`, outputs the same expression in [postfix notation](http://en.wikipedia.org/wiki/Reverse_Polish_notation), i.e. `1 2 +`.
(Note: [A similar challenge was posted earlier in January.](https://codegolf.stackexchange.com/questions/4620/convert-from-infix-notation-to-prefix-notation) 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.1
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"
```
1 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)2:
```
expression  := number | expression sp expression sp operator
operator    := "+" | "-" | "*" | "/"
number      := digit | digit number
digit       := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
sp          := " "
```
2 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 231 − 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]
## 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]
## 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]
# 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](https://en.wikipedia.org/wiki/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!**](https://tio.run/nexus/python2#RY7BboMwDIbvPIWVS2wCFNa126DswAvksCNEajVSLRMLEcq0HvbuzEiVdvFv//rs36v7CvMSYbGJbnvTdFyS67xABOfZLa7Oj5dpQjmM6nd4k5nz4TsiUW1v9h0Fb0WjtMiEa3XBsL2hRElNp1rd1840mtWpqjbM/Hy4yYKGix8ZOum@NNziFibTnaRTi5t3n@rtRhHmgCUN/j@J7bPzESOdM0E9xlfJtNqU7sofmCQsTEmQxefsPHZK07qKMq9A4UMOe6D0MT9AisccnxQ80@5FVSWJPw)
---
**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]
## 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]
# [Prolog (SWI-Prolog)](http://www.swi-prolog.org), 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!](https://tio.run/nexus/prolog-swi#@5@sEaUTqGmlG2WrpxftqOOk4xyrk6zhpBOsCaScdUKAVH5ecmJJfGJJfq5GdLBOiI5jrI66gjpQl3VJalFufEk@RA5kjh5XgUYE2Dw0qQiQcWAV//8XaKgb6BpqaxjpGmtqmeiaammY6WqYa1to6ltqGxgaaIKM1gMA "Prolog (SWI) – TIO Nexus")
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]
## 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]
# 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 `if`s 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]
# [Perl 5](https://www.perl.org/), 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!](https://tio.run/##fY9dT4MwFIbv9ytOmuraUUILbn4Q5u5N3I13k5CZgaIbrWN@ZcG/Pk9BozK0gXB43@e8Pcek6@VwR7NoVz7dbJ/KFPQzSnq@gEKv0s2dXkRja90s07KcTZJZIKRQcVyFqEKRvmzLuzzbhI0vxSSJK@uYLU1mMsbn/F7nBSWCream0WgSu2MjlPC5@KLOmkLFVfo8XzKjTfReenLArhcO9/AeWM3zglHFvds1x/ZqF2Z6zXoAMyCKwN6JxlAbsfhkwAGfdDHgg/PNgZQKkAXpA/mHY/YozjmyzMcv6eaU45Pu2VqcnQ/fgHRxELRZVquc7LFI7ucOunMDNH6x3t@sZ@lvtubABdVmm1QF7m@W1XBrXssi@TNXKmk3k3hau6Euf04rXeUw3w344MgdDtjIZcfOCfdOHSXxGuwhsg736zmP7KowhBEcwwlWp7gQDoSJaDSz8m3P3rZ6YzQvjKDpq@HRhCbhp0xv9SY6pFlt80Y167zYZOTAHZUAKEfWQx17IxuApe2yrdcFqTMhfQT7f97XD/2z/uX0CqYX/bBX7T4A "Perl 5 – Try It Online")
]