5

99プロローグ問題と呼ばれる素晴らしい問題セットがあります。問題P70はタイトルで言及されているものです。そしてここに、たった5行しかかからないこの問題の素晴らしいPrologソリューションがあります。ただし、Prologについての私の理解は限られています。

このソリューションは、Cのような形式（itertoolsは利用できません）ではどのように見えますか？

リクエストにより編集。私は著作権を侵害しないことを望みます。

問題：

BNFの構文：

tree ::= letter forest '^'
forest ::= | tree forest

差分リストを使用した優れたソリューション：

tree(TS,T) :- atom(TS), !, atom_chars(TS,TL), tree_d(TL-[ ],T). % (+,?)
tree(TS,T) :- nonvar(T), tree_d(TL-[ ],T), atom_chars(TS,TL).   % (?,+)
tree_d([X|F1]-T, t(X,F)) :- forest_d(F1-['^'|T],F).
forest_d(F-F,[ ]).
forest_d(F1-F3,[T|F]) :- tree_d(F1-F2,T), forest_d(F2-F3,F).
4

1 に答える 1

4

問題の定義

（P-99から引用：99のプロローグ問題）

多元ツリーのノードには単一の文字が含まれていると想定します。そのノードの深さ優先シーケンスでは^、ツリーの走査中に移動が前のレベルに戻るたびに、特殊文字が挿入されています。

この規則により、図のツリーは次のように表されます。afg^^c^bd^e^^^

代替テキスト
（出典：ti.bfh.ch）

文字列の構文を定義し、が指定されたときにtree(String,Tree)を構築するための述語を記述します。（文字列の代わりに）アトムを操作します。述語を両方向で機能させます。TreeString

ソリューションパート1：String2Tree

これはスタックで簡単です。擬似コードは次のとおりです。

FUNCTION String2Tree(String str) : Tree
   LET st BE New-Stack<Node>
   LET root BE New-Node
   st.push(root)

   FOREACH el IN str
      IF el IS '^'
         st.pop()
      ELSE
         LET child BE New-Node(el)
         LET top BE st.top()
         top.adopt(child)
         st.push(child)

   RETURN New-Tree(root)

ダミーrootノードを使用すると、問題が単純化されます。基本的に、アルゴリズムは次のとおりです。

  • 文字列を左から右にスキャンします
  • ノードラベルに遭遇するたびに、新しいノードを作成します
    • そのノードはスタックの最上位に採用されます
    • 次に、そのノードはスタックにプッシュされ、新しいトップになります
  • に遭遇する'^'と、スタックの一番上から飛び出します。

ソリューションパート2：Tree2String

反対方向は単純な再帰の問題です。

FUNCTION string(Tree t) : String
   LET sb BE New-StringBuffer

   visit(t.root, sb)

   RETURN New-String(sb)

PROCEDURE visit(Node n, StringBuffer sb)
   sb.append(n.label)

   FOREACH child IN n.children()
      visit(child, sb)

   sb.append('^')

^問題で指定されているように、前のレベルに戻るたびに挿入します。

于 2010-07-28T10:17:19.147 に答える