Оценка экспрессии - исключение исключения StackOverflow

Question

Я занимался поиском собственного оценщика выражений и приземлился на эту проблему, мне интересно.

Я использовал 2 способа оценки строкового выражения. Один метод использует двоичное дерево.

Когда я ввожу строку выражения длиной более (приблизительно) 42000, я получаю исключение stackoverflow.

Однако то же самое не произойдет, если я оценивать ту же выражение строку (даже в много большей длины) с этой функцией (моя вторая реализация)

Теперь я предпочел бы придерживаться метода двоичного дерева - есть способ, которым я могу исправить исключение переполнения стека, т.е. я могу избежать переполнения стека в рекурсии или есть способ найти, когда стек будет фактически переполняться? Если нет, то как я могу на самом деле как минимум предупредить пользователя, прежде чем даже выражение начнет оцениваться, что может произойти переполнение стека?

Answer 1

Честно говоря, лучше всего использовать второй метод. Хотя рекурсия применима здесь, с точки зрения алгоритма, метод стека, который вы предоставили, является более правильным - главным образом, потому что ваш метод двоичного дерева не имеет способа справиться с унарными операторами (насколько я могу судить, по крайней мере) (например, ++ i).

Что касается вашего первого вопроса, на самом деле нет способа сказать, что что-то выкинет исключение переполнения стека только из ввода. Лучше всего было бы просто перенести первый вызов рекурсивного метода в try/catch и явно поймать StackOverflowException и вернуть правильное сообщение об ошибке пользователю.

Также имейте в виду, что теоретически можно было бы переместить реализацию двоичного дерева, чтобы использовать объект стека, аналогичный номеру 2, если хотите. Хотя вам все равно придется перепроектировать метод, чтобы использовать ваш стек вместо стека приложения.