Shunting Yard 알고리즘의 역전은 무엇입니까?
문제
데이크스트라의 션팅 야드 알고리즘 중위 표기법을 구문 분석하고 생성하는 데 사용됩니다. RPN 산출.
나는 그 반대, 즉 일반 사용자가 이해할 수 있는 방식으로 데이터베이스의 RPN 표현식을 표현하기 위해 RPN을 고등학교 수학 수업 스타일 중위 표기법으로 바꾸는 방법을 찾고 있습니다.
시간을 절약하고 알고리즘을 직접 조작하지 말고, 제가 찾을 수 없는 교과서 예제를 알려 주시기 바랍니다.Shunting Yard 알고리즘에서 거꾸로 작업하고 표기법에 대한 지식을 사용하면 아마도 해결책을 찾을 수 있을 것입니다.나는 단지 빠른 지름길을 찾고 있을 뿐이므로, 바퀴를 다시 만들 필요가 없습니다.
아, 그리고 이것을 '숙제'라고 태그하지 마세요. 욕을 하다 난 벌써 학교를 떠났어!;-)
해결책
RPN은 후위 표기법(postfix notation)으로도 알려져 있기 때문에 구글링을 해보았습니다. "후위를 중위로" 변환 꽤 많은 결과를 얻었습니다.처음 몇 개에는 코드 예제가 있지만 RubyQuiz 항목 특히 깨달음.
다른 팁
중복된 괄호 제거에 대해 걱정하지 않는다면 다음 Lisp 코드가 작동합니다.
(defun rpn-to-inf (pre)
(if (atom pre)
pre
(cond ((eq (car (last pre)) 'setf)
(list (rpn-to-inf (first pre)) '= (rpn-to-inf (second pre))))
((eq (car (last pre)) 'expt)
(list (rpn-to-inf (first pre)) '^ (rpn-to-inf (second pre))))
(t (list (rpn-to-inf (first pre))
(car (last pre))
(rpn-to-inf (second pre)))))))
제휴하지 않습니다 StackOverflow