123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657 |
- #!/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(' ');
|