4. Ako sa to ráta? vzorové riešenie

5
+ + 1 2 3

ANO

7
+ + 1 2 + 3 4

NIE

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\).

n = int(input())
vstup = input().split()

ops = ['+', '-', '/', '*']

class Vrchol:
	def __init__(self, value=None):
		self.value = value
		self.L = None
		self.R = None

	def __str__(self):
		s = self.value
		if self.L:
			s += f" {self.L}"
		if self.R:
			s += f" {self.R}"
		return s

root = Vrchol(vstup[0])
root.L = Vrchol()
root.R = Vrchol()
stack = [root.R, root.L]

if root.value not in ops:
	print("ANO")
	raise SystemExit(0)

for v in vstup[1:]:
	m = stack.pop()
	m.value = v

	if v in ops:
		m.L = Vrchol()
		m.R = Vrchol()
		stack.append(m.R)
		stack.append(m.L)

c_on_right = root.value in ["-", "/"]
v = root
while v:
	op = None
	nxt = None
	if v.L:
		if v.L.value in ops:
			op = v.L.value
		else:
			nxt = v.L

	if v.R:
		if v.R.value in ops:
			if op or c_on_right:
				print("NIE")
				raise SystemExit(0)
			op = v.R.value
		else:
			nxt = v.R

	v = nxt
	c_on_right = op in ["-", "/"]

print("ANO")