質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.48%

  • 基本情報技術者

    47questions

    基本情報技術者とは、経済産業省が行う国家資格「情報処理技術者試験」の区分の一つです。試験ではプログラマーやシステムエンジニアなどIT業界で働くために必要とされる基礎知識や情報処理において論理的な考え方ができるか等が問われ、企業から高い評価を獲ることができ、IT業界の入門的な資格として人気があります。

疑似言語の構文解析がわかりません。

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 1,185

remember

score 150

2005年秋期
普通の数式をスタックを使って後置表記法に変換するプログラムです。

<変換の優先度>
・(        …4
・0~9までの数字 …3
・×、÷       …2
・+、-      …1
・)        …0

スタックの底は制御文字「EOS」が入ります。優先度はー1です。
プログラムは以下の通りです。
---------------------------------------------------
・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の例として (2+4)×3+5×6 を取り上げてるんですが、トレースしていくとどうしても5番目の文字で止まってしまいます。回答の処理の流れを見てもいまいちわかりません。またコメントの「取り出した要素は使わない」というのもよくわからないというか、このプログラムの処理後の文字列は "(" と ")" が消えているので多分これのことを言っているんだろうなとはなんとなく思うのですが、トレースしていくと「???」となってしまいます。どなたか教えてください。
リンク内容
午後問題の14~18pです。

【トレース手順】
・最初の文字 "(" の処理
⇒ スタックの先頭文字 (EOS) の方が優先度が低い 
⇒スタックに "(" を格納
・2番目の文字 "2" の処理
⇒スタックの先頭文字の方が優先度が高いが "(" である
⇒スタックに "2" を格納
・3番目の文字 "+" の処理
⇒スタックの先頭文字の方が優先度が高い
⇒Postfix[0] に "2" を代入
⇒スタックに "+" を格納
・4番目の文字 "4" の処理
⇒スタックの先頭文字の方が優先度が低い
⇒スタックに "4" を格納
・5番目の文字 ")" の処理
⇒スタックの先頭文字の方が優先度が高い
⇒Postfix[1] に "4" を代入

ここでどうしても止まってしまいます。この時点で
Postfix     【24】
スタック   【+(EOS】
になっていますよね? 回答によるとこの次は
Postfix     【24+】
スタック   【(EOS】
になるということですが、pop() で "+" を取り出すにしてもそれをPostfixに代入する処理がないような…
あとこの ")" の処理が終わった後スタックは【EOS】だけになっているそうなのですが、いつのまにか "(" が消えています。これも一体何なのでしょうか。
イメージ説明
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • eripong

    2015/09/23 19:34

    トレースの過程を書いた方が、間違っている箇所が指摘できて良いと思います。

    キャンセル

  • remember

    2015/09/23 19:38

    なるほど。そうですね。

    キャンセル

回答 3

checkベストアンサー

0

・5番目の文字 ")" の処理 
⇒スタックの先頭文字の方が優先度が高い
  ⇒Postfix[1] に "4" を代入

このあと、

 ⇒スタックの先頭文字("+")の方が(")"より)優先度が高い
   ⇒Postfix[2] に "+" を代入

となると思います。

| ■getPriority(Exptext[i] <= getPriority(top()) and top() != "("
| |・Postfix[k] ← pop()
| |・k ← k + 1
| ■

の部分はループと思いますが、認識合っていますか?
また、スタックに残った"("はその後の
|    |  ・pop()        /* 取り出した要素は使わない */ 
で取り除かれます。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/09/23 21:05

    getPriority の処理はループでしたね…一回処理したら次の条件式にとんでました。基本的なミスですみません…ありがとうございます!

    キャンセル

0

出題は、中置記法((2+4)×3+5×6)を後置記法(24+3×56×+)に変換するプログラムについてですね。

後置記法には()を用いないので、適切に除去するプログラムが書かれています。





投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/09/23 18:44

    回答ありがとうございます…と言いたいところですがやっぱりわかりません…
    後置表記法は "(" と ")" は使わないことはわかるのですが、それを除去するプログラムが問題文には書かれていないような気がするのですが…
    質問に過去問のリンクを貼っておいたので見ていただけないでしょうか? すみません…

    キャンセル

  • 2015/09/23 20:07

    スタックExptextの最初の要素は"("で、優先順位4で最高です。
    getPriorityで始まるループは、始点の文字と等価か優先順位の高い文字列まで、スタックExptextから文字列を取り出し、Postfixに入れるようになっています。で、最初のケースでは")"迄です。

    で、次のIF条件ですが、
    ・")"でなければ、スタックExptextに戻す。
    ・")"であれば、更にスタックExptextから取り出す。(結果、")"は何もされずに破棄)
    という風になっています。

    キャンセル

  • 2015/09/23 21:06

    基本的な見落としをしていました。すみません…回答ありがとうございます!

    キャンセル

0

一言で「取り出す」と言っていますが,実際の処理は次の手順です.
  1.  スタックの一番上の要素を取得する
  2.  スタックの一番上を削除する
  3.  1.で取得した要素を返却する
ここで鍵になるのは「返却する」ということです.
どこに返却されるかというと,この場合pop()に返却されます.
ここで文字型の変数(例えばa)を用意して
a = pop()
とすれば使えますが,ここでは代入していないので,これ以降返却された値を使う術がなくなります.
そしてスタックからも2.によって削除されているので,結果的に除去されていることになるのです.

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/09/23 21:05

    ありがとうございます!

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.48%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • 基本情報技術者

    47questions

    基本情報技術者とは、経済産業省が行う国家資格「情報処理技術者試験」の区分の一つです。試験ではプログラマーやシステムエンジニアなどIT業界で働くために必要とされる基礎知識や情報処理において論理的な考え方ができるか等が問われ、企業から高い評価を獲ることができ、IT業界の入門的な資格として人気があります。