題目描述
在某個字符串（長度不超過100）中有左括號、右括號和大小寫字母；規定（與常見的算數式子一樣）任何一個左括號都從內到外與在它右邊且距離最近的右括號匹配。寫一個程序，找到無法匹配的左括號和右括號，輸出原來字符串，並在下一行標出不能匹配的括號。不能匹配的左括號用"$"標注,不能匹配的右括號用"?"標注。
輸入
輸入包括多組數據，每組數據一行，包含一個字符串，只包含左右括號和大小寫字母，字符串長度不超過100。
注意：cin.getline(str,100)最多只能輸入99個字符！
輸出
對每組輸出數據，輸出兩行，第一行包含原始輸入字符，第二行由"$","?"和空格組成，"$"和"?"表示與之對應的左括號和右括號不能匹配。
樣例輸入
bge)))))))))
((IIII))))))
()()()()(uuu
))))UUUU((()
樣例輸出
bge)))))))))
?????????
((IIII))))))
????
()()()()(uuu
$
))))UUUU((()
???? $$
提示 [+]
*** 提示已隱藏，點擊上方 [+] 可顯示 ***
來源
2010年北京大學計算機研究生機試真題
【思路】：
[cpp]
/*********************************
* 日期：2013-3-15
* 作者：SJF0115
* 題號: 天勤OJ 題目1072: 括號匹配問題
* 來源：http://www.acmclub.com/problem.php?id=1072
* 結果：AC
* 來源：2010年北京大學計算機研究生機試真題
* 總結：
**********************************/
#include<stdio.h>
#include<iostream>
#include<stack>
#include<string.h>
using namespace std;
int main(){
int i;
char str[101],Mark[101];
while(scanf("%s",str) != EOF){
stack<char> S;
for(i = 0;i < strlen(str);i++){
//如果是'('則入棧
if(str[i] == '('){
//將數組下表暫存在棧中
S.push(i);
//對應輸出字符串暫且為' '
Mark[i] = ' ';
}
else if(str[i] == ')'){
//如果沒有'('相匹配
if(S.empty()){
//對應輸出字符串改為'?'
Mark[i] = '?';
}
//有'('相匹配
else{
//對應輸出字符串改為' '
Mark[i] = ' ';
//棧頂位置左括號與其匹配，彈出已經匹配的左括號
S.pop();
}
}
//其他字符需許考慮,與括號無關
else{
Mark[i] = ' ';
}
}//for
//若棧非空，則有沒有匹配的左括號
while(!S.empty()){
//對應輸出字符串改為'$'
Mark[S.top()] = '$';
S.pop();
}
Mark[i] = '\0';
//輸出
puts(str);
puts(Mark);
}
return 0;
}
/*********************************
* 日期：2013-3-15
* 作者：SJF0115
* 題號: 天勤OJ 題目1072: 括號匹配問題
* 來源：http://www.acmclub.com/problem.php?id=1072
* 結果：AC
* 來源：2010年北京大學計算機研究生機試真題
* 總結：
**********************************/
#include<stdio.h>
#include<iostream>
#include<stack>
#include<string.h>
using namespace std;
int main(){
int i;
char str[101],Mark[101];
while(scanf("%s",str) != EOF){
stack<char> S;
for(i = 0;i < strlen(str);i++){
//如果是'('則入棧
if(str[i] == '('){
//將數組下表暫存在棧中
S.push(i);
//對應輸出字符串暫且為' '
Mark[i] = ' ';
}
else if(str[i] == ')'){
//如果沒有'('相匹配
if(S.empty()){
//對應輸出字符串改為'?'
Mark[i] = '?';
}
//有'('相匹配
else{
//對應輸出字符串改為' '
Mark[i] = ' ';
//棧頂位置左括號與其匹配，彈出已經匹配的左括號
S.pop();
}
}
//其他字符需許考慮,與括號無關
else{
Mark[i] = ' ';
}
}//for
//若棧非空，則有沒有匹配的左括號
while(!S.empty()){
//對應輸出字符串改為'$'
Mark[S.top()] = '$';
S.pop();
}
Mark[i] = '\0';
//輸出
puts(str);
puts(Mark);
}
return 0;
}
