Q&A
トレースの過程を書いた方が、間違っている箇所が指摘できて良いと思います。
２００５年秋期
普通の数式をスタックを使って後置表記法に変換するプログラムです。
＜変換の優先度＞
・（ …４
・０～９までの数字 …３
・×、÷ …２
・＋、－ …１
・） …０
スタックの底は制御文字「ＥＯＳ」が入ります。優先度はー１です。
プログラムは以下の通りです。
・initStack()
・k ← 0
■i : 0, i < Textlen, 1
| ■getPriority(Exptext[i] <= getPriority(top()) and top() != "("
| |・Postfix[k] ← pop()
| |・k ← k + 1
| ■
| ↑Exptext[i] != ")"
| | ・push(Exptext[i])
| ------------------
| | ・pop() /* 取り出した要素は使わない */
| ↓
■
配列Exptextから取り出した文字が ")" だった時の処理 pop() がよくわかりません。これはスタックから取り出すんですよね？ スタックの先頭から取り出したその文字を次にどうするのかがわかりません。
この問題は配列Exptextの例として （２＋４）×３+５×６ を取り上げてるんですが、トレースしていくとどうしても５番目の文字で止まってしまいます。回答の処理の流れを見てもいまいちわかりません。またコメントの「取り出した要素は使わない」というのもよくわからないというか、このプログラムの処理後の文字列は "(" と ")" が消えているので多分これのことを言っているんだろうなとはなんとなく思うのですが、トレースしていくと「？？？」となってしまいます。どなたか教えてください。
リンク内容
午後問題の14~18pです。
【トレース手順】
・最初の文字 "(" の処理
⇒ スタックの先頭文字 (EOS) の方が優先度が低い
⇒スタックに "(" を格納
・２番目の文字 "2" の処理
⇒スタックの先頭文字の方が優先度が高いが "(" である
⇒スタックに "2" を格納
・３番目の文字 "+" の処理
⇒スタックの先頭文字の方が優先度が高い
⇒Postfix[0] に "2" を代入
⇒スタックに "+" を格納
・４番目の文字 "4" の処理
⇒スタックの先頭文字の方が優先度が低い
⇒スタックに "4" を格納
・５番目の文字 ")" の処理
⇒スタックの先頭文字の方が優先度が高い
⇒Postfix[1] に "4" を代入
ここでどうしても止まってしまいます。この時点で
Postfix 【24】
スタック 【+(EOS】
になっていますよね？ 回答によるとこの次は
Postfix 【24+】
スタック 【(EOS】
になるということですが、pop() で "+" を取り出すにしてもそれをPostfixに代入する処理がないような…
あとこの ")" の処理が終わった後スタックは【EOS】だけになっているそうなのですが、いつのまにか "(" が消えています。これも一体何なのでしょうか。
なるほど。そうですね。
回答3件
0
ベストアンサー
・５番目の文字 ")" の処理
⇒スタックの先頭文字の方が優先度が高い
⇒Postfix[1] に "4" を代入
このあと、
⇒スタックの先頭文字("+")の方が(")"より)優先度が高い
⇒Postfix[2] に "+" を代入
となると思います。
| ■getPriority(Exptext[i] <= getPriority(top()) and top() != "("
| |・Postfix[k] ← pop()
| |・k ← k + 1
| ■
の部分はループと思いますが、認識合っていますか？
また、スタックに残った"("はその後の
| | ・pop() /* 取り出した要素は使わない */
で取り除かれます。
投稿2015/09/23 11:52
編集2015/09/23 11:59総合スコア1546
getPriority の処理はループでしたね…一回処理したら次の条件式にとんでました。基本的なミスですみません…ありがとうございます！
0
一言で「取り出す」と言っていますが，実際の処理は次の手順です．
0. スタックの一番上の要素を取得する
0. スタックの一番上を削除する
0. 1.で取得した要素を返却する
ここで鍵になるのは「返却する」ということです．
どこに返却されるかというと，この場合pop()に返却されます．
ここで文字型の変数(例えばa)を用意して
a = pop()
とすれば使えますが，ここでは代入していないので，これ以降返却された値を使う術がなくなります．
そしてスタックからも2.によって削除されているので，結果的に除去されていることになるのです．
投稿2015/09/23 09:56
総合スコア20651
ありがとうございます！
0
投稿2015/09/23 07:22
総合スコア1124
回答ありがとうございます…と言いたいところですがやっぱりわかりません…
後置表記法は "(" と ")" は使わないことはわかるのですが、それを除去するプログラムが問題文には書かれていないような気がするのですが…
質問に過去問のリンクを貼っておいたので見ていただけないでしょうか？ すみません…
スタックExptextの最初の要素は"("で、優先順位4で最高です。
getPriorityで始まるループは、始点の文字と等価か優先順位の高い文字列まで、スタックExptextから文字列を取り出し、Postfixに入れるようになっています。で、最初のケースでは")"迄です。
で、次のIF条件ですが、
・")"でなければ、スタックExptextに戻す。
・")"であれば、更にスタックExptextから取り出す。（結果、")"は何もされずに破棄）
という風になっています。
基本的な見落としをしていました。すみません…回答ありがとうございます！
あなたの回答
tips
プレビュー
