Скачать или смотреть Обратная польская нотация: типы математических обозначений и использование стека для решения выра...

Бесплатный 5-дневный мини-курс: https://backtobackswe.com
Попробуйте нашу полную платформу: https://backtobackswe.com/pricing
📹 Интуитивно понятные видеообъяснения
🏃 Запускайте код по мере обучения
💾 Сохраняйте прогресс
❓Новые, ранее не рассматривавшиеся вопросы
🔎 Получить все решения

Вопрос: Дан массив с последовательностью, представляющей выражение RPN. Вычислите выражение в обратной польской нотации.

Это одна из классических задач. Это классический пример того, когда поведение LIFO благоприятно для решения определенных задач.

Чтобы получить выражение RPN, нам по определению нужны 2 вещи:

Одна цифра или последовательность цифр.

Оно имеет вид ["A", "B", "o"], где A и B — целые числа, а o — оператор (+, -, * или /).

Примеры:

[ "3", "4", "+", "2", "*", "1", "+" ]

то же самое, что и ( ( 3 + 4 ) * 2 ) + 1

что, в свою очередь, то же самое, что и ( 3 + 4 ) * 2 + 1 из-за порядка операций.

Пример 2:

[ "1", "1", "+", "2", "2", "*", "+" ]

Подход

Это классическая задача на стек, давайте просто решим её.

Две ключевые операции:

Когда мы видим цифру, мы помещаем её в стек.

Когда мы видим операцию, мы выполняем 2 извлечения, применяем операцию к двум значениям (первый извлечённый элемент помещается слева от знака, второй — справа от знака), а затем помещаем результат обратно в стек, чтобы мы могли работать с ним дальше.

Если это корректное выражение RPN, то у нас не должно возникнуть проблем с несовпадениями и нулевыми указателями. Всегда уточняйте у своего интервьюера, что это корректная строка RPN.

Сложности

n — длина выражения RPN

Время: O(n)

Мы обработаем все n операторов/операндов в выражении. Каждый из них потребует либо вставки/выталкивания O(1), либо арифметических вычислений O(1).

Арифметические операции занимают O(1).

Вставки и выталкивания O(1).

Пространство: O(d)

Пусть d — общее количество операндов (чисел).

Пусть b — количество операторов (+, -, *, /).

Если у нас d цифр и b операторов, где d + b = n, мы точно не будем использовать O(d + b) памяти (операторы не помещаются в стек).

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

++++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank:    / @hackerrankofficial  

Тушар Рой:    / tusharroy2525  

GeeksForGeeks:    / @geeksforgeeksvideos  

Джарвис Джонсон:    / vsympathyv  

Успех в технологиях:    / @successintech  

++++++++++++++++++++++++++++++++++++++++++++++++++++

Этот вопрос — номер 9.2 в разделе «Элементы собеседований по программированию». Аднан Азиз, Цун-Сиен Ли и Амит Пракаш.