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

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.