# 11549: 【原1549】Parentheses Matching Problem

### 题目描述

author: Online Judge 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1549

## Sample Input

``````)(rttyy())sss)(
``````

## Sample Output

``````)(rttyy())sss)(
?            ?\$
``````

## ligongzzz's solution

``````#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;
using pic = pair<int, char>;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

string ch;
while (cin >> ch) {
stack<pic> sdata;
auto length = ch.length();
vector<char> vdata(length, ' ');

for (int i = 0; i < length; ++i) {
if (ch[i] == '(') {
sdata.push(make_pair(i, '('));
}
else if (ch[i] == ')') {
if (!sdata.empty() && sdata.top().second == '(') {
sdata.pop();
}
else{
sdata.push(make_pair(i,')'));
}
}
}

while (!sdata.empty()) {
vdata[sdata.top().first] = sdata.top().second == '(' ? '\$' : '?';
sdata.pop();
}
cout << ch << "\n";
for (auto p : vdata)
cout << p;
cout << "\n";
}

return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char str[110],cha[110];
int point;

int main() {

while (scanf("%s", str) != EOF) {
point = 0;
int len = strlen(str);
for (int i = 0; i < len; ++i) {
cha[i] = ' ';
if (str[i] == '(') ++point;
if (str[i] == ')') {
--point;
if (point < 0) {
point = 0; cha[i] = '?';
}
}
}
point = 0;
for (int i = len - 1; i >= 0; --i) {
if (str[i] == ')') ++point;
if (str[i] == '(') {
--point;
if (point < 0) {
point = 0; cha[i] = '\$';
}
}
}
printf("%s\n%s\n", str, cha);
}
}
``````