Quando vi o título dessa pergunta encerrada , pensei que parecia um desafio interessante para o código de golfe. Então deixe-me apresentá-lo como tal:

Desafio:

Escreva um programa, expressão ou sub-rotina que, dada uma expressão aritmética na notação infix , como 1 + 2, emita a mesma expressão na notação postfix , ie 1 2 +.

(Observação: um desafio semelhante foi postado no início de janeiro. No entanto, acho que as duas tarefas são suficientemente diferentes em detalhes para justificar esse desafio separado. Além disso, só notei o outro segmento depois de digitar tudo abaixo, e prefiro não apenas jogue tudo fora.)

Entrada:

A entrada é constituído por uma expressão aritmética infixa válido que consiste em números (números inteiros não negativos representada como sequências de um ou mais dígitos decimais), equilibrado parênteses para indicar uma subexpressão agrupados, e os quatro infixa binários operadores + , -, *e /. Qualquer um deles pode ser separado (e toda a expressão envolvida) por um número arbitrário de caracteres de espaço, que deve ser ignorado. ^{1 1}

Para quem gosta de gramáticas formais, aqui está uma gramática simples, semelhante a BNF, que define entradas válidas. Por questões de clareza e clareza, a gramática não inclui os espaços opcionais, que podem ocorrer entre dois tokens (exceto dígitos dentro de um número):

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

_{¹ O único caso em que a presença de espaços pode afetar a análise é quando eles separam dois números consecutivos; no entanto, como dois números não separados por um operador não podem ocorrer em uma expressão de infixo válida, esse caso nunca pode ocorrer em entrada válida.}

Saída:

A saída deve ser uma expressão postfix equivalente à entrada. A expressão de saída deve consistir apenas de números e operadores, com um único carácter de espaço entre cada par de símbolos adjacentes, como na seguinte gramática (que não incluem os espaços) ² :

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

_{² Novamente, por simplicidade, a numberprodução nesta gramática admite números com zeros à esquerda, mesmo que sejam proibidos na saída pelas regras abaixo.}

Operador precedente:

Na ausência de parênteses, as seguintes regras de precedência se aplicam:

• Os operadores *e /têm maior precedência que +e -.
• Os operadores *e /têm precedência igual entre si.
• Os operadores +e -têm precedência igual entre si.
• Todos os operadores são associativos à esquerda.

Por exemplo, as duas expressões a seguir são equivalentes:

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

e ambos devem produzir a seguinte saída:

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

(Essas são as mesmas regras de precedência que no idioma C e na maioria dos idiomas dele derivados. Provavelmente se assemelham às regras que você aprendeu no ensino fundamental, exceto, possivelmente, pela relativa precedência de *e /.)

Regras diversas:

• Se a solução fornecida for uma expressão ou sub-rotina, a entrada deve ser fornecida e a saída retornada como uma única sequência. Se a solução for um programa completo, ele deve ler uma linha contendo a expressão infix da entrada padrão e imprimir uma linha contendo a versão do postfix na saída padrão.

• Os números na entrada podem incluir zeros à esquerda. Os números na saída não devem ter zeros à esquerda (exceto o número 0, que deve ser exibido como 0).

• Não é esperado que você avalie ou otimize a expressão de forma alguma. Em particular, você não deve assumir que os operadores necessariamente satisfazem qualquer identidade associativa, comutativa ou outras identidades algébricas. Ou seja, você não deve assumir que, por exemplo, 1 + 2igual 2 + 1ou 1 + (2 + 3)igual a (1 + 2) + 3.

• Você pode supor que os números na entrada não excedam 2 ³¹ - 1 = 2147483647.

Essas regras visam garantir que a saída correta seja definida exclusivamente pela entrada.

Exemplos:

Aqui estão algumas expressões de entrada válidas e as saídas correspondentes, apresentadas no formulário "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 + * -"

(Pelo menos, espero que tudo isso esteja correto; fiz a conversão manualmente, para que erros possam ter surgido.)

Só para esclarecer, as seguintes entradas são todas inválidas; ele não importa o que sua solução não se lhes deu (embora, é claro, por exemplo, retornando uma mensagem de erro é mais agradável do que, digamos, consumindo uma quantidade infinita de memória):

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

Shell utils - 60 caracteres

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

Corrigimos os vários problemas, mas demorou muito mais :(

C, 250 245 236 193 185 caracteres

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));}

Aqui está uma versão legível da fonte não destruída, que ainda reflete a lógica básica. Na verdade, é um programa bastante simples. O único trabalho real que ele precisa fazer é colocar um operador de baixa associatividade em uma pilha quando um operador de alta associatividade for encontrado e, em seguida, recolocá-lo no "final" dessa subexpressão.

#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;
}

Bash com Haskell com Pré-processador C 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

Por fim, não é mais do que a solução C. A parte crucial de Haskell é quase tão preguiçosa quanto a solução bc ...

Recebe a entrada como parâmetros da linha de comando. Um arquivo wcom algumas mensagens de aviso do ghc será criado, se você não gostar dessa alteração runghc 2>/dev/null.

Python 2, 290 272 268 250 243 238 bytes

Agora finalmente mais curto que a resposta JS!

Este é um programa completo que utiliza uma implementação básica do algoritmo shunting yard . A entrada é fornecida como uma string entre aspas e o resultado é impresso em 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)

Experimente online!

Explicação:

A primeira coisa que precisamos fazer é converter a entrada em tokens. Fazemos isso usando todas as correspondências da regex \d+|\S, traduzidas aproximadamente para "qualquer grupo de dígitos e qualquer caractere que não seja espaço". Isso remove o espaço em branco, analisa os dígitos adjacentes como tokens únicos e analisa os operadores separadamente.

Para o algoritmo do shunting yard, existem 4 tipos de token distintos que precisamos tratar:

• ( - Parêntese esquerdo
• ) - Parêntese direito
• +-*/ - Operadores
• 9876543210 - Literais numéricos

Felizmente, os códigos ASCII desses estão todos agrupados na ordem mostrada, para que possamos usar a expressão (t>'/')+(t>')')+(t>'(')para calcular o tipo de token. Isso resulta em 3 para dígitos, 2 para operadores, 1 para parêntese direito e 0 para parêntese esquerdo.

Usando esses valores, indexamos a tupla grande após execa execução do snippet correspondente, com base no tipo de token. Isso é diferente para cada token e é a espinha dorsal do algoritmo do shunting yard. Duas listas são usadas (como pilhas): O(pilha de operação) e B(buffer de saída). Após a execução de todos os tokens, os operadores restantes na Opilha são concatenados com o buffer de saída e o resultado é impresso.

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

Experimente online!

O SWI Prolog tem um conjunto muito melhor de componentes para isso do que o GNU Prolog, mas ainda é um pouco retido pela verbosidade da sintaxe do Prolog.

Explicação

term_to_atom, se for executado ao contrário, analisará uma expressão de notação de infixo (armazenada como um átomo) em uma árvore de análise (obedecendo às regras de precedência usuais e excluindo zeros à esquerda e espaços em branco). Em seguida, usamos o predicado auxiliar cpara fazer uma recursão estrutural sobre a árvore de análise, convertendo em notação postfix de maneira profunda.

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

Exemplo:
Chamada: f('0-1+(2-3)*4-5*(6-(7+8)/9+10)')
Saída: 0 1 - 2 3 - 4 * + 5 6 7 8 + 9 / - 10 + * -(com um espaço à direita)

Explicação:

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

R, 142 bytes

R é capaz de analisar a si próprio; portanto, em vez de reinventar a roda, apenas colocamos o analisador em funcionamento, o que gera notação de prefixo e usamos uma função recursiva para alternar para a notação de postfix.

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,"")
}

O pargumento é controlar o uso de avaliação não-padrão (a desgraça dos programadores R em todos os lugares), e existem alguns ifs extras para controlar a saída de colchetes (que queremos evitar).

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

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

Entrada: (((((1))) + (2)))

Saída: 1 2 +

Como bônus, funciona com símbolos arbitrários e quaisquer funções predefinidas com até dois argumentos:

Identidade de Euler

Entrada: e^(i*pi)-1

Saída: e i pi * ^ 1 -

Dividendos de 13 entre 1 e 100

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

Saída: 1 100 : 13 %% 0 == which

Regressão linear do peso do frango bebê em função do tempo

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

Saída: weight Time ~ ChickWeight lm summary

O último exemplo talvez esteja um pouco fora do escopo do OP, mas ele usa a notação postfix, então ...