Algorithm developed by Edsger Dijkstra for converting infix expression into a postfix expression. Algorithm uses a stack for stacking operators and an output queue.

Infix: 3 + 4 * 20
Postfix: 3 4 20 * +

It uses a queue as a resulting structure and a stack for operators. Algoritm has simple steps:

  1. split the input
  2. go to loop
  3. if the character is a numeric value, put it into the queue
  4. if the character is an operator, put it into the operator stack
  5. if, on the operator stack, is already an operator with a bigger or equal precedence (and has a left associativity), pop it into the queue
  6. pop everything from the stack into the output queue

Ruby implementation:

def shunting(str)
  @precedence = {
    '*' => 2,
    '/' => 2,
    '+' => 1,
    '-' => 1
  }

  queue = []
  stack = []
  chars = str.split(//)

  chars.each do |c|
    next if c =~ /^\s*$/

    if c =~ /\d/
      queue << c

    elsif stack.empty? || stack.last == c
      stack << c

    elsif @precedence[stack.last] < @precedence[c]
      stack << c

    elsif @precedence[stack.last] >= @precedence[c]
      count = 0
      stack.each do |s|
        if @precedence[s] > @precedence[c]
          queue << s
          count += 1
        end
      end
      stack.pop(count)
      stack << c
    end
  end

  queue << stack.pop while stack.any?
  queue.join
end

puts shunting('2+3*2')
#=> 232*+

This code is not a full implementation as it does not implement few cases like brackets and associativity.