Java를 사용하여 간단한 Lisp 식 계산기를 구현하려고합니다. 실제로 주제에 대한 풍부한 정보가 있지만, 모두 결과에 도달하기 위해 두 개의 별도 스택을 사용합니다. 하나의 스택을 사용하여 그런 프로그램을 구현할 수 있는지, 그리고 어떤 의사 코드가 어떻게 보이는지 궁금합니다.자바로 된 Lisp 식 계산기 (하나의 스택 만 사용)
감사합니다. 에 대한 추가 정보를 원하시면
제가
참조에 대해서 이야기하고 당신은 매우 중요한 가정을 만들기 위해 링크 된 통역 모두 : 그 +, - , * 등은 모두 이진 함수이므로 항상 두 개의 인수를 사용합니다. 실제 Lisp에서는 (+ 1 2 3 4 5)을 사용하여 많은 수의 수를 합산 할 수 있습니다. 그러나 각 연산자의 장점이 알려져 있다는 간소화 가정을 기꺼이 받아들이려는 경우 단 하나의 스택만으로이 작업을 수행 할 수 있습니다. 키 : 스택을 뒤집습니다.
는이 같은 스택이 연결된 통역 :
하단 ->(+ (- 2 1) 4) < - 상단은에서 뒤로 당신은 또한 당신의 표정에서 읽을 수, (우리는 밀어 여기에서 팝업)
을하지만, 오른쪽과 같이 스택을 구축 :
정상 -> < (+ (- 2 1) 4) - 하단
은 그럼 당신은 기본적으로 RPN을 얻을, 역 폴란드 표기법. RPN은 스택과 함께 정말 잘 실행됩니다.
알고리즘이 같다 :
예를 들어 (+ (- 2 1) 4)입니다. 여기 알고리즘이 작동 할 방법은 다음과 같습니다
스택 :빈읽기 :)작업 : 무시 괄호. 왼쪽 :(+ (- 2 1) 4
스택 :빈독서 :4작업 : 피연산자는 스택을 밀었다.왼쪽 :(+ (- 2 1)
스택 : 4 읽기 :)작업 : 괄호를 무시했다. 왼쪽 :(+ (- 2 1
스택 : 4 읽기 :1작업 : 피연산자 스택을 밀었다. 왼쪽 :(+ (- 2
스택 : 1~4 읽기 :2조치 : 오퍼랜드 스택으로 푸시. 왼쪽 :(+ (-
스택 : 2 1 4 읽기 :-작업 : 호출 연산자. 스택에서 2와 1을 꺼내고 2-1=1을 누릅니다. 왼쪽 :(+ (
스택 : 1 4 읽기 :(작업 : 괄호를 무시했다. 왼쪽 :(+
스택 : 1 4 읽기 :+작업 : 호출 연산자. 스택에서 1과 4가 나오면 1+4=5을 누릅니다. 왼쪽 :(
스택 : 5 읽기 :(작업 : 괄호를 무시했다. 왼쪽 :없음
완료! 결과는 예상대로 5입니다.
추신 : 괄호 무시. 당신이 입력하는 표현이 잘 형성되어 있다면 이것은 완벽하게 작동 할 것입니다. 그러나 형식이 좋지 않은 표현을 취할 수 있고 무의미한 가치를 부여 할 수 있습니다. 예 : (+ - + 1 2 3 4)은 (+ (- (+ 1 2) 3) 4)으로 해석됩니다. 이 동작을 방지하려면 닫는 괄호를 스택에 밀어 넣기 만하면됩니다. 연산자를 호출 할 시간이되면 인수를 빼고 여분의 토큰 하나를 더합니다. 토큰이 가까이 있는지 확인하십시오. 그렇지 않으면 오류가 발생합니다. 결과가 나오면 스택에 밀어 넣습니다. 읽은 다음 토큰이 열린 괄호인지 확인한 다음이를으로 버립니다.
PPS 진짜 Lisps 에서처럼 함수에 대한 인수 자체가 함수가 될 수 있다면이 모든 것이 훨씬 더 복잡해집니다.그런 다음 RPN이 의존하는 연산자/피연산자를 쉽게 구별 할 수 없으며 괄호에 그룹화 요소로 더 많은주의를 기울여야합니다. 가변성 (variable-arity)과 피연산자 (operand-as-operand)를 가진 단 하나의 스택을 가진 완전한 식의 Lisp 표현식 평가자를 수행 할 수 있는지 확실하지 않습니다.
희망 하시겠습니까? lisp style calculator with no stack