59 lines
1.3 KiB
Text
59 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(' ')
|