Сложность: Medium
Вам дан массив строк под названием tokens, который представляет арифметическое выражение в обратной польской нотации.
Вычислите это выражение. Верните целое число, которое представляет значение этого выражения.
Обратите внимание на следующие моменты:
Допустимые операторы: '+', '-', '*' и '/'.
Каждый операнд может быть целым числом или другим выражением.
Деление двух целых чисел всегда округляется к нулю.
Деление на ноль в выражении отсутствует.
Входные данные представляют собой действительное арифметическое выражение в обратной польской нотации.
Ответ и все промежуточные вычисления можно представить 32-битным целым числом.
Пример:
Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
👨💻 Алгоритм:
1⃣Обработка входных массивов:
Для языков, таких как Java, где входные данные представлены фиксированным массивом, необходимо определить собственные методы для манипулирования массивом (например, удаление элементов). Это может включать сдвиг элементов для заполнения пробелов после удаления элемента. В качестве альтернативы, копирование массива в ArrayList могло бы упростить удаление, но за счет увеличения сложности по памяти с O(1) до O(n).
2⃣Обработка типов и деление в Python:
Необходимо быть внимательным при обработке типов в Python во время обработки списка, поскольку числа могут быть представлены как строки или целые числа. Кроме того, стандартное деление в Python не округляет к нулю. Вместо этого использование int(a / b) достигает желаемого результата округления, что отличается от деления нацело int(a // b), которое является другим распространенным подходом.
3⃣Использование лямбда-функций:
Лямбда-функции могут упростить реализацию арифметических операций (таких как +, -, *, /). Если вы знакомы с лямбда-функциями, они предлагают элегантное решение для динамической обработки операций. Если лямбда-функции новы или не поддерживаются в используемом языке программирования, можно использовать другие методы, а изучение лямбда-функций можно отложить на потом.
😎 Решение:
class Solution {
private let operations: [String: (Int, Int) -> Int] = [
"+": { $0 + $1 },
"-": { $0 - $1 },
"*": { $0 * $1 },
"/": { $0 / $1 }
]
func evalRPN(_ tokens: [String]) -> Int {
var tokens = tokens
var currentPosition = 0
while tokens.count > 1 {
while operations[tokens[currentPosition]] == nil {
currentPosition += 1
}
let operation = tokens[currentPosition]
let number1 = Int(tokens[currentPosition - 2])!
let number2 = Int(tokens[currentPosition - 1])!
let value = operations[operation]!(number1, number2)
tokens[currentPosition] = String(value)
tokens.removeSubrange((currentPosition - 2)..<currentPosition)
currentPosition -= 1
}
return Int(tokens[0])!
}
}Ставь 👍 и забирай 📚 Базу знаний