A conversão entre os formatos infixo e posfixo pode ser feita através do algoritmo de shunting-yard.
Para entendê-lo, considere que cada operador possui tanto uma precedência quanto uma associatividade: vezes aplica antes de mais, por exemplo, e ambos se associam à esquerda. A - B - C
se aplica como (A - B) - C
e não como A - (B - C)
, mas A^B^C
se aplica como A^(B^C)
e não o contrário. Sub-expressões entre parênteses se aplicam antes do resto.
O algoritmo funciona lendo cada token (número, operador, abre parêntese ou fecha parêntese) da entrada e então colocando-o ou na saída ou em uma pilha. Números vão sempre pra saída. Operadores vão pra pilha, mas antes eles retiram da pilha (mandando pra saída) qualquer operador cuja precedência seja menor ou menor-ou-igual a ele (dependendo da associatividade). Abre parênteses vão pra pilha, e fecha parênteses desmpilha tudo até o abre parênteses correspondente e joga na saída.
1 + 2 * 3 []
_ + 2 * 3 [] 1
_ 2 * 3 [+] 1
_ * 3 [+] 1 2
_ 3 [+, *] 1 2
_ [+, *] 1 2 3
[+] 1 2 3 *
[] 1 2 3 * +
(1 + 2) * 3 []
_1 + 2) * 3 [(]
_ + 2) * 3 [(] 1
_ 2) * 3 [(, +] 1
_) * 3 [(, +] 1 2
_ * 3 [] 1 2 +
_ 3 [*] 1 2 +
_ [*] 1 2 + 3
[] 1 2 + 3 *
1 + 2*3 / (4 ^ (5+6) ) []
_ + 2*3 / (4 ^ (5+6) ) [] 1
_ 2*3 / (4 ^ (5+6) ) [+] 1
_*3 / (4 ^ (5+6) ) [+] 1 2
_3 / (4 ^ (5+6) ) [+, *] 1 2
_ / (4 ^ (5+6) ) [+, *] 1 2 3
_ (4 ^ (5+6) ) [+, /] 1 2 3 *
_4 ^ (5+6) ) [+, /, (] 1 2 3 *
_ ^ (5+6) ) [+, /, (] 1 2 3 * 4
_ (5+6) ) [+, /, (, ^] 1 2 3 * 4
_5+6) ) [+, /, (, ^, (] 1 2 3 * 4
_+6) ) [+, /, (, ^, (] 1 2 3 * 4 5
_6) ) [+, /, (, ^, (, +] 1 2 3 * 4 5
_) ) [+, /, (, ^, (, +] 1 2 3 * 4 5 6
_ ) [+, /, (, ^] 1 2 3 * 4 5 6 +
_ [+, /] 1 2 3 * 4 5 6 + ^
[+] 1 2 3 * 4 5 6 + ^ /
[] 1 2 3 * 4 5 6 + ^ / +
Exemplo em C no rosettacode.