Differences

This shows you the differences between two versions of the page.

--- courses:b3b33alp:cviceni:t08 [2019/09/21 11:40]
stepan removed
+++ courses:b3b33alp:cviceni:t08 [2019/11/18 09:14]
stepan created
@@ Line 91: / Line 91: @@
 ==== Lehká varianta ====
- * Napište program **assemble.py**, který si ze souboru se jménem zadaným jako první argumentu na příkazové řádce, přečte rozměr pole a díly, kterými má to pole zaplnit
+  * Napište program **postfix.py**, který převede výraz z [[https://cs.wikipedia.org/wiki/Infixov%C3%A1_notace|infixového zápisu]] (standardní zápis výrazů, jak jste zvyklí ze školy) do postfixového zápisu (tzv. [[https://cs.wikipedia.org/wiki/Postfixov%C3%A1_notace|reverzní polské notace]]) s využitím algoritmu [[https://cs.wikipedia.org/wiki/Shunting-yard_%28algoritmus%29|shunting yard]].
-    * první řádek obsahuje dvě čísla //S// //R//, kde //R// je počet řádků a //S// je počet sloupců obdélníkového pole
-    * dále násluduje //R// řádků, kde
-      * 0 - definují volná pole v matici, která se mají vyplnit zadanými dílky
-      * -1 - definují obsazená pole, kam dílky nesmí zasahovat
-      * čísla na jednom řádku jsou oddělena jednou nebo více mezerami (použijte funkci "split()" bez parametrů).
-    * každý další řádek obsahuje popis jednoho dílku:
-      * jedna řádka obsahuje souřadnice čtverečků (x y), ze kterých je sestaven celý dílek
-      * souřadnice jsou uvedeny za sebou bez oddělovacích čárek a závorek
-      * dílek může být libovolně posunut, nemusí obsahovat čtverec se souřadnicemi (0,0)
-  * Program v souboru **assemble.py** nalezne libovolné pokrytí volných polí matice dílky, které se použijí tak, jak jsou zadány - nesmíte je natáčet ani převracet, pouze posouvat. Námi zadané příklady mají právě jedno řešení.
-  * Výstupem programu je pokrytí matice dílky, kdy plocha prvního dílku (zadaný v souboru hned za maticí volného místa) je vyplněna číslem 1, plocha druhého dílku (na další řádce za prvním dílkem) číslem 2, atd.
-  * Notace pro popis dílků: je to seznam x y souřadnic.
+  * **Vstup**:
-  * Pro T-dílek na obrázku je jeho popis: 0 0 1 0 2 0 1 1
+    * textový řetězec, přes standardní vstup
-{{:courses:b3b33alp:cviceni:blokus1.eps.png?200|}}
+    * obsahuje pouze celá kladná čísla, kulaté závorky a operace '' + - * / <nowiki>**</nowiki> ''
+    * mezi dvěma členy je vždy právě jedna mezera
-  * Pro obsah zadan0ho souboru:
+  * **Výstup**:
-<code>
+    * pokud je vstupní řetězec ve správném formátu, pak je výstup textový řetězec reprezentující vstupní výraz v postfixové notaci. Mezi každými dvěma členy výstupu vytiskněte právě jednu mezeru
-5
+    * jinak ''ERROR''
-  0 0 0 0
-  0 0 0 0
+  * priorita operátorů: ''<nowiki>**</nowiki>'' větší než ''*'', ''/'', větší než ''+'', ''-''
-  0 0 0 0
+  * operátor mocnění je asociativní zprava
--1  0 0 0 0
--1 -1 0 0 0
+  * **Příklad 1(a)**: <code>
- 2 2 1 2 0 1 0 0 0 0 1
++ 4 * 2 / ( 1 - 5 )
-0 0 1 1 1 2 1 2 0 2 2
+</code> výstup <code>
- 0 3 1 2 1 1 1 0 1
+ 4 2 * 1 5 - / +
-0 0 1 0 2 1 1 2 1
 </code>
-Příklad dílku 1:
+  * **Příklad 1(b)**: <code>
-<code>
+( 3 + 4 ) * 2 / ( 1 - 5 )
- 2 2 1 2 0 1 0 0 0 0 1
+</code> výstup (všimněte si, jak se oproti předchozímu příkladu projeví přidání závorky)<code>
+4 + 2 * 1 5 - /
 </code>
-<code>
+  * **Příklad 2** <code>
-souřadnice
+* 3 ** 5
-y
+</code> Výstup: <code>
+3 5 ** *
+</code>
-  *
+  * **Příklad 3**: <code>
-* *
+( 3 * ( 4 - 5 ) ) + ( 8 * ( 10 + 2 ) / 9 )
-***
+</code> výstup <code>
-souřadnice x
+4 5 - * 8 10 2 + * 9 / +
 </code>
+  * **Příklady chybných vstupů**
+    * ''2 + ( 4 ( * 5 ) )''
+    * ''3 - * 5''
+    * ''( 2 * ( 1 - 3 )''
-Graficky znázorněné všechny dílky
+==== Těžká varianta ====
-:{{:courses:b3b33alp:cviceni:ubongo-0e.png?100|}}
+  * Napište program **pretoin.py**, který převede výraz z [[https://cs.wikipedia.org/wiki/Prefixov%C3%A1_notace|prefixové notace]] do [[https://cs.wikipedia.org/wiki/Infixov%C3%A1_notace|infixového zápisu]]
-:{{:courses:b3b33alp:cviceni:ubongo-1.png?100|}}
+  * **Vstup**
-:{{:courses:b3b33alp:cviceni:ubongo-2e.png?100|}}
+    * textový řetězec přes standardní vstup
-:{{:courses:b3b33alp:cviceni:ubongo-3e.png?100|}}
+    * řetězec obsahuje pouze kladná celá čísla, operátory ''- + / * <nowiki>**</nowiki>'', případně mezeru mezi dvěma členy, pokud je to pro jednoznačnost výrazu nutné ( dvě hvězdičky bez mezery ''<nowiki>**</nowiki>'' je operátor mocnění, dvě hvězdičky oddělené mezerou ''* *'' jsou dvě po sobě jdoucí operace násobení), dva numerické členy jsou vždy oddělené mezerou
-program vytiskne:
+  * **Výstup**
+    * pokud je na vstupu platný řetězec v prefixové notaci, pak řetězec převedený na infixovou notaci, vytiskněte bez mezer
+    * jinak ''ERROR''
-<code>
+  * Operace +,-,*,/ se vyhodnocují zleva, operace <nowiki>**</nowiki> se vyhodnocuje zprava (stejně jako je to v Pythonu)
-3 3 3 3
+  * Složitost této úlohy je ve správném doplnění závorek, které musí zaručit správné vyhodnocení zleva doprava, ale nesmíte závorky používat zbytečně
-4 4 2 3
-2 2 2 1
--1 2 1 2 1
--1 -1 1 1 1
-</code>
-Nápověda možného řešení:
+  * **Příklady:**
-  * Postupně se snažím vyplnit prázné místo, např odshora zleva
+    * Vstup <code>
-  * Na první volné políčko se snažím umístit dílek tak, že toto volné pole zaplní svou nejhořejší levou částí (protože vše nad a vlevo od volného políčka je zaplněno, viz obrázek) a rekurzivně zavolám plnění se seznamem dílků, ze kterých odstraním právě použitý dílek
+*-4 2 3
-{{:courses:b3b33alp:fill.png?100|}}
+</code> převede na výstup: <code>
-  * Pokud to nevyjde a políčko nelze žádným dílkem zaplnit tak, aby tento dílek nepřekrýval jiné dílky, nebo nepřesahoval přes okraj matice), pak se vrátím z rekurze
+(4-2)*3
-  * Při návratu z rekurze, zkusím obsadit volné pole jiným dílkem
-  * Pro správné fungování rekurze buď vytvořím nové pole s nově vloženým dílkem, nebo při návratu z rekurze musím odstranit z matice starý dílek
-  * Pokud již nemám dílky a celá matice je obsazená - mám řešení a mohu skončit
-==== Těžká varianta ====
-  * Napište program **three.py**, který převede výraz z [[https://cs.wikipedia.org/wiki/Infixov%C3%A1_notace|infixového zápisu]] (standarní zápis výrazů, jak jste zvyklí ze školy) do reprezentace [[https://en.wikipedia.org/wiki/Three-address_code|tří-adresného módu]]. Tento tří-adresový kód je využíván překladačem, jako mezistupeň mezi programem a strojovým jazykem.
-**Vstup:**
-  * Výraz je zadán na jedné řádce standardního vstupu
-  * Vstupní výraz může obsahovat pouze celá kladná celá čísla (záporné číslo je unární operátor - a kladné číslo), mezery, závorky (, ) a operace +,-,*,/,^. (Operace ^ je mocnina a má nejvyšší prioritu, nejnižší prioritu mají operace +,-, prostřední prioritu *,/)
-  * Oproti lehké variantě výraz umožňuje unární + a -, tedy je správně 2 + - 3, i 2-+-3 (POZOR unární - má ještě vyšší prioritu než mocnina)
-**Výstup:**
-  * Při převodu musíte otestovat správnost zadaného výrazu a pokud je formát chybný, pak vytisknete ERROR
-  * formát výstupu:
-    * první trojice má číslo 1, každá další trojice o jedno větší číslo
-    * trojice tiskněte bez mezer, tak jak je uvedeno níže
-    * unární - se přeloží jako trojice, např -5 bude tXX:=0-5
-    * unární + se vypustí, ve výrazu je vlastně zbytečné
-    * výraz se vyhodnocuje zleva doprava (všechny operace i mocniny) a toto vyhodnocování určuje pořadí trojic. V příkladu níže není tedy možné nejdříve vypočítat rozdíl 1-5 a teprve potom součin 4*2
-Příklad:
-  * Vstup
-<code>
-+ 4 * 2 / ( 1 - 5 )
 </code>
-  * převede na výstup:
+    * Vstup <code>
-<code>
++-4 2 3
-t1:=4*2
+</code> převede na výstup: <code>
-t2:=1-5
+-2+3
-t3:=t1/t2
-t4:=3+t3
 </code>
+    * Vstup <code>
-Příklad:
+*4-2 3
-  * Vstup
+</code> převede na výstup: <code>
-<code>
+*(2-3)
-(1+2)*(3+4)/(5+6)
 </code>
-  * převede na výstup:
-<code>
-t1:=1+2
-t2:=3+4
-t3:=t1*t2
-t4:=5+6
-t5:=t3/t4
-</code>
-Příklad:
-  * Vstup
-<code>
-+2/(*4+5)
-</code>
-  * převede na výstup:
-<code>
-ERROR
-</code>