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 个操作数（和一个运算符）
   和
   算法适用于 3 个操作数（和 2 个运算符）
  ==> 那将是你的基本情况

2) 如果算法适用于 n 个操作数（和 n-1 个运算符）
  那么它必须适用于 n+1 个操作数。
  ==> 这将是证明的归纳部分

祝你好运 ;-）

请注意数学证明，以及它们有时令人困惑的名称。在归纳证明的情况下，有时仍期望通过演绎逻辑“弄清楚”某些东西（某些事实或某些规则），但是这些事实和规则放在一起构成了更广泛的真理，购买归纳；那就是：因为基本情况被确定为真，并且因为有人证明如果 X 对于“n”情况为真，那么 X 对于“n+1”情况也为真，那么我们不需要尝试每个情况，可能是一个很大的数字，甚至是无限的）

Back on the stack-based expression evaluator... One final hint (in addtion to Captain Segfault's excellent explanation you're gonna feel over informed...).

The RPN expressions are  such that:
  - they have one fewer operator than operand
  - they never provide an operator when the stack has fewer than 2 operands 
    in it (if they didn;t this would be the equivalent of an unbalanced 
    parenthesis situation in a plain expression, i.e. a invalid expression).

Assuming that the expression is valid (and hence doesn't provide too many operators too soon), the order in which the operand/operators are fed into the algorithm do not matter; they always leave the system in a stable situtation: - either with one extra operand on the stack (but the knowledge that one extra operand will eventually come) or - with one fewer operand on the stack (but the knowledge that the number of operands still to come is also one less).

So the order doesn't matter.

于 2009-09-22T22:23:07.173 回答
0

You know what induction is? Do you generally see how the algorithm works? (even if you can't prove it yet?)

Your induction hypothesis should say that, after processing the N'th character, the stack is "correct". A "correct" stack for a full RPN expression has just one element (the answer). For a partial RPN expression the stack has several elements.

Your proof is then to think of this algorithm (minus the result = pop from stack line) as a parser that turns partial RPN expressions into stacks, and prove that it turns them into the correct stacks.

It might help to look at your definition of an RPN expression and work backwards from it.

于 2009-09-22T23:55:09.540 回答