200108 : 括号匹配问题
描述

在C++中,有内部括号先计算,外部括号后算的原则,正常情况下括号都是按"("在前")"在后的顺序成对出现的,即和数学算式同样的规则。检查一句代码中的括号是否符合以上原则。如果左括号没有匹配的右括号则在其下方输出"<",如果右括号没有匹配的左括号则在其下方输出">"。

输入

一行,一个仅包含大小写英文字母、"("、")"、" "的字符串str

对于100%的数据:

1\le str.size() \le 1\cdot 10^2

输出

第一行,原字符串。

第二行,在第一行不符合规则的括号下方输出"<"或">"。

样例

输入

FUN(MATH(a)))(

输出

FUN(MATH(a)))(
            ><
提示

本题数据非常小,可以直接在字符串上查找左右括号。

如果数据很大,则应预处理之后再进行查找:用两个数组分别记录左括号、右括号的位置,这样可以避免对非括号字符的搜索,而保存左括号的数组是升序的可以再采用二分查找,这样效率将会有极大提升。

语言:
主题: