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

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

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

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

Answer 6

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

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

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

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

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

Answer 7

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