Оценка короткого замыкания RPN
Сейчас я нахожусь в процессе создания простого интерпретатора байт-кода, который использует RPN для нотации выражений и действительно постфиксную нотацию для чего-либо, но теперь я пришел к вопросу: может ли оценка короткого замыкания фактически использоваться в выражениях postfix? Например, при оценке выражения (ложь && (factorial (7)> factorial (5))) C ++ знает результат && Оператор с двумя операндами оценивается как ложное до того, как оно попадает во второй операнд, поскольку (ложно && что угодно) всегда равно false. Теперь, когда вы помещаете это в RPN, вы получаете (false (7 факториал 5 факториал>) &&).
Я хотел создать эффективный синтаксический анализатор выражений RPN, поэтому проблема заключается в следующем: как создать эффективный анализатор выражений RPN с оценкой короткого замыкания?
Решение
Вы бы оценили RPN Выражение в два этапа.
Этап 1: разобрать RPNи построить древовидное представление RPN. Так, в этом дереве, например, && узел имеет два дочерних узла для каждой половины выражения. Построение этого дерева является почти идентичным процессом оценки RPNза исключением вычисляющей части, которая заменяется операцией создания нового узла и связывания его дочерних узлов с их новым родительским узлом, а затем отодвигает родительский узел обратно на RPN стек оценки.
Этап 2: оценка построенного дерева с использованием рекурсивного спуска. На этом этапе оценка короткого замыкания становится тривиальной: оцените левого потомка &&затем решите, действительно ли вы хотите оценить правого ребенка.
То же самое для || узел и т.д …
Другие решения
Других решений пока нет …