58 lines
1.3 KiB
Text
58 lines
1.3 KiB
Text
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(var t = inp.shift) {
|
||
when (/\d/) { reduce(t) }
|
||
when ('(') { shift(t) }
|
||
when (')') {
|
||
while (ops) {
|
||
(var x = ops.pop) == '(' ? break : 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(' ')
|