Обратная польская запись - это форма записи для математических выражений, где операторы следуют за операндами. При оценке выражения RPN каждый двоичный оператор ссылается на два операнда , непосредственно предшествующих ему . Возьмем это выражение RPN, например:
5 4 3 + *
Начните сканирование выражения слева, пока не дойдете до первого оператора, который является +. Этот оператор имеет операнды 4 и 3 (те, которые идут непосредственно перед ним), поэтому мы можем заменить все три с результатом, 7. (Обратите внимание, что скобки не нужны, но я использую их, чтобы прояснить смысл).
5 (4 3 +) * => 5 7 *
Теперь у нас есть оператор * и два операнда 5 и 7 (что в действительности является результатом 4 + 3). Мы умножаем 5 и 7, и все выражение оценивается как 35.
5 7 * => 35
Это общий алгоритм для вычисления любого выражения RPN.
Выражения RPN особенно хорошо подходят для анализа компьютерами, использующими структуру данных, известную как стек .
Стек - это упорядоченная коллекция, один конец которой обозначен как «верх». Элементы всегда добавляются в стек или удаляются из стопки сверху. Таким образом, единственный элемент, который нужно удалить, это всегда элемент, который был добавлен последним. По этой причине стеки иногда называют Last In, First Out (или LIFO), поскольку последний элемент, помещенный в стек, находится сверху и, таким образом, будет удален первым.
В C вы можете реализовать стек с двумя переменными: массивом (достаточно большим, чтобы вместить максимальное количество элементов, которое, как вы ожидаете, может понадобиться в стеке), и целым числом, которое указывает, какой индекс в массиве в настоящее время является верхним.
Стеки хорошо подходят для оценки выражения RPN, потому что, когда вы сталкиваетесь с оператором, оно всегда применяется к самым последним встречаемым операндам. Так как вы просматриваете выражение слева, вы можете сохранить операнды в стеке. Возьмем наш пример снова:
5 4 3 + *
Первым делом здесь операнд (5), поэтому поместите его в стек (который изначально пуст). Затем мы встречаем 4 и помещаем его в стек. Это становится новой вершиной. Затем мы делаем то же самое с 3.
5 4 3 <-- top
+ * // Remaining expression
Далее мы сталкиваемся с оператором +. Мы знаем, что это относится к ранее обнаруженным операндам, но где мы можем их найти? Конечно, на вершине стека! Вытяните 3 и 4 из стека и добавьте их, чтобы получить 7. Но что делать с результатом? Ну, это может быть операнд другого оператора, поэтому поместите его обратно в стек (точно так же, как мы заменили операнды и оператор результатом, когда мы вычислили выражение вручную):
5 7 <-- top
* // Remaining expression
Теперь мы видим *. Еще раз, самые последние операнды - это два верхних операнда в стеке. Мы выталкиваем их и умножаем, чтобы получить 35, а затем помещаем их обратно в стек.
35 <-- top
// No expression remaining
На данный момент мы достигли конца выражения, и единственное, что в стеке - это результат. Были сделаны! Вы можете видеть, как стек операндов «сохраняет» первые обнаруженные операнды, пока не встретится соответствующий оператор, который может находиться на другом конце выражения.
Если бы мы достигли конца и обнаружили, что в стеке осталось более одного числа, это означало бы, что в выражении слишком много операндов и недостаточно операторов. С другой стороны, если бы мы столкнулись с оператором в какой-то момент и имели меньше двух операндов в стеке, мы бы знали, что в выражении слишком много операторов и недостаточно операндов.