{-----------------------------------------------------------------------------
   Exact Arithmetic (in Haskell)

                         Written by T.Yoshino <tossy-2@yl.is.s.u-tokyo.ac.jp>
 -----------------------------------------------------------------------------}
import Ratio
import IO

{----- Generic Helper Functions ----------------------------------------------}

-- ユーザ定義の比較関数を用いた簡易クイックソート
sort :: (a -> a -> Bool) -> [a] -> [a]
sort _ []	= []
sort f (p:ps)	= sort f lt ++ [p] ++ sort f ge
		  where	lt = filter (not . f p) ps; ge = filter (f p) ps

-- 数を平方数と非平方数に因数分解する
quadratic :: Integer -> (Integer, Integer)
quadratic x = aux primes x 1
  where	aux (a:as) n q
	  | a * a > n		= (q, n)
	  | mod n (a * a) == 0	= aux (a:as) (div n $ a * a) (q * a)
	  | otherwise		= aux as n q
	primes = s [2..] where s (x:xs) = x : [y | y <- xs, mod y x /= 0]

-- 二項演算子の一般型
type Binary a = a -> a -> a

{----- Arithmetic of X and X^* -----------------------------------------------}

-- データ型定義
type Component	= (Integer, Rational)		-- (root, coeff)
data Value	= V [Component] deriving (Eq)

{- 和の正規化
	* 根号内の数字の昇順
	* 同じ根号を持つ要素はまとめる
	* 係数が 0 の項を消去する					-}
normalize :: [Component] -> [Component]
normalize = reduce . merge . sort (\(r1,_) (r2,_) -> r1 < r2)
  where	merge ((r1,c1):(r2,c2):xs)
	  | r1 == r2	= merge ((r1, c1 + c2):xs)
	  | otherwise	= (r1,c1) : merge ((r2,c2):xs)
	merge x		= x		-- compensate [e] and []
	reduce		= filter ((0 /=) . snd)

-- 注: Value 型の値に含まれている要素は正規化されていなければならない。

-- 二項演算子をリフトする操作
scan :: (Binary Rational) -> Rational -> Binary Value
scan f id (V xs) (V ys) = V (normalize $ aux xs ys)
  where	aux xs []		= coeffmap (flip f id) xs
	aux [] ys		= coeffmap (f id) ys
	aux ((r1,c1):xs) ((r2,c2):ys)	-- マージソート的なことをやる
		| r1 < r2	= (r1, f c1 id) : aux xs ((r2,c2):ys)
		| r1 > r2	= (r2, f id c2) : aux ((r1,c1):xs) ys
		| r1 == r2	= (r1, f c1 c2) : aux xs ys
	coeffmap f xs		= [(r, f c) | (r,c) <- xs]

-- 演算子定義
instance Num Value where
 (+)		= scan (+) 0
 (-)		= scan (-) 0
 (V x) * (V y)	= V $ normalize [mulC e1 e2 | e1 <- x, e2 <- y]
  where	mulC (r1,c1) (r2,c2) =
		let (q,p) = quadratic (r1 * r2) in (p, c1 * c2 * (q % 1))
 fromInteger x	= V $ normalize [(1, toRational x)]

instance Fractional Value where
 (V a) / (V [(r,c)])	= V . normalize $ map div a
  where	div (rx,cx) = let (q,p) = quadratic (rx * r) in (p, cx * (q % r) / c)
 _ / _		= error "Unsupported format in division"

sqrtV :: Value -> Value
sqrtV (V [])	= V []	-- sqrt(0)
sqrtV (V [(1,x)])	-- 単項有理数でなければならない。
	| x > 0	= let (q,p) = quadratic (a * b) in V [(p, q % b)]
		  where a = numerator x; b = denominator x
sqrtV _		= error "Unsupported term in square root"

{----- Abstract Machine Y ----------------------------------------------------}

-- データ構造定義
data Insn	= Push Integer | Add | Sub | Mul | Div | Sqrt | Disp | Stop
			deriving (Eq, Show, Read)
data YState	= ST ([Value], [String]) -- stack と出力された文字列(出力逆順)

-- 初期状態
initial :: YState
initial =  ST ([], [])

-- 2 オペランド命令にリフトする
bin_insn :: Binary Value -> YState -> YState
bin_insn f (ST (v1:v2:rest, o))	= ST (f v2 v1 : rest, o)

-- 命令実行エンジン
step :: YState -> Insn -> YState
step st@(ST (s,o)) i	= case i of
	Push x	-> ST (fromInteger x : s, o)
	Sqrt	-> let v:rest = s in ST (sqrtV v : rest, o)
	Disp	-> let v:rest = s in ST (rest, show v : o)
	Stop	-> if s == [] then ST (s, o)
		   else error "Term called for non-empty stack"
	_	-> bin_insn fn st
	  where	fn = case i of Add -> (+); Sub -> (-); Mul -> (*); Div -> (/)

{----- User Interfaces -------------------------------------------------------}

-- 文字列化ルールの定義
instance Show Value where
 show (V xs)	= aux xs
  where	aux []		= "0"
	aux [x]		= show_comp x
	aux (x:xs)	= show_comp x ++ " + " ++ aux xs
	show_comp (r,c) = if r == 1 then show_ratio c
			  else if c == 1 then sq else if c == -1 then '-' : sq
			  else show_ratio c ++ '*' : sq
		where sq = "sqrt(" ++ show r ++ ")"
	show_ratio c	= show p ++ (if q > 1 then '/' : show q else "")
		where p = numerator c; q = denominator c

-- Toplevel
loop :: Handle -> YState -> IO YState
loop h st = do
	x <- hGetLine h; let insn = read (capitalize x); next = step st insn
	(if insn /= Stop then loop h else return) next
  where	capitalize (x:xs) = toEnum (fromEnum x - 0x20) : xs

main :: IO ()
main = do
	h <- openFile "sqrt.in" ReadMode; ST (_, ss) <- loop h initial
	putStr . concat . reverse . map (++ "\n") $ ss; hClose h