C++與演算法

題目 - 小呆的決心

  剛上國中的小呆,在上數學課時總是被老師罵「你怎麼這麼呆,這麼簡單的練習題都不會算,我看你一定連把括號配對起來都不會吧!」事實上,小呆還真的不知道如何將數學式的括號給配對起來。小呆為了挽回在數學課丟掉的面子,決心要將括號如何配對學好。於是小呆跑回家找媽媽商量,但是很遺憾的是,就連小呆的媽媽也不完全會括號配對這種困難的問題。小呆媽媽知道的僅有,要將括號配對好,似乎是要將距離最近的兩個括號弄成一對而已。因此身為一個愛好助人的程式設計師,請你幫助他們母子倆解決括號配對的問題,如此一來小呆及他的家人都會很感謝你的!(因為小呆連最基本的括號配對都不會,基於不能揠苗助長的原則,以下的問題的括號形式皆只有()


Input說明

每個測資有許多列字串(每個字串長度不會超過1000個字元且保證不會有空格)。

Output說明

請你對每列字串輸入,各輸出兩列。

第一列為測資本身

第二列則是和測資長度一樣的字串,把無法配對成功的括號位置標記為^,其餘為-


Sample Input

(1+(2+3)+4+())
)1+2(())+3*(4+5()(
(rock1246((ckcsc20th)

Sample Output

(1+(2+3)+4+())
--------------
)1+2(())+3*(4+5()(
^----------^-----^
(rock1246((ckcsc20th)
^--------^-----------


input1

(1+2)+(2+3)*1000
()
)(
(())

output1

(1+2)+(2+3)*1000
----------------
()
--
)(
^^
(())
----


input2

()))))))))(())()()()()((((((((()))))))))))))((((
1234567789976554433322
()(((((((((
)))))))))()

output2

()))))))))(())()()()()((((((((()))))))))))))((((
--^^^^^^^^------------------------------^^^^^^^^
1234567789976554433322
----------------------
()(((((((((
--^^^^^^^^^
)))))))))()
^^^^^^^^^--


input3

((((((((((((((((((((((((((()))))))))))))))))))))))))))()()()()()()()()()()()()()()()()(())
)(((((((((((((((((((((((((()))))))))))))))))))))))))))()()()()()()()()()()()()()()()()(())
((((((((((((((((((((((((((()))))))))))))))))))))))))))()()()()()()()()()()()()()()()()(()(
))))))))))))))))))))(((((((((((((((((((((((((((((((())))))))))))))))))((((((((((((((((((((

output3

((((((((((((((((((((((((((()))))))))))))))))))))))))))()()()()()()()()()()()()()()()()(())
------------------------------------------------------------------------------------------
)(((((((((((((((((((((((((()))))))))))))))))))))))))))()()()()()()()()()()()()()()()()(())
^----------------------------------------------------^------------------------------------
((((((((((((((((((((((((((()))))))))))))))))))))))))))()()()()()()()()()()()()()()()()(()(
--------------------------------------------------------------------------------------^--^
))))))))))))))))))))(((((((((((((((((((((((((((((((())))))))))))))))))((((((((((((((((((((
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^------------------------------------^^^^^^^^^^^^^^^^^^^^