1

私は、オペランドと演算子が後置表記で書かれた文字の配列を読み取るコンピュータープログラムを持っています。次に、プログラムは配列をスキャンして、次のようにスタックを使用して結果を計算します。

get next char in array until there are no more
if char is operand
    push operand into stack
if char is operator 
    a = pop from stack
    b = pop from stack
    perform operation using a and b as arguments
    push result
result = pop from stack

このプログラムが後置式を正しく評価することを帰納法によって証明するにはどうすればよいですか? (演習 4.16 Java のアルゴリズム (Sedgewick 2003) から取得)

4

2 に答える 2

5

アルゴリズムを証明するために必要な式がわかりません。しかし、それらが典型的な RPN 式のように見える場合は、次のようなものを確立する必要があります。

1) アルゴリズムは 2 つのオペランド (および 1 つの演算子) に対して機能します。
   と
   アルゴリズムは 3 つのオペランド (および 2 つの演算子) に対して機能します
  ==>それがあなたの基本ケースになります

2) アルゴリズムが n 個のオペランド (および n-1 個の演算子) に対して機能する場合
  次に、n + 1オペランドで機能する必要があります。
  ==> それは証明の帰納的な部分です

幸運を ;-）

数学的証明と、それらの紛らわしい名前にも気をつけてください。帰納的証明の場合でも、演繹的な論理によって、何か (何らかの事実または何らかの規則) を「理解する」ことが期待されますが、これらの事実と規則を組み合わせると、より広範な真実が構成されます。つまり、基本ケースが真であると確立されており、X が "n" ケースで真である場合、X は "n+1" ケースでも真であることが証明されているため、すべてを試す必要はありません。場合によっては、大きな数または無限の可能性さえあります)

スタックベースの式エバリュエーターに戻ります... 最後のヒント (セグフォールト船長の優れた説明に加えて、あなたは情報過多に感じるでしょう...)。

RPN 式は次のようになります。
  - オペランドより演算子が 1 つ少ない
  - スタックのオペランドが 2 つ未満の場合、演算子は提供されません。
    その中に（もしそうでなければ、これは不均衡な
    単純な式の括弧の状況、つまり無効な式)。

式が有効である (したがって、すぐに多くの演算子を提供しない) と仮定すると、オペランド/演算子がアルゴリズムに供給される順序は重要ではありません。それらは常に安定した状況でシステムを離れます。来るのも1つ少ない）。

なので順番は関係ありません。

于 2009-09-22T22:23:07.173 に答える
0

誘導って知ってる？アルゴリズムがどのように機能するか、おおむね理解できていますか? （まだ証明できなくても？）

あなたの誘導仮説は、N 番目の文字を処理した後、スタックが「正しい」と言うはずです。完全な RPN 式の「正しい」スタックには、1 つの要素 (答え) しかありません。部分 RPN 式の場合、スタックにはいくつかの要素があります。

次に、このアルゴリズム (結果 = スタック行からのポップを除く) を、部分的なRPN 式をスタックに変換するパーサーと考え、それがそれらを正しいスタックに変換することを証明します。

RPN 式の定義を調べて、そこからさかのぼって作業すると役立つ場合があります。

于 2009-09-22T23:55:09.540 に答える