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

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

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

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

Да. Подумайте, как работает калькулятор 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). Таким образом, для правоассоциативных операторов левая ветвь должна иметь более высокий приоритет (а не более высокий или равный), чтобы избежать заключения в скобки.

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

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

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

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

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

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

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

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

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

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

Я только что написал версию на 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# очень просто.