首页 > ACM题库 > 九度OJ > 九度-1153-括号匹配问题[解题代码]
2013
12-13

九度-1153-括号匹配问题[解题代码]

题目来源:2010年北京大学计算机研究生机试真题

题目描述:

    在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序,找到无法匹配的左括号和右括号,输出原来字符串,并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.

输入:

    输入包括多组数据,每组数据一行,包含一个字符串,只包含左右括号和大小写字母,字符串长度不超过100。
    注意:cin.getline(str,100)最多只能输入99个字符!

输出:

    对每组输出数据,输出两行,第一行包含原始输入字符,第二行由"$","?"和空格组成,"$"和"?"表示与之对应的左括号和右括号不能匹配。

样例输入:
)(rttyy())sss)(
样例输出:
)(rttyy())sss)(
?            ?$

cpp 代码如下:
#include <stdio.h>
#include <stack>
#include <string.h>
using namespace std;
int main(){
	char str[100],out[100];stack<int> s;
	while(scanf("%s",str) != EOF){
		int n = strlen(str);memset(out,' ',sizeof(out));
		for(int i=0; i<n; i++){
			if(str[i] == '('){s.push(i);
			}else if(str[i] == ')'){
				if(s.size() > 0) s.pop();
				else out[i] = '?';}}
		while(s.size() > 0){int k = s.top();s.pop();out[k] = '$';}out[n] = '\0';printf("%s\n%s\n",str,out);}return 0;}
/**************************************************************
	Problem: 1153
	User: coder
	Language: C++
	Result: Accepted
	Time:10 ms
	Memory:1044 kb
****************************************************************/


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?