时间限制：1 秒
内存限制：32 兆
特殊判题：否
题目描述：在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.
输入：输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100。 注意：cin.getline(str,100)最多只能输入99个字符！
输出：对每组输出数据，输出两行，第一行包含原始输入字符，第二行由"$","?"和空格组成，"$"和"?"表示与之对应的左括号和右括号不能匹配。
样例输入： )(rttyy())sss)( 样例输出： )(rttyy())sss)( ? ?$ 来源： 2010年北京大学计算机研究生机试真题 #include <stdio.h> #define M 100 int stack[M]; int top; int push(int x) //定义入栈操作 { if (top == M) return 0; stack[top] = x; top ++; return 1; } int pop(int *x) //定义出栈操作 { if (top == 0) return 0; top --; *x = stack[top]; return 1; } int main(void) { int x, i; char s[M+1], s2[M+1]; while (scanf("%s", s) != EOF) //输入字符串 { top = 0; for(i=0; s[i]; i++) //从左到右遍历字符串 { if (s[i] == '(') //若遇到左括号 { push(i); //将其数组下标放入堆栈中 s2[i] = ' '; //将对应的输出字符串位置改为空格 } else if (s[i] == ')') //若遇到右括号 { if ( !pop(&x) ) //若堆栈为空，则无法找到左括号与其匹配 s2[i] = '?'; //修改输出中该位置为“？” else s2[i] = ' ';//若堆栈非空，修改输出中该位置为空格 } else s2[i] = ' '; //若其为其他字符，与括号匹配无关，则修改输出为空格 } s2[i] = '\0'; while (top) { pop(&x); s2[x] = '$'; //当字符串遍历完成时，尚留在堆栈中的左括号无法匹配，修改输出为“$” } printf("%s\n", s); //输出原字符串 printf("%s\n", s2); //输出答案字符串 } return 0; } /************************************************************** Problem: 1153 User: zpy Language: C Result: Accepted Time:0 ms Memory:912 kb ****************************************************************/