投稿する

大原本  問77 [5392]

 まきさん(No.1) 
前回同様にプログラムを入れました
逆ポーランドなので、例えば
後置記法→中置記法
abc++→(a+(b+c))
というのは分かるのですが、実際のトレースをどうしたらいいのか不明です
op1とop2に文字を入れてop2&op1の文字列を作るのは分かります。
(2)、(3)は何故こうなるのかが分かりません。すみませんが解説をお願い致します。

文字列の配列:postfixtoinfix(文字列の配列:exp)
文字列の二次元配列:stack
文字列の配列:op1,op2,infix
整数型:i,sp←0
for(i,1~expの長さ,1)
if(isoprand(exp[i]=true))(1)
sp←sp+1(2)
strcpy(stack[sp],exp[i])
else
strcpy(op1,stack[sp])
sp←sp-1(3)
strcpy(op2,stack[sp])
strcpy(stack[sp],"("&op2&exp[i]&op1&"))
endif
endfor
strcpy(infix,stack[sp])
return,infix

○論理型:isoprand(文字型:x)
return not((x="+")or(x="-")or(x="*")or(x="/")
2024.04.09 21:06
電タックさん(No.2) 
FE ブロンズマイスター
見当違いであればスルーしてください。

>(2)、(3)は何故こうなるのかが分かりません
どこが悩みポイントなのかいまいち読み取れなかったので、配列でスタックの構造を作るのがわからないということなのでしょうか?

配列はインデックスさえ指定すれば基本的にどの場所にもアクセス可能です
ですが
設問ではスタックの構造としてspのインデックスしかアクセスできないようにプログラムしています。

スタックはご存知とは思いますがLIFOのアクセスとなっておりアクセスポイントは最上部(push or popともに)の1点のみです。
なので
新しく入れる(push)時にはスタックのポイント(sp)を上げ、取り出す(pop)時にはスタックのポイント(sp)を下げる必要があります。
2024.04.10 12:57
 まきさん(No.3) 
>電タックさん
>どこが悩みポイントなのかいまいち読み取れなかったので、配列でスタックの構造を作るのがわからないということなのでしょうか?

このプログラムだけを見てスタックの構造のイメージが出来ない
スタックなら具体的な絵とかあるなら分かるのですがすみません
2024.04.10 18:16
 まきさん(No.4) 
">電タックさん"

素直に言うとスタックは分かっていますがプログラムは、
これ見て何やっているのっていうレベルなんです

整数型:i,sp←0
for(i,1~expの長さ,1)
if(isoprand(exp[i]=true))(1)
sp←sp+1(2)
strcpy(stack[sp],exp[i])
else
strcpy(op1,stack[sp])
sp←sp-1(3)
strcpy(op2,stack[sp])
strcpy(stack[sp],"("&op2&exp[i]&op1&"))
endif
endfor
strcpy(infix,stack[sp])
return,infix
2024.04.10 18:54
 まきさん(No.5) 

    
stack[sp]   1 2 3 4 5
            a b c + +

    1 2 3 4 5
op1 c +
op2 b a

1回目  op2&op1
(b+c) (op1)
2回目  op2&op1
a+  (op2)
3回目  op2&op1
(a+(b+c))

私なりの理解でこんな感じでしょうかと思いますが、あんまり理解出来てないです
2024.04.10 19:46
電タックさん(No.6) 
FE ブロンズマイスター
一気にプログラムを読むとわかりにくいかもしれないので分割して考えるのがいいと思います。
※これは私がプログラムを読む場合にしていることなので一般ではないかもしれません。

今回のプログラムであれば
for(i,1~expの長さ,1)
if(isoprand(exp[i]))
  A
else
  B
endif
endfor

とした上でBの部分を消してどう動くのか?をみると
設問の{"a", "b", "c", "+", "+"}や、{"a", "b", "c", "d"}とシンプルにしたものにしてAの動作を観察します。

結果
stackに{"a", "b", "c"}となってsp=3

stackに{"a", "b", "c", "d"}となってsp=4
となりstackに英字が溜まっていくことがわかります。

Aの動作がわかったのであれば今度はBの動作を見ればいいのでという風に
段階的に読んでいくのが良いと思いました。

ちなみにBには英字以外の場合だけが行くので"+"の2回分実行され
実施前
stack{"a", "b", "c"}
sp=3
1回目
op1="c" // sp=3
op2="b" // sp=2
exp[i]="+"
結果stack{"a", "(b+c)"}
2回目
op1="(b+c)" // sp=2
op2="a" // sp=1
exp[i]="+"
結果stack{"(a+(b+c))"}

となっていると思います。
2024.04.10 20:52
jjon-comさん(No.7) 
FE ゴールドマイスター
この投稿は投稿者により削除されました。(2024.04.11 00:06)
2024.04.11 00:06
jjon-comさん(No.8) 
FE ゴールドマイスター
operand(オペランド)は「被演算子、演算対象」という意味の英単語。
以下では「変数」と表現することにします。
ちなみに反対概念は operator(オペレータ)「演算子」です。

postfix_to_infix…後置き記法(ab+)を中置き記法(a+b)へ
is_operand…変数か? 変数ならばtrue、演算子ならfalse
exp…式(expression)

▼'a'は変数なのでスタックにpush
if(isoprand('a')=true)
+―+
|a|sp=1
+―+

▼'b'は変数なのでスタックにpush
if(isoprand('b')=true)
+―+
|b|sp=2
+―+
|a|
+―+

▼'c'は変数なのでスタックにpush
if(isoprand('c')=true)
+―+
|c|sp=3
+―+
|b|
+―+
|a|
+―+

▼'+'は変数でないので(演算子なので)スタックから2つpopして文字列結合してpush
if(isoprand('+')=true)
else
strcpy(op1,stack[sp])
sp←sp-1
strcpy(op2,stack[sp])
strcpy(stack[sp],"("&op2&exp[i]&op1&")")
+―――――+
|(b+c)|sp=2
+―――――+
|    a    |
+―――――+

▼'+'は変数でないので(演算子なので)スタックから2つpopして文字列結合してpush
if(isoprand('+')=true)
else
strcpy(op1,stack[sp])
sp←sp-1
strcpy(op2,stack[sp])
strcpy(stack[sp],"("&op2&exp[i]&op1&")")
+―――――――――+
|(a+(b+c))|sp=1
+―――――――――+

▼"(a+(b+c))"を中置き記法の文字列として戻り値とする
strcpy(infix,stack[sp])
return infix
2024.04.11 00:09
 まきさん(No.9) 
>皆様大変分かりやすい解説をありがとうございます。
視覚的に書いてくれると嬉しいです
2024.04.11 19:56
返信投稿用フォームスパム防止のためにスレッド作成日から30日経過したスレッドへの投稿はできません。
© 2010- 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop