Matematické Fórum

Ahoj, neviem si rady s nasledujucou ulohou, myslim si ze to je na dynamicke programovanie, ale nejako to vtom nevidim ako to implementovat. Vopred dakujem :)


Z aritmetického výrazu se nám poztrácely závorky. Určete minimální a maximální hodnotu, které může zadaný výraz nabývat, pokud do něj závorky doplníme vhodným způsobem.

Na stadardním vstupu je zadán korektně zapsaný aritmetický výraz tvořený pouze kladnými jednocifernými celočíselnými konstantami a binárními operátory +, - a *. Výraz tedy neobsahuje víceciferná čísla, žádné závorky, žádné jiné binární operátory ani unární minus, žádné oddělující mezery. Počet konstant ve výrazu není větší než 100. Program vypíše na standardní výstup jediný řádek obsahující dvě celá čísla oddělená mezerou - minimální a maximální hodnotu, kterých lze dosáhnout vhodným doplněním závorek do výrazu.

Můžete předpokládat, že všechny výsledky a i mezivýsledky získané při vyhodnocování jakkoliv uzávorkovaného výrazu nepřesáhnou hodnotu 2 miliardy (tzn. int v jazyce C#).


Příklad 1
Vstup:
   3+2*5+1*7-6

Odpovídající výstup:
   14 204

Vysvětlení:
Výrazy 3+(2*5)+(1*7)-6 nebo 3+(2*5)+(1*(7-6)) nabývají hodnoty 14,
výraz ((3+2)*(5+1)*7)-6 nabývá hodnoty 204.