Evaluate Reverse Polish Notation
Kamu mendapatkan ekspresi aritmetika dalam notasi Polandia terbalik, sebagai sebuah array token. Setiap operator muncul tepat setelah kedua operandnya, jadi 3 4 + berarti 3 + 4 dan 3 4 + 2 * berarti (3 + 4) * 2, tanpa tanda kurung. Setiap token adalah bilangan bulat atau salah satu operator +, -, *, dan /.
Kembalikan nilai ekspresi tersebut. Pembagian dibulatkan menuju nol: 7 / 2 adalah 3 dan -7 / 2 adalah -3.
Fungsi
- tokensstring-array
- angka dan operator dalam ekspresi, secara berurutan
- Mengembalikaninteger
- nilai dari ekspresi
Batasan
1 ≤ tokens.length ≤ 104- Setiap token adalah
+,-,*,/, atau bilangan bulat dari-200hingga200yang ditulis dalam desimal, dengan tanda minus di depan jika nilainya negatif. tokensmerupakan ekspresi yang valid dalam notasi Polandia terbalik.- Tidak terjadi pembagian dengan nol, dan setiap nilai antara maupun nilai akhir lebih besar dari
-231dan lebih kecil dari231.
Contoh
- Input
- tokens = ["8", "3", "-", "4", "*"]
- Output
- 20
- Penjelasan
- Operator
-diterapkan pada 8 lalu 3, dalam urutan itu, sehingga hasilnya 5, bukan -5. Kemudian*mengalikan 5 itu dengan 4, sehingga hasilnya 20.
- Input
- tokens = ["6", "2", "9", "3", "/", "-", "*"]
- Output
- -6
- Penjelasan
/menggunakan dua nilai terbaru: 9 dibagi 3 hasilnya 3. Lalu-menghitung 2 dikurangi 3, hasilnya -1, dan*mengalikan 6 dengan -1.
- Input
- tokens = ["10", "-7", "2", "/", "+"]
- Output
- 7
- Penjelasan
- Token
-7adalah angka, bukan operator. -7 dibagi 2 adalah -3.5, yang dipotong menuju nol menjadi -3, bukan -4, dan 10 ditambah -3 adalah 7.
Pertanyaan lanjutan
Bisakah kamu menyusun kembali ekspresi dalam notasi biasa, seperti (3 + 4) * 2, dengan menambahkan tanda kurung hanya jika tanda kurung tersebut mengubah maknanya?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Baca token dari kiri ke kanan. Saat kamu menemukan operator, dua nilai mana yang dikenai operator tersebut? Perhatikan urutan nilai-nilai itu dihasilkan.
Operator selalu berlaku pada dua nilai terbaru yang belum digunakan oleh operator mana pun, dan hasilnya menjadi nilai baru bagi operator berikutnya. “Yang terbaru dan belum digunakan” persis seperti yang diberikan oleh stack.
Masukkan setiap angka. Saat menemukan operator, keluarkan operand kanan terlebih dahulu, lalu operand kiri, gabungkan keduanya dalam urutan tersebut, dan masukkan hasilnya. Saat token habis, stack berisi satu nilai: jawabannya. Pastikan pembagianmu membulatkan ke arah nol.
Solusi
Setiap operator diterapkan pada dua nilai yang tepat sebelumnya, dan salah satunya bisa merupakan hasil dari operator sebelumnya. Jadi, tumpukan nilai mengevaluasi ekspresi dalam satu kali lintasan. Hal yang perlu diperhatikan adalah urutan operand untuk - dan /, membedakan operator - dari angka -7, serta pembagian yang membulatkan hasil ke bawah.
Uraikan operator pertama, lalu ulangi
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Temukan operator paling kiri. Tidak ada operator sebelumnya, jadi dua token sebelumnya adalah angka, yaitu operandnya. Ganti tiga token itu dengan hasilnya. Operator setelahnya melihat nilai itu di posisi bagian tersebut, sehingga ekspresi tetap memiliki makna yang sama. Ulangi sampai tersisa satu angka.
Setiap putaran mencari lagi dari awal. Dengan 5,000 angka yang diikuti 4,999 operator, operator pertama berada kira-kira di tengah setiap putaran, sehingga pencarian saja membaca sekitar 1.25 × 10^7 token.
Algoritma
- Salin token ke dalam list yang bisa kamu ubah.
- Pindai dari awal hingga operator pertama, pada posisi
k. - Terapkan operator itu pada angka di
k-2(kiri) dank-1(kanan). - Ganti tiga token di
k-2,k-1, dankdengan hasilnya. - Ulangi hingga tersisa satu token, lalu kembalikan token itu sebagai angka.
def evalRPN(tokens):
items = list(tokens)
while len(items) > 1:
# Find the first operator. Everything to its left is a plain number.
k = 0
while items[k] not in ("+", "-", "*", "/"):
k += 1
left, right, op = int(items[k - 2]), int(items[k - 1]), items[k]
if op == "+":
value = left + right
elif op == "-":
value = left - right
elif op == "*":
value = left * right
else:
value = int(left / right) # int() truncates toward zero
# Replace the three tokens "left right op" with the number they stand for.
items[k - 2:k + 1] = [str(value)]
return int(items[0])Satu kali lintasan dengan stack nilai
Intuisi
Simpan nilai di sebelah kiri operator pada tumpukan, bukan membacanya kembali. Sebuah angka masuk ke tumpukan. Operator mengeluarkan dua nilai, menggabungkannya, lalu memasukkan hasilnya ke tumpukan. Hasil itu menunggu operator berikutnya seperti nilai lainnya. Tumpukan selalu menyimpan nilai dari bagian lengkap yang sudah dibaca, sesuai urutannya, sehingga operator selalu diterapkan pada dua nilai teratas. Nilai teratas adalah operand kanan karena nilai itu dihasilkan terakhir.
Dalam 6 2 9 3 / - *, / mengeluarkan 3 lalu 9 dan memasukkan 3, - mengeluarkan 3 lalu 2 dan memasukkan -1, dan * memasukkan 6 × -1 = -6. Setiap token diproses satu kali: waktu O(n) dan ruang O(n).
Algoritma
- Mulai dengan stack kosong.
- Untuk setiap token berupa angka, masukkan nilainya ke stack.
- Untuk setiap operator, keluarkan operand kanan, lalu operand kiri.
- Hitung
left op right, dengan pembulatan menuju nol untuk/, lalu masukkan hasilnya. - Setelah token terakhir, kembalikan satu-satunya nilai di stack.
def evalRPN(tokens):
stack = [] # values of the parts read so far, the newest on top
for token in tokens:
if token in ("+", "-", "*", "/"):
# The right operand was pushed last, so it comes off first.
right = stack.pop()
left = stack.pop()
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
elif token == "*":
stack.append(left * right)
else:
# int() truncates toward zero; // would round -7 / 2 down to -4.
stack.append(int(left / right))
else:
stack.append(int(token))
return stack[0]
Jebakan dan kasus tepi
- Menukar operand. Pop pertama adalah operand kanan:
["3", "5", "-"]bernilai -2, dan["2", "9", "/"]bernilai 0, bukan 4. - Mengenali operator dari karakter pertamanya.
-7diawali tanda minus, tetapi merupakan angka, jadi bandingkan seluruh token. - Membulatkan ke bawah, bukan memotong.
//di Python,/di Ruby,%/%di R, danmath.floordi Lua mengubah-7 / 2menjadi -4 dan-1 / 3menjadi -1. - Mencetak
-0. Di JavaScript dan Lua,0 * -5danMath.trunc(-1 / 3)menghasilkan nol negatif. Tambahkan 0 ke nilai akhir.
Pertanyaan yang sering diajukan4
Apa kompleksitas waktu dari Evaluate Reverse Polish Notation?
Solusi stack berjalan dalam waktu O(n) untuk n token: setiap angka di-push satu kali, dan setiap operator melakukan dua operasi pop dan satu operasi push. Stack menampung hingga sekitar n/2 nilai, jadi penggunaan ruangnya adalah O(n).
Mengapa notasi Polandia terbalik tidak memerlukan tanda kurung?
Dalam notasi biasa, 3 + 4 * 2 memerlukan aturan prioritas atau tanda kurung untuk menentukan operasi mana yang dilakukan lebih dahulu. Dalam notasi Polandia terbalik, operator selalu diterapkan pada dua nilai tepat sebelumnya, jadi urutan token menentukan hasilnya: 3 4 2 * + menghasilkan 11 dan 3 4 + 2 * menghasilkan 14.
Bagaimana cara melakukan pembagian dengan pemotongan ke arah nol di Python?
Gunakan int(a / b). Operator // membulatkan ke bawah, jadi -7 // 2 adalah -4, sedangkan int(-7 / 2) adalah -3. Pembagian float cukup akurat untuk nilai 32-bit. Untuk bilangan bulat yang lebih besar, bagi nilai absolutnya dengan // lalu kembalikan tandanya.
Bagaimana cara mengubah ekspresi biasa menjadi notasi Polandia terbalik?
Algoritma shunting-yard melakukannya dalam satu kali pemindaian dengan stack operator. Angka langsung masuk ke output. Sebelum memasukkan operator, pindahkan semua operator di dalam stack yang memiliki prioritas lebih tinggi atau sama ke output. Tanda kurung tutup memindahkan operator keluar sampai menemukan pasangan tanda kurung buka. Pada akhirnya, pindahkan sisanya ke output.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def evalRPN(tokens):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
tokens = ["8", "3", "-", "4", "*"]
Output yang diharapkan
20