모든 RPN 표현식을 모든 연산자가 왼쪽에 나타나고 모든 피연산자가 오른쪽에 나타나도록 표현할 수 있습니까?

Question

나는 그들이 할 수 없다고 스스로 확신했습니다.

예를 들면 다음과 같습니다.

4 4 + 4 /

스택:4 스택 :4 4 4 + 4 = 8 스택 :8 스택 :8 4 8 / 4 = 2 스택 :2

피연산자가 모두 먼저 오도록 동일한 연산자와 피연산자로 위의 표현식을 쓸 수있는 두 가지 방법이 있습니다."4 4 4 + /"및 "4 4 4 / +", 그 중 어느 것도 평가하지 않습니다.

"4 4 4 + /"스택 :4 스택 :4 4 스택 :4 4 4 4 + 4 = 8 스택 :4 8 4 / 8 = 0.5 스택 :0.5

"4 4 4 / +"스택 :4 스택 :4 4 스택 :4 4 4 4 / 4 = 1 스택 :4 1 4 + 1 = 5 스택 :5

스택에 있는 항목을 교환할 수 있는 능력이 있다면 가능합니다. 그렇지 않으면 불가능합니다.

생각?

Answer 1

대수적 표현을 고려하십시오.

(a + b) * (c + d)

RPN으로의 명확한 번역은 다음과 같습니다.

a b + c d + *

스왑 작업이 가능하더라도 오른쪽에 있는 모든 연산자를 수집할 수 있는 방법은 없다고 생각합니다.

a b c d +
a b S

여기서 S는 c와 d의 합입니다.이 시점에서는 단일 스왑 작업을 사용하여 + 작업을 위해 a와 b를 모두 제 위치에 가져올 수 없습니다.대신 a와 b를 올바른 위치에 가져오려면 보다 정교한 스택 작업(예: 롤)이 필요합니다.모든 경우에 롤 작업이 충분한지 여부도 모르겠습니다.

Answer 2

실제로 귀하는 제목에 암시된 가정을 반증하기에 충분한 반례를 검토하여 답을 제시했을 뿐만 아니라 결정적인 증거도 제시했습니다.

Answer 3

나는 이것이 매우 오래된 스레드라는 것을 알고 있지만 오늘 그것을 발견했고 원래 질문에 대한 대답은 '예'라고 믿고 싶다고 말하고 싶었습니다.나는 모든 RPN 표현식이 모든 연산자가 왼쪽에 나타나고 모든 피연산자가 오른쪽에 나타나도록 표현될 수 있다고 확신합니다. 만약 일반적인 산술 연산 외에 세 개의 추가 '탐색' 연산자를 표현에 포함할 수 있습니다.

모든 산술 표현식은 리프 노드에 변수와 상수가 있고, 트리 분기에 이진 산술 연산이 있고, 분기를 따라 부정, 역수, 제곱근과 같은 단항 연산이 있는 이진 트리로 표현될 수 있습니다.내가 제안하는 세 가지 추가 작업은 왼쪽 가지 만들기, 오른쪽 가지 만들기 또는 이진 트리의 리프 노드에 도달하는 것을 나타냅니다.이제 모든 피연산자를 트리의 각 리프 위치에 따라 입력 문자열의 왼쪽에 배치하면 입력 문자열의 나머지 부분에 메모리에서 적절한 이진 트리를 재구성하고 삽입하는 방법을 알려주는 연산을 제공할 수 있습니다. 피연산자와 수학적 연산을 올바른 지점에 삽입합니다.마지막으로 깊이 우선 트리 순회 알고리즘이 적용되어 결과를 계산합니다.

이것이 실제 적용이 되는지 모르겠습니다.표현을 인코딩하고 디코딩하는 방법으로는 아마도 너무 비효율적일 것입니다.그러나 학술적인 연습으로서는 그것이 실행 가능하다고 확신합니다.

Answer 4

이에 대한 답을 말해주기 위해서는 할 수 없는 것을 보여주는 것만으로도 충분하다.

스택 내용을 다시 정렬할 수 없으면 식 (2+4)*(7+8)을 다시 정렬할 수 없습니다.

2 4 + 7 8 + *

어떻게 순서를 바꾸든 계속하기 전에 요약해야 할 내용이 남게 됩니다.

적어도 나는 그렇다고 믿는다.