프로그램이 무언가를하는 것을 유도하여 증명하는 방법?

StackOverflow https://stackoverflow.com/questions/1462843

문제

오페라와 연산자가 PostFix 표기법으로 작성된 숯불 배열로 읽는 컴퓨터 프로그램이 있습니다. 그런 다음 프로그램은 그림과 같이 스택을 사용하여 결과를 검사합니다.

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))

도움이 되었습니까?

해결책

알고리즘에 대해 어떤 표현을 증명 해야하는지 잘 모르겠습니다. 그러나 전형적인 RPN 표현식처럼 보이면 다음과 같은 것을 설정해야합니다.

1) algoritm works for 2 operands (and one operator)
   and 
   algorithm works for 3 operands (and 2 operators)
  ==> that would be your base case

2) if algorithm works for n operands (and n-1 operators)
  then it would have to work for n+1 operands.
  ==> that would be the inductive part of the proof

행운을 빕니다 ;-)

수학적 증거와 때로는 혼란스러운 이름에 관한 마음을 취하십시오. An의 경우 유도 성 증거는 여전히 무언가 (일부 사실 또는 규칙)를 "알아 내"할 것으로 예상됩니다. 연역적 논리, 그러나 이러한 사실과 규칙이 합쳐진 것은 더 넓은 진실을 구성합니다. 즉, 기본 사례가 참으로 확립되었고 "N"케이스에 대해 X가 참이면 "N+1"케이스에 대해서도 X가 사실이라는 것을 증명했기 때문에 모든 것을 시도 할 필요는 없습니다. 큰 숫자가 될 수 있거나 심지어 무한한 경우)

스택 기반 표현식 평가자로 돌아 가기 ... 하나의 최종 힌트 (세그 파트 대위의 훌륭한 설명에 대한 추가 정보를 추가로 느낄 것입니다 ...).

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).

표현이 유효하다고 가정하고 (따라서 너무 많은 연산자를 너무 빨리 제공하지 않음), 오페라/연산자가 알고리즘에 공급되는 순서는 중요하지 않습니다. 그들은 항상 시스템을 안정적인 앉은 상태로 남겨 둡니다 .- 스택에 하나의 여분의 피연산자 (그러나 하나의 여분의 피연산자가 올 것이라는 지식) 또는 스택에 피연산자가 적은 것 (그러나 피연산자 수는 여전히 여전히 지식이 있습니다. 앞으로 나올 것도 덜)).

따라서 주문은 중요하지 않습니다.

다른 팁

유도가 무엇인지 알고 있습니까? 일반적으로 알고리즘이 어떻게 작동하는지 보십니까? (아직 증명할 수 없더라도?)

당신의 유도 가설은 N'TH 캐릭터를 처리 한 후 스택이 "정확하다"고 말해야합니다. 전체 RPN 표현식을위한 "올바른"스택에는 하나의 요소가 있습니다 (답변). 부분 RPN 표현식의 경우 스택에는 몇 가지 요소가 있습니다.

그런 다음 증거는이 알고리즘 (결과를 빼고 스택 라인에서 팝)을 회전하는 구식으로 생각하는 것입니다. 부분적 RPN 표현식은 스택으로 표현되어 올바른 스택으로 바꾸 었다는 것을 증명합니다.

RPN 표현식의 정의를보고 뒤로 작업하는 데 도움이 될 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top