Преобразование обратной польской записи

Question

Есть ли способ интерпретации обратной польской записи в «нормальную» математическую запись при использовании C ++ или C #? Я работаю в инженерной фирме, поэтому они время от времени используют RPN, и нам нужен способ его конвертировать. Есть предложения?

Answer 1

Да. Подумайте, как работает калькулятор RPN. Теперь вместо вычисления значения вы добавляете операцию в дерево. Так, например, 2 3 4 + *, когда вы добираетесь до +, тогда вместо помещения 7 в стек вы помещаете (+ 3 4) в стек. И точно так же, когда вы доберетесь до * (ваш стек будет выглядеть как 2 (+ 3 4) * на этом этапе), он станет (* 2 (+ 3 4)).

Это префиксная нотация, которую затем нужно преобразовать в инфикс. Пройдите дерево слева направо, сначала на глубину. Для каждого «внутреннего уровня», если приоритет оператора ниже, вам придется поместить операцию в скобки. Здесь, затем, вы скажете, 2 * (3 + 4), потому что + имеет более низкий приоритет, чем *.

Надеюсь, это поможет!

Редактировать: Есть тонкость (не считая унарных операций в приведенном выше): я предположил левоассоциативные операторы. Для правоассоциативного (например, **) вы получите разные результаты для 2 3 4 ** ** ⇒ (** 2 (** 3 4)) против 2 3 ** 4 ** ⇒ (** (** 2 3) 4).

При восстановлении инфикса из дерева оба случая показывают, что для приоритета не требуется заключать в скобки, но в действительности последний случай должен заключаться в квадратные скобки ((2 ** 3) ** 4). Таким образом, для правоассоциативных операторов левая ветвь должна иметь более высокий приоритет (а не более или равно), чтобы избежать заключения в скобки.

Кроме того, дальнейшие мысли заключаются в том, что вам нужны скобки для правой ветви операторов - и /.

Answer 2

Алгоритм Шунтирующего двора используется для преобразования Infix (то есть алгебраического) в RPN. Это противоположность того, что вы хотите.

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

Answer 3

C # не имеет встроенной поддержки синтаксического анализа обратной польской нотации (RPN). Вам нужно написать собственный синтаксический анализатор или найти его в Интернете.

Существуют десятки учебных пособий для преобразования постфиксной формы (RPN) в инфикс (алгебраическое уравнение). Взгляните на this , может быть, вы найдете его полезным, и вы можете попытаться «перепроектировать» его для преобразования постфиксных выражений в инфиксную форму, имея в виду, что может быть несколько инфиксных нотаций для данного постфикс один. Есть очень мало полезных примеров, которые на самом деле обсуждают конвертацию постфикса в инфикс. Вот запись из двух частей, которая мне показалась очень полезной. У этого также есть некоторый псевдокод:

• PostFix в Infix: преобразование RPN в алгебраические выражения
• Постфикс в инфикс, часть 2: добавление скобок

Answer 4

Если вы можете прочитать ruby, вы найдете несколько хороших решений для этого здесь

Answer 5

Я только что написал версию на Java, она здесь и одна в Objective-C, более здесь .

Возможный алгоритм : Учитывая, что у вас есть стек с вводом в rpn, как пользователь будет вводить его, например, 8, 9, *. Вы перебираете массив от первого до последнего и всегда удаляете текущий элемент. Этот элемент вы оцениваете. Если это операнд, вы добавляете его в стек результатов. Когда это оператор, вы дважды извлекаете стек результатов (для двоичных операций) для операндов и записываете строку результата в стек результатов.

В качестве примера ввода « 8, 9, +, 2, *» вы получите эти значения в стеке результатов (квадратные скобки для обозначения отдельных элементов) :

шаг 1: [8]

шаг 2: [8], [9]

шаг 3: [(8 + 9)]

шаг 4: [(8 + 9)], [2]

шаг 5: [(8 + 9) * 2]

Когда входной стек пуст, вы закончите, и единственным элементом resultStack будет ваш результат. (Однако обратите внимание, что входные данные могут содержать несколько записей или такие, которые не имеют смысла, например, ведущая операция: "+ 2 3 /".)

Реализации в ссылках сознательно не используют какие-либо самодельные типы, например операторы или операнды, а также не применяются, например, составной шаблон. Это просто и понятно, поэтому его легко понять и перенести на любой другой язык.

Портировать его на C # просто.

Answer 6

Если у вас есть исходный текст (строка / строки), который вы хотите преобразовать из RPN (постфиксная нотация) в «нормальную нотацию» (инфикс), это, безусловно, возможно (и, вероятно, не так уж сложно).

RPN был разработан для стековых машин, так как способ представления операции («2 + 3» -> «2 3 +») соответствовал тому, как она фактически выполнялась на оборудовании (вставьте «2» в стек, вставьте «3» в стек, вытолкните два верхних аргумента из стека и добавьте их, верните обратно в стек).

По сути, вы хотите создать синтаксическое дерево из вашего RPN, сделав 2 выражения, которые вы хотите оперировать на «конечных узлах», и саму операцию, которая следует после этого, «родительским узлом». Вероятно, это будет сделано путем рекурсивного просмотра вашей входной строки (возможно, вы захотите убедиться, что подвыражения правильно заключены в скобки для дополнительной ясности, если они еще не сделаны).

Когда у вас есть это синтаксическое дерево, вы можете выводить префиксную, инфиксную или постфиксную нотацию, просто выполняя предварительный, пост-порядок или упорядоченный обход этого дерева (опять же, если необходимо, заключите в скобки вывод для ясности ).

Более подробную информацию можно найти здесь .

Answer 7

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