# Convert infix expressions to postfix notation

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.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)"
``````
-
Is Lisp like notation acceptable? For example `1 2 3 4 +` mean ` 1 + 2 + 3 + 4` . – Ćukasz Niemier May 15 '12 at 22:31
@Hauleth: Not in this challenge, no. Besides, without parentheses, how would you parse `1 2 3 4 + *`? – Ilmari Karonen May 15 '12 at 23:06
So, no trailing whitespace (including a newline) is permitted in the otuput? – breadbox May 16 '12 at 2:19
@breadbox: Trailing newlines are OK. In fact, let me explicitly clarify that any trailing whitespace is allowed. – Ilmari Karonen May 16 '12 at 15:22

## 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 :(

-
This is rather clever, except that it doesn't seem to handle numbers greater than 9 correctly. – breadbox May 16 '12 at 13:48
@breadbox, `sed -re's/[:@iKWr]+/ /g'` fixes it at 1 character cost. – ugoren May 16 '12 at 14:44
oops, though @ugoren suggestion doesn't work since consecutive operators no longer have a space between them; I've gotta come up with a fix for that too – Geoff Reedy May 16 '12 at 15:40

## C, 250245236193 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;
}
``````
-
Save chars by removing `if`. E.g. `if(!*p||*p==41)return p;s[++t]=*p;}` -> `return*p&&*p-41?s[++t]=*p:p;` – ugoren May 16 '12 at 8:22
K&R style declaration: `*f(p,s)char*p,s;{` – ugoren May 16 '12 at 8:23
1. It's an error to return if the `if` test fails. 2. I know, but K&R function decls is where I draw the line. I just can't go back to them. – breadbox May 16 '12 at 8:51
I thought the return is at the function end anyway. Missed the `}}` and `for`. But here's an imrovment: `printf(" %ld"+!a,...` – ugoren May 16 '12 at 9:21
Also I think you should make `p` global (the recursive call just assigns the callee `p` back to the caller's). Then do `f(p=gets(b))`. – ugoren May 16 '12 at 9:30

## Bash w/ Haskell w/ C preprocessor sed, 180 195198275

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

-