표현식 평가 - StackOverflow 예외 방지

Question

나는 내 자신의 표현식 평가자를 구성하기 위해 주변을 둘러 보았고이 문제에 대해 궁금해합니다.

문자열 식을 평가하는 두 가지 방법을 사용했습니다. 한 가지 방법은 이진 트리를 사용합니다.

(약) 42000보다 긴 표현식 문자열을 입력하면 stackoverflow 예외가 발생합니다. 난이 기능 (내 두 번째 구현)

지금 내가 이진 트리 방법을 고수하는 것을 선호와 (심지어 많은 이상 길이) 같은 표현 문자열을 평가하는 경우

그러나 같은 발생하지 않습니다 - 스택 오버 플로우 예외를 해결할 수있는 방법이 있습니까? 즉 재귀에서 스택 오버플로를 피할 수 있습니까? 아니면 스택이 실제로 오버플로 할 때를 찾는 방법이 있습니까? 그렇지 않다면, 실제로는 적어도은 스택 오버 플로우가 발생할 수 있다는 평가를 받기 전에 사용자에게 경고 할 수 있습니까?

Answer 1

솔직히 최선의 방법은 두 번째 방법을 사용하는 것입니다. 여기에서 재귀를 사용할 수는 있지만 알고리듬 관점에서 보면 제공 한 스택 메소드가 더 정확합니다 - 주로 이진 트리 메소드가 단항 연산자를 처리 할 방법이 없기 때문에 (적어도 제가 말할 수있는 한) (예 : ++ i).

첫 번째 질문에 대해서는 실제로 입력에서 스택 오버플로 예외가 발생하는지 알 수있는 방법이 없습니다. 가장 좋은 방법은 try/catch에서 재귀 메서드로 첫 번째 호출을 래핑하고 명시 적으로 StackOverflowException을 catch 한 다음 유효한 오류 메시지를 반환하는 것입니다.

또한 원하는 경우 이론적으로 숫자 2와 비슷한 스택 개체를 사용하도록 이진 트리 구현을 이동할 수 있습니다. 애플리케이션 스택 대신 스택을 사용하는 방법을 다시 설계해야하지만