Wikipedia: Infix to Postfix Conversion Extract

http://en.wikipedia.org/wiki/Shunting_yard_algorithm

This has been simplified to remove the processing of function calls / method invocations.  — tjr

The algorithm in detail

• While there are tokens to be read:

Read a token.

• If the token is a number, then add it to the output queue.
• Else if the token is an operator, o₁, then:

1) while there is an operator, o₂, at the top of the stack, and either

o₁ is associative or left-associative, and its precedence is less than or equal to that of o₂, or

o₁ is right-associative and its precedence is less than that of o₂,

pop o₂ off the stack, onto the output queue;

2) push o₁ onto the operator stack.

• Else if the token is a left parenthesis, then push it onto the stack.
• Else if the token is a right parenthesis, then pop operators off the stack, onto the output queue, until the token at the top of the stack is a left parenthesis, at which point it is popped off the stack but not added to the output queue. If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.

• When there are no more tokens to read, pop all the operators, if any, off the stack, add each to the output as it is popped out and exit. (These must only be operators; if a left parenthesis is popped, then there are mismatched parentheses.)

Input 3+4*2/(1-5)^2
Read "3"
 Add "3" to the output
  Output: 3

Read "+"
 Push "+" onto the stack
  Output: 3
  Stack: +

Read "4"
 Add "4" to the output
  Output: 3 4
  Stack: +

Read "*"
 Push "*" onto the stack
  Output: 3 4
  Stack: + *

Read "2"
 Add "2" to the output
  Output: 3 4 2
  Stack: + *

Read "/"
 Pop "*" off stack and add it to output, push "/" onto the stack
  Output: 3 4 2 *
  Stack: + /

Read "("
 Push "(" onto the stack
  Output: 3 4 2 *
  Stack: + / (

Read "1"
 Add "1" to output
  Output: 3 4 2 * 1
  Stack: + / (

Read "-"
 Push "-" onto the stack
  Output: 3 4 2 * 1
  Stack: + / ( -

Read "5"
 Add "5" to output
  Output: 3 4 2 * 1 5
  Stack: + / ( -

Read ")"
 Pop "-" off stack and add it to the output, pop (
  Output: 3 4 2 * 1 5 -
  Stack: + /

Read "^"
 Push "^" onto stack
  Output: 3 4 2 * 1 5 -
  Stack: + / ^

Read "2"
 Add "2" to output
  Output: 3 4 2 * 1 5 - 2
  Stack: + / ^

End of Expression
 Pop stack to output
  Output: 3 4 2 * 1 5 - 2 ^ / +