역방향 폴란드어 표기법 이해, 숙제 지정?

Question

나는 C에서 숙제 과제의 일부로 간단한 역 폴란드어 표기법 계산기를 쓸 것을 요청 받았다. RPN을 이해하는 데 어려움이 있습니다. 역 폴란드어 표기법을 이해하도록 도와 주시겠습니까? 또한이 문제에 접근하는 방법에 대한 모든 정보를 크게 높이 평가할 수 있습니다.

Answer 1

당신은 http://www.codeproject.com/KB/cs/Reverse_Polish_Notation.aspx

Answer 2

Reverse Polish Notation에서 튜토리얼을 찾을 수있는 것은 당신이 값을 기록 첫째 쓰기 식의 특정 방법, 다음 작업은 당신이 수행 할. 예를 들어 숫자 3과 4를 추가하려면 3 4 +을 작성하십시오.

그래서 당신은

• 같은 콘솔에서와 같이 입력을 수신하는 수단이 필요합니다 RPN 계산기를 작성하는
• 당신이 파괴, 무슨 일을하는지에 대한 tokenizing 입력 (의 수단 공백이) 기재
3 등
• 값 (피연산자를 저장하는 stack) (4)의 조작
• 사전 적 충분할

그런 다음 루프는 본질적으로된다 :

while (there's a token available) { 
    token = get_the_token 
    if (token is known operator) { 
     get the number of values from stack this operation requires (usually two); fail if stack doesn't have enough 
     perform operation on values 
     push result on the stack 
    } 
    else if (token is valid value) { 
     push it on the stack 
    } 
    else { 
     show error: invalid input 
    } 
} 
show result remaining on stack 

당신은 RPN 상당히 쉽게 calcuator를 작성하게 이유를 볼 수 있습니다 당신은 그들이에서 운영하는 값 사이의 통신을 문제에 대해 걱정할 필요가 없습니다, 당신 돈 더 일반적인 infix 표기법을 사용하는 것처럼 그룹화를 위해 괄호가 필요하지 않습니다. 예를 들어 (10 + (4 * 2))/9을 중침 표기법으로 작성하면 10 4 2 * + 9 /을 RPN으로 작성합니다. 그것은 값의 스택에

2를 밀어 : 스택에

4를 밀어, 그것은 값입니다 :

• 10 : 귀하의 계산기는 그 같은 토큰을 처리 할 것입니다 그것은 값, 푸시입니다 그것 스택에
• * : 그것은 연산자, 팝업 2와 4 스택에서 해제하고 (4 * 2); 결과 (8) 스택에 밀어 넣으십시오.
• + : 운영자이고, 스택에서 8 및 10 번 팝하고 추가하십시오 (10 + 8); (18/9)를 또한 스택에서 조작자 팝 (9) 및 (18) 그리고 그들 나눈다 : 그것은 치의
• / 스택에 푸시 :
• 9 스택 결과 (18)를 밀어 스택 결과 (2)를 밀어
• (이 경우   —에서 스택   — (9)의 상단의 값은 제수 그것을   — 18   — 하에서 다음 값임을 배당되는 주) 입력 단부는 스택의 값 (들)을 보여 2

Answer 3

Reverse Polish Notation는 운영자 피연산자 따라 수학 식 표기법의 한 형태이다.RPN 표현식을 평가할 때 각 2 진수 연산자는 바로 앞에있는 두 개의 피연산자을 참조합니다. 예를 들어이 RPN 식을 가지고 : 당신이 + 첫 번째 연산자에 올 때까지

5 4 3 + * 

시작 왼쪽에서 식을 스캔. 이 연산자에는 피연산자 4과 3 (바로 앞에 오는 피연산자)이 있으므로 3 개를 모두 7으로 바꿀 수 있습니다. (괄호는 필요하지 않지만 의미를 명확히하는 데 사용합니다).

5 (4 3 +) * => 5 7 * 

는 이제 오퍼레이터 * 및 (실제로 4 + 3의 결과이다) 두 피연산자 5 및 7있다. 5과 7을 곱하면 전체 표현식은 35이됩니다.

5 7 * => 35 

이것은 RPN 표현식을 평가하기위한 일반적인 알고리즘입니다.

---

RPN 표현식은 stack으로 알려진 데이터 구조를 사용하는 컴퓨터에 의해 evaulation에 특히 적합하다.

스택은 순서가 지정된 컬렉션이며 한 쪽 끝이 "위쪽"으로 지정됩니다. 항목은 항상 스택에 추가되거나 맨 위에있는 스택에서 제거됩니다. 이렇게하면 제거 할 유일한 항목은 항상 가장 최근에 추가 된 항목입니다. 이러한 이유 때문에, 스택은 스택에 푸시 된 마지막 요소가 맨 위에 있으므로 제거해야 할 첫 번째 요소가되므로 Last In, First Out (또는 LIFO)이라고도합니다.

C에서는 두 개의 변수를 갖는 스택을 구현할 수 있습니다 : 배열 (스택이 필요로하는 최대 요소 수를 저장할만큼 충분히 큼)과 배열의 어느 인덱스가 현재 최상위인지 나타내는 정수 .

스택은 연산자를 만나면 항상 최근에 발생한 피연산자에 적용되므로 RPN 표현식을 평가하는 데 적합합니다. 따라서 왼쪽에서 표현식을 스캔하면 피연산자를 스택에 저장할 수 있습니다. (빈 처음 인)

5 4 3 + * 

여기에 제일 먼저 피연산자 (5), 그래서 스택으로 푸시 : 다시 우리의 예를보십시오. 그런 다음 4을 만나 스택에도 밀어 넣습니다. 그것은 새로운 최고가됩니다. 그런 다음 3과 동일하게 처리합니다.

5 4 3 <-- top 
+ * // Remaining expression 

다음으로 우리는 + 연산자를 접하게됩니다. 이전에 발생한 피연산자에 적용된다는 것을 알고 있지만 어디에서 찾을 수 있습니까? 스택 맨 위에 물론! 스택에서 3 및 4을 가져 와서 7이되도록 추가하십시오. 그러나 그 결과로 무엇을 할 것인가? 음, 다른 연산자 피연산자가 될 수 있으므로 (우리가 손으로 표현 평가 때 우리는 결과 피연산자와 연산자를 대체처럼) 스택에 다시 밀어 :

5 7 <-- top 
* // Remaining expression 

이제 우리는 * 참조 . 다시 한 번 가장 최근에 발생한 피연산자는 스택의 두 개의 최상위 피연산자입니다. 우리는 그들을 팝업하고 35을 얻기 위해 번식 한 다음 스택에 다시 밀어 넣습니다.

35 <-- top 
// No expression remaining 

이 시점에서 우리는 표현식의 끝 부분에 도달했으며 스택의 유일한 결과가 나타납니다. 우리는 끝났다! 표현식의 다른 끝에있을 수있는 해당 연산자가 발생할 때까지 피연산자가 마주 치게되는 첫 번째 피연산자를 "저장"하는 방법을 볼 수 있습니다.

끝에 도달하여 스택에 둘 이상의 숫자가 남아 있으면 연산자에 연산자가 너무 많고 표현식에 피연산자가 너무 많았다 고 말했을 것입니다. 반면에 어떤 점에서 연산자를 만나 스택에 피연산자가 두 개 미만인 경우 표현식에 연산자가 너무 많고 피연산자가 충분하지 않다는 것을 알 수 있습니다.

Answer 4

당신은 http://expressionoasis.vedantatree.com/