#!/usr/bin/ruby
#
## https://rosettacode.org/wiki/Parsing/Shunting-yard_algorithm
#
var prec = Hash(
    '^' => 4,
    '*' => 3,
    '/' => 3,
    '+' => 2,
    '-' => 2,
    '(' => 1,
);
var assoc = Hash(
    '^' => 'right',
    '*' => 'left',
    '/' => 'left',
    '+' => 'left',
    '-' => 'left',
);
func shunting_yard(prog) {
    var inp = prog.words;
    var ops = [];
    var res = [];
    func report (op) { printf("%25s    %-7s %10s %s\n", res.join(' '), ops.join(' '), op, inp.join(' ')) }
    func shift  (t)  { report( "shift #{t}"); ops << t }
    func reduce (t)  { report("reduce #{t}"); res << t }
    while (inp) {
        given (inp.shift) { |t|
           when (/\d/) { reduce(t) }
           when ('(')  { shift(t) }
           when (')')  { var x; while (ops && (x = ops.pop) && (x != '(')) { reduce(x) } }
           default {
                var newprec = prec{t};
                while (ops) {
                    var oldprec = prec{ops[-1]};
                    break if (newprec > oldprec)
                    break if ((newprec == oldprec) && (assoc{t} == 'right'))
                    reduce(ops.pop);
                }
                shift(t);
            }
        }
    }
    while (ops) { reduce(ops.pop) }
    return res
}
say shunting_yard('3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3').join(' ');