12
(一般的な話を書いたら長文になってしまいました。)
プログラムが実行時にどうメモリを使うか、については色々なやり方があって、実際に色々試されて来たのですが、その中で定番になったのが、データを寿命によって次のとおり分類する方法です。
プログラムを実行する前からどのくらい必要か決まっていて、実行開始時から終了時まで存在し続けるもの
関数/サブルーチンの実行中のみ必要で、サブルーチンを抜けたら不要になるもの
実行してみないとどのくらい必要になるかわからないけれど、一つの関数やサブルーチンの実行を越えて存在し続ける必要があるもの
Cの仕様では寿命をstorage durationと呼び、上の分類はそれぞれstatic、automatic、allocatedと呼んでいます。...
10
c で関数の引数は値渡し(複写渡し)であるため、です。
提示コード main 側は
push(stack_root, 3);
で stack_root が変更されて帰ってくることを期待している構造になっています。
が c の文法規則上、この呼び出しでは stack_root は変更されないのです。
push で行っている
stack_root = new_stack;
は main の stack_root とは異なる局所変数 stack_root を書き換えるだけです。
結果的に main の stack_root は変化しないままです。
大域変数だったら両者が同一なのでうまくいくわけです。
ではどうするか・・・なんですが、やりかたはいくつもあります。
策1 push pop には &...
7
1つだけ答えてみます
スタック領域のデータ構造はどのようなものなのか
スタックです
6
ヒープ領域とスタック領域の違いについて教えてください
メモリ領域にはテキスト領域、静的領域、ヒープ領域、スタック領域の4つの領域がある。
テキストはプログラム、静的はグローバル変数やstatic変数、スタックは装飾しのないローカル変数、ヒープは動的に確保できる
ここでプログラムやグローバル変数は利用する数や処理が確定すれば、プログラム中でサイズが変化することはない、スタックはOSやコンパイラがサイズを指定しているため定まったサイズが与えられる、ヒープはプログラム中で確保や廃棄されるため可変となる。
いつ確保されるのか
スタックではプログラムの変数の宣言の直後に、確保し}に到達すると廃棄される、これは関数を多く呼び出す構造をもたせた時、変数はスタックと同じ動作になる。正確にはブロックや関数毎に管理される。
...
5
スタックとヒープの違いを、使い方とデータ構造から説明します。
スタックは手続きの呼び出しで利用されます。手続きが呼び出されると、呼び出された手続きのローカル変数を格納するためのフレームがスタック上に生成されます。手続きからリターンすると、そのフレームも不要になります。メモリ領域の確保と解放のタイミングは、後から呼び出された手続きのフレームほど先に解放されます。
従って、スタックを実装するデータ構造としては、先入れ後出し(FILO)のデータ構造である「スタック(同じ名前なのでややこしいかもしれませんが)」がスタックを実装するのに利用されます。
これに対して、ヒープに確保されるメモリ領域は、確保と解放にこのような一定の順序がありません。先に確保したメモリ領域が先に解放されることもあります。そのため、...
5
質問がズレてきてしまっているのかもしれないので、最初の質問文「ヒープ領域とスタック領域の違いについて教えてください」に答えてみようと思います。
メモリ領域は元々は1つですがそれでは扱い辛いため、任意サイズ・ブロックに切り出し、使用・未使用を管理することで便利になります。この管理自体や切り出されたブロックのことをheapと呼びます。このメモリブロックをどのように使うかは利用者側の自由です。
グローバル変数(この用語自体、言語毎に定義されるもので一般化し辛いところですが)などはheapに内容を格納したりもします。
一方、プログラムは一般に呼び出し、戻りの繰り返しであり、グローバル変数のように常に特定のメモリを参照するわけにはいきません。例えば再起呼び出しなら呼び出し毎にそれぞれ異なるローカル変数が必要なはずです。...
3
もし質問の意図が、+演算子が、不定個数の被演算子を取れるようにできるか、ということだったら無理です。スタックから+演算子を取り出した時にどんな処理をすればいいのか、決定できないからです。
たとえば、乗算も加算も不定個数の被演算子を取れるようにしてみたとします。つまり2 * 3 * 4なら2 3 4 *、5 + 3なら5 3 +と書けるようにします。
ここで普通の式2 + 3 + 4 * 5を、逆ボーランドで記述してみます。とりあえず乗算は後回しにして
2 3 (4 * 5) +
さらに乗算も変換すると最終的に
2 3 4 5 * +
になります。
では次は2 + 3 * 4 * 5を変換してみます。上と同じ手順で
2 (3 * 4 * 5) +
2 3 4 5 * +
この通り、2 + 3 + ...
3
中間記法「3 + 4 + 5」は逆ポーランド記法ではどのように書けばよいのでしょうか?
ご質問中にあるように、3 4 + 5 +でも構いませんし、3 4 5 + +でも構いません。
「3 4 5 +」のように書くことはできないのでしょうか?
+がどのような演算として定義されているかによるわけですが、他の箇所に合わせて2数の加算と考えると、3 4 5 +だと、最後の4 5だけが加算されて、3 9と書いたのと同じ状態になってしまいます。
もし「スタック上から3つの数を取り出して全部を足し合わせる演算」、なんてものが定義できれば、3 4 5 add3なんて書き方もありになります。
逆ポーランド記法を基礎に置いた言語(と言うよりスタック操作を基礎、と言った方が良いかもしれませんが)Forthだとこんな感じ。(\...
1
小さいメモリアドレスに向かって積み上がっていく
とも限りません。 スタックが低いアドレスに向かって積まれない場合はありますか?
スタックの上限より小さいアドレスが書き換えられますか?
まあ普通はそうですね。今どきの CPU/OS であればメモリ保護機構なるものがついているので、スタック領域外は書き換えそのものができない(=どこも壊さない・壊せない)こともあります。
16bit CPU でスタックが 0x2000 番地から小さいアドレスへ進む場合を仮定して、
スタック末尾(=最小アドレス)が 0x1000 番地であったなら、スタックオーバーフローすると 0x0FFE 番地あたりを壊すわけです(=小さいアドレスを壊す)
スタック末尾が 0x0000 であったなら 0xFFFE 番地あたりを壊す(=...
1
scanfの%s指定子は空白類文字(半角スペースや改行)区切りに標準入力への文字列を入れていく物です
(char s[100]へガツンと一括入力される訳ではありません)
例えば「11 12 +」という入力がある場合
1回目のsには「11」
2回目のsには「12」
3回目のsには「+」
がそれぞれ入ります
各記号の場合、入力毎の1文字目しか見なくても問題がないので
s[0]を指定しているのだと思います。
余談ですが、多分どこかの本に出ている例題だったりしませんか?
入力例のような物があれば、デバッガやprintfをはさみつつ動作を確認すると分かりやすいかもしれません
(下記は一例です)
int main() {
int a, b;
top = 0;
char s[100];
...
1
現在のコードが正しいという前提では、インデックスをaの値でソートしてフェニック木(Binary Indexed Tree)の最大値、最小値版を使うのがシンプルじゃないかと思います。
フェニック木は、あるインデックスの値を変更したり(最大値版なら増やす、最小値版なら減らすのみ)、[0..i]の範囲の最大値・最小値を求めるような計算が高速に行えるデータ構造です。
(詳しくはググってください。ただしネット上の実装だとインデックスを1から始めるものとして書かれてることが多いので注意してください。下のコードは0から始まるインデックスです。)
フェニック木でa[i]未満の値のインデックスがiの位置にある状態にすると、今のコードで2重ループの内側のループになってる部分を範囲内のインデックスの最大値・...
1
まずはじめに、一般的な言語で大抵の場合は四則演算子+, -, *, ÷は二項演算子です。
これは、二つの数字を引数に取り、結果を返すというのが素直な理解だと思います。
なので、3 4 5 +の様に書けない理由は逆ポーランド記法が原因では無く、演算子が必要とする引数の個数の問題です。
なので、パーサーを自作するなどして、(式として見た場合)自分より左に異なる演算子が見つかるか、式の開始までの数字をすべて足す演算子を例えばsumなどと定義することは可能かと思います。
ですが、偶然にも逆ポーランド記法は非常に日本語と相性がいい事を理解しておられますでしょうか?
たとえば、
1 2 + 3 4 + ×
というRPN式は、素直に
「1に2を足した(+)ものと3に4を足した(+)ものを掛け合わせ(×)る」
と、...
上位に投票された、最小文字数のコミュニティ wiki 以外の回答のみが対象となります