Оценка короткого замыкания RPN

Question

Я сейчас в середине создания простого интерпретатора байт-кода, который использует RPN для обозначения выражений и действительно постфиксной нотации для чего-либо, но теперь я пришел к вопросу, который есть: может ли оценка короткого замыкания на самом деле быть используется для постфиксных выражений? Например, при оценке выражения (false & & (factorial (7)> ​​factorial (5))) C++ знает, что оператор & & на двух операндах оценивает значение false до того, как он даже попадает во второй операнд, поскольку (false & & ничего) всегда равно false. Теперь, когда вы помещаете это в RPN, вы получаете (false (7 факториалов 5 факториалов>) & &).

Я хотел создать эффективный синтаксический анализатор выражения RPN, поэтому проблема заключается в следующем: как сделать эффективный парсер выражения RPN с оценкой короткого замыкания?

Answer 1

Вы бы оценили выражение RPN в две фазы.

Этап 1: проанализируйте RPN и создайте древовидное представление RPN. Итак, в этом дереве, например, узел && имеет два дочерних узла для каждой половины выражения. Построение этого дерева является почти идентичным процессом, как оценка RPN, за исключением оценочной части, которая заменяется операцией построения нового узла и связыванием ее дочерних узлов с их новым родительским узлом, а затем возвращением родительского узла на RPN оценка стек.

Этап 2. Оцените построенное дерево, используя рекурсивный спуск. На этом этапе оценка короткого замыкания становится тривиальной: оцените левого ребенка &&, а затем решите, действительно ли вы хотите оценить правого ребенка.

Ditto для || узла, и т.д. ...