Zadanie
Julka má veľa domácich úloh. Nebaví ju ale stále počítať komplikované príklady ručne. Rozhodla sa siahnuť po modernom pomocníkovi - kalkulačke. Zistila však, že na svojom iPade stále nemá predinštalovanú kalkulačku, ktorú by mohla použiť. Preto musela oprášiť svoju malú starú kalkulačku. Hneď pri prvom príklade ale nastal problém. Jej kalkulačka nedokáže vypočítať všetky výrazy. Viete jej pomôcť zistiť, ktoré výrazy dokáže Julka vyrátať?
Úloha
Julkina kalkulačka dokáže vykonávať iba základné operácie -
sčítavanie, odčítavanie, násobenie a delenie. Ako bežná jednoduchá
kalkulačka, ani táto nepodporuje zátvorky a operácie vždy vykonáva medzi
posledným výsledkom a zadanou hodnotou. Teda, ak zadáme
1 + 2 =
, na display-i svieti 3
, pre
pripočítanie čísla \(4\) stlačíme
+ 4 =
a na display-i sa zobrazí 7
.
V pamäti kalkulačky má Julka uložený nový svetový rekord počtu desatinných miest pre konštantu Pí, ktorý by bola škoda stratiť (teda pamäť kalkulačky nepoužívajte). Takisto, nemôžeme sa s medzivýsledkami spoliehať na Julkinu pamäť. Všetky operácie musia byť vykonané na kalkulačke a nesmieme si pamätať žiadne medzivýsledky “v hlave.”
Výraz je potrebné na kalkulačke vykonať tak, ako je zadaný na vstupe – teda, nemôže si ho Julka upraviť do iného tvaru, maximálne môže prehodiť poradie operandov. \(1 + 2\) môže zadať aj ako \(2 + 1\), ale napríklad \(3 + (1 - 2)\) nemôže zadať ako \(3 - (2 - 1)\), aj napriek tomu, že ide o výraz získaný ekvivalentnou úpravou.
Formát vstupu
Na vstupe sú dva riadky. V prvom riadku je číslo N
-
počet operácií a operandov na vstupe. V druhom riadku nasleduje
N
medzerou oddelených operandov (kladných celých čísiel) a
operácií (+
, -
, *
,
/
).
Matematické výrazy sú na vstupe zadané v tzv. prefixovom zápise
(Polish notation). Na rozdiel od bežne používaného infixového
zápisu, ktorý umiestňuje znamienka operácií medzi operandy
(3 + 2
), v prefixovom zápise ich píšeme pred operandami
(+ 3 2
). Napríklad 1 + 2 * 3
zapíšeme ako
+ 1 * 2 3
. V prefixovom zápise nie je potrebné používať
zátvorky, keďže poradie operácií je vždy zľava doprava:
(1 + 2) * 3
zapíšeme ako * + 1 2 3
.
Môžete predpokladať, že výraz na vstupe je validný.
Formát výstupu
Na výstup vypíšte ANO
alebo NIE
podľa toho,
či dokáže Julka vyrátať zadaný výraz na svojej kalkulačke.
Hodnotenie
Sú \(4\) sady vstupov. Platia v nich nasledovné obmedzenia:
Sada | \(1\) | \(2\) | \(3\) | \(4\) |
---|---|---|---|---|
\(3 \leq n \leq\) | \(1\,000\) | \(10\,000\) | \(100\,000\) | \(1\,000\,000\) |
Príklady
Input:
5
+ + 1 2 3
Output:
ANO
Najprv zrátame 1 + 2, potom k výsledku pripočítame 3.
Input:
7
+ + 1 2 + 3 4
Output:
NIE
Potrebovali by sme si niekde pamätať medzivýsledok 1+2 alebo 3+4.
Naše riešenie si rozdelíme na dve časti – v prvej sa pokúsime spracovať vstup a v druhej zistiť, či sa dá daný výraz vypočítať.
Načítanie vstupu
Bežné aritmetické výrazy je vhodné v počítači reprezentovať tzv. aritmetickým stromom. Aritmetický strom je binárny strom, kde v listoch sa nachádzajú operandy (čísla) a v ostatných vrcholoch sa nachádzajú operácie. Aritmetický strom pre výraz 2 * (3 + 4)
by vyzeral takto:
Príjemná vlastnosť takéhoto stromu je, že z neho vieme pomerne jednoducho vyčítať výrazy v rôznych zápisoch. Nás ale bude zaujímať prefixový zápis, ktorý z takéhoto stromu dostaneme napríklad týmto jednoduchým rekurzívnym algoritmom: pre každý vrchol vypíšeme svoju hodnotu a následne rekurzívne pokračujeme do ľavého a pravého potomka. Môžeš sa doma zamyslieť, ako by sme z takéhoto stromu získali infixový a postfixový zápis.
Keď už toto vieme, stačí sa nám zamyslieť, ako vieme takýto strom zostrojiť zo zápisu.
Spracovanie vstupu
Keď už máme aritmetický strom vytvorený, potrebujeme z neho zistiť, či ho Julka dokáže vyrátať na svojej kalkulačke. Pozrime sa najprv na výrazy zo zadania. Výraz + + 1 2 3
vieme prepísať na infixový zápis (1 + 2) + 3
a výraz + + 1 2 + 3 4
zas na (1 + 2) + (3 + 4)
. Môžeš si všimnúť, že sme v zápise naschvál nechali zátvorky, ktoré tam implicitne z prefixového zápisu sú. Takýto výraz na našej kalkulačke vypočítať nevieme – Julka má zakázané robiť úpravy výrazu na vstupe, takže ani tieto zátvorky nemôže dať preč. Z toho si už vieme všimnúť, že Julka nevie vypočítať také výrazy, v ktorých sú zátvorky na oboch stranách operácie.
Ako takéto situácie nájdeme v našom aritmetickom strome? Postupne prejdeme stromom (napríklad algoritmom DFS) a ak nastane situácia, že máme aj v ľavom aj v pravom potomkovi operáciu, vieme, že sa daný výraz vypočítať nedá. Za takéto riešenie bolo možné získať dva body.
Nie všetky operácie sú rovnaké
Na plný počet bodov bolo potrebné si ešte uvedomiť jednu vlastnosť tejto kalkulačky. Výraz 4 * (2 + 3)
vieme vypočítať. Ak ste niekedy vlastnili takúto najlacnejšiu formu kalkulačky, pravdepodobne viete, že zadaním 4 * 2 + 3 =
nedostaneme správny výsledok (lebo výrazy vyhodnocuje zľava doprava bez ohľadu na prioritu operácií). Bežne by ste si proste vypočítali najprv 2 + 3
a potom výsledok vynásobili číslom 4
. Výsledok 2 + 3
si budete musieť buď pamätať, alebo si vo výraze prehodíte poradie operandov: (2 + 3) * 4
. Toto už viete bez problémov vypočítať zadaním 2 + 3 * 4 =
.
Toto ale nefunguje pre všetky operácie. Násobenie a súčet vieme takto upraviť, ale delenie a rozdiel nie. 4 - (2 + 3)
si už nevieme prehodiť tak, aby sa to dalo na takejto kalkulačke vypočítať. Vieme takýto výraz upraviť ale to, ako sme si už spomenuli vyššie, nie je dovolené. Rovnako to platí aj pre delenie. Preto si musíme do nášho riešenia pridať ešte túto situáciu: ak je vo vrchole delenie/rozdiel a jeho pravý potomok je operácia, nepôjde to.
Časová zložitosť riešenia je \(O(n)\), keďže vytvorenie stromu nám zaberie \(O(n)\) času a prejdenie všetkých jeho vrcholov tiež \(O(n)\). Pamäťová zložitosť je \(O(n)\), keďže si pamätáme len vrcholy stromu, ktorých počet je rovný \(n\).
= int(input())
n = input().split()
vstup
= ['+', '-', '/', '*']
ops
class Vrchol:
def __init__(self, value=None):
self.value = value
self.L = None
self.R = None
def __str__(self):
= self.value
s if self.L:
+= f" {self.L}"
s if self.R:
+= f" {self.R}"
s return s
= Vrchol(vstup[0])
root = Vrchol()
root.L = Vrchol()
root.R = [root.R, root.L]
stack
if root.value not in ops:
print("ANO")
raise SystemExit(0)
for v in vstup[1:]:
= stack.pop()
m = v
m.value
if v in ops:
= Vrchol()
m.L = Vrchol()
m.R
stack.append(m.R)
stack.append(m.L)
= root.value in ["-", "/"]
c_on_right = root
v while v:
= None
op = None
nxt if v.L:
if v.L.value in ops:
= v.L.value
op else:
= v.L
nxt
if v.R:
if v.R.value in ops:
if op or c_on_right:
print("NIE")
raise SystemExit(0)
= v.R.value
op else:
= v.R
nxt
= nxt
v = op in ["-", "/"]
c_on_right
print("ANO")
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.