Mon Jun 15 2020

dc はパズルとして面白い. 逆に本来の計算機として使う人なんていないんじゃないだろうか. シェルスクリプトからさっと呼ぶ計算コマンドとして使えなくはないけど.

man

マニュアルとして man dc があるが, ここには主要コマンドが載っているだけで, そこに載っていないコマンドや仕様がある. ソースコードをこないだ読んでまとめた → memo/dc.

tac

何行かわからないけれど何行かの整数が与えられる. これを逆順に出力せよ.

   seq 5 | dc -e '(FILL YOUR CODE)'
5
4
3
2
1

ここで入力が整数だけとしているのは dc に都合が良いから (? で読めるから). 何行か分からないというのが dc に優しくない. ? はちょうど一行を受け取って, dc コマンドとして実行する.

   seq 5 | tr '\n' ' ' | dc -e '(FILL YOUR CODE)'
5
4
3
2
1

1 2 3 4 5

である. ? は一行読み込んで実行する. 1 2 3 4 5 というのは dc 的には, 5 つのコマンドから成っている（空白区切りで）. 1 というコマンドはスタックに 1 を積む操作にほかならない. 2 から 5 も全く同様. というわけで,

seq | tr ... | dc -e '?'

という状態を残して終了する. 何もプリントさせてないので何も出力しないで終了するが, f はこのスタックの状態をプリントしてくれる. このとき, 今上に書いたように, スタックの頭から順に書いてくれる. というわけで,

   seq 5 | tr '\n' ' ' | dc -e '?f'
5
4
3
2
1

じゃあ元の問題に戻る. tr とかを挟まずに直接 dc に入力が渡されるパターン.

この入力のとき, 一回 ? を読んだところで一つの数値をスタックに積むことしかできない. z コマンドは現在のスタックのサイズ（長さ, 深さ）を取得する. ? で読んで入力がない場合, 何も実行されないのでスタックサイズが変わらない. ということで, この２つを組み合わせればできそうだ.

seq 5 | dc -e '
  stack_size = 0  # 前のスタックサイズを記録しておく変数
  loop {
    ?
    # z() で現在のスタックサイズを取得
    if (stack_size < z()) {  # 増えてるということは入力を受け取ったということ
      stack_size = z()
      continue
    } else {
      break
    }
  }
  f
'

seq 5 | dc -e '
  var@ = 0
  function r() {
    ?
    tmp_@ = var@
    var@ = z()
    if z() < tmp@ {
      r()  # recursive call
    }
  }
  r()
'

   seq 5 | dc -e '0s@[?zdl@rs@<r]dsrxf'
5
4
3
2
1

スタックサイズを記録するのにレジスタ @ を使ってるが, 入力が整数しか無い場合 scale レジスタが使える. s@ が k にできて, l@ を K に置き換えて良くなる. しかもこれは最初 0 で初期化されてるのも都合が良い.

seq 5 | dc -e '[?zdKrk<r]dsrxf'

dc やってく

man

tac