はじめに
ここではdcの基本的な考え方であるスタックについて勉強していきましょう。
スタックというのはデータを上に積んでいって、それを上から取り扱うような構造をいいます。
1ページ目ではスタックについて触れずに進めていましたが、スタックを理解するために、いったん1ページ目の内容は忘れて読み進めてください。
スタックの扱い方
2 13
数字を書くとその数字がスタックに積まれます。数字同士はスペースで区切ってください。
| 入力 | 5 3 9 |
|---|
??
「?」で数字を読み込むと前から順にスタックに積まれていきます。
「?」は一行だけ読み込みます。
6 8pn
| 出力 | 8 8 |
|---|
「p」は一番上の値に改行を付けて出力します。
「n」は一番上の値を取り出し、改行を付けずに出力します。
計算のコマンド
1ページ目では計算に「+」「-」「*」「/」「%」「^」が使えると紹介しましたが、実際にスタックがどうなっているかを見ていきましょう。この6つは2つの値を取り出し、その計算結果をスタックに積むという操作をしています。
6 8+
$6 + 8$を計算します。
8 2-
$8 - 2$を計算します。
3 4*
$3 \times 4$を計算します。
11 4/
$11 \div 4$を計算します。
整数の割り算は切り捨てて整数が答えになる。
11 4%
$11 \div 4$の余りを計算します。
3 2^
$3^2$を計算します。
実際の問題
1ページ目で扱った問題を見ていきましょう。
ABC004
| 入力 | 1000 |
|---|
?2*p
| 出力 | 2000 |
|---|
$1000 \times 2$を計算します。
| 入力 | 2 |
|---|
?1+2/p
| 出力 | 1 |
|---|
$(2+1) \div 2$を計算します。
複数のスタックを用いる
他の問題も見ていきましょう。
ABC001
| 入力 | 15 10 |
|---|
??-p
| 出力 | 5 |
|---|
| 入力 | 50 7 40 8 30 9 |
|---|
?*?*?*++A/p
| 出力 | 94 |
|---|
$(50\times7+40\times8+30\times9)\div10$を計算します。
前述しましたが、「A」は「10」と解釈されます。
#他の演算子
「~」は割り算をして商と余りをスタックに積みます。
| 入力 | 23 |
|---|
?A~+p
| 出力 | 5 |
|---|
この問題のためにあるようなコマンドですね。
「|」はべき剰余を計算します。
5 2 7|
$5^2$を$7$で割った余りを計算しています。
「v」はルートを計算します。桁数には気をつけるようにしましょう。
Bv
$\sqrt{11}$を計算しています。
数字が負のときは、なにも積まないので、ただ一番上のデータが消えます。
おわりに
ここまでの知識で解ける問題があるのでこちらの「複数のスタックを用いる」の箇所にある問題を解いてみましょう。
次からは、コマンドを勉強していきましょう。