# 11605: 【原1605】Brackets Stack

### 题目描述

author: 2017-data-structure TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1605

# Description

1. push
2. pop（栈空则忽略此操作）
3. 输出栈顶元素（栈空则忽略此操作）
4. 询问当前括号是否匹配（栈空则认为匹配）

e.g.

{[()]} 匹配

{[}] 不匹配

## Sample Input

``````6
1 (
1 )
3
4
2
4
``````

## Sample Output

``````)
YES
NO
``````

## FineArtz's solution

``````/* Brackets Stack */
#include <iostream>
using namespace std;

char full[1000005], inco[1000005];
bool isco[1000005] = {0};
int n, fsize = 0, isize = 0;

bool isLeft(char ch){
return (ch == '(' || ch == '[' || ch == '{');
}

char getRight(char ch){
if (ch == '(') return ')';
else if (ch == '[') return ']';
else if (ch == '{') return '}';
else return ' ';
}

char getLeft(char ch){
if (ch == ')') return '(';
else if (ch == ']') return '[';
else if (ch == '}') return '{';
else return ' ';
}

int main(){
ios::sync_with_stdio(false);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
while (n--){
int op;
char ch;
cin >> op;
switch(op){
case 1:
cin >> ch;
full[fsize++] = ch;
if (isLeft(ch)){
inco[isize++] = ch;
isco[fsize - 1] = true;
}
else{
if (isize != 0 && isLeft(inco[isize - 1]) && ch == getRight(inco[isize - 1])){
--isize;
isco[fsize - 1] = true;
}
else{
inco[isize++] = ch;
isco[fsize - 1] = false;
}
}
break;
case 2:
if (fsize == 0)
break;
ch = full[fsize - 1];
if (isLeft(ch))
--isize;
else{
if (isco[fsize - 1])
inco[isize++] = getLeft(ch);
else
--isize;
}
--fsize;
break;
case 3:
if (fsize != 0)
cout << full[fsize - 1] << '\n';
break;
case 4:
if (isize)
cout << "NO\n";
else
cout << "YES\n";
break;
}
}
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
using namespace std;

constexpr auto maxNum = 1000000;

class myStack {
int num = 0, acNum = 0;
char data[maxNum] = { 0 };
bool flag[maxNum] = { 0 };
char ac[maxNum] = { 0 };
public:
void push(char b) {
if (b == '(' || b == '[' || b == '{')
ac[acNum++] = b;
else if (b == ')'&&acNum > 0 && ac[acNum - 1] == '(') {
acNum--;
flag[num] = true;
}
else if (b == ']'&&acNum > 0 && ac[acNum - 1] == '[') {
acNum--;
flag[num] = true;
}
else if (b == '}'&&acNum > 0 && ac[acNum - 1] == '{') {
acNum--;
flag[num] = true;
}
else
ac[acNum++] = b;
data[num++] = b;
}
bool empty() {
return num == 0;
}
char pop() {
if (num == 0)
return  0;
num--;
char temp = data[num];
data[num] = 0;

//回退
if (flag[num]) {
if (temp == ')')
ac[acNum++] = '(';
else if (temp == ']')
ac[acNum++] = '[';
else if (temp == '}')
ac[acNum++] = '{';
}
else
acNum--;
flag[num] = false;
return temp;
}
char back() {
if (num == 0)
return 0;
return data[num - 1];
}
bool match() {
return acNum == 0;
}
};

int main() {
int num;
myStack data;
cin >> num;
for (int i = 0; i < num; i++) {
int temp;
scanf("%d", &temp);
if (temp == 1) {
char c;
scanf(" %c", &c);
data.push(c);
}
else if (temp == 2) {
data.pop();
}
else if (temp == 3) {
if (!data.empty())
printf("%c\n", data.back());
}
else if (temp == 4) {
if (data.match())
printf("YES\n");
else
printf("NO\n");
}
}

return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

char input1[1001000], save[1001000];

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

int N, choice, inputCount = 0, saveCount = 0, wrong = 0;
char ch;

cin >> N;
for (int i = 0; i < N; i++) {
cin >> choice;

if (choice == 1) {
cin >> ch;
input1[++inputCount] = ch;
if (wrong) {  //如果已经有问题就直接跳过下面的部分
continue;
} else if (ch == ')' || ch == ']' || ch == '}') {
if ((saveCount == 0) || (ch == ')' && save[saveCount] != '(') ||
(ch == ']' && save[saveCount] != '[') ||
(ch == '}' && save[saveCount] != '{')) {
wrong = inputCount;  //记录下有问题的位置
} else {  //如果新输入的和之前的左括号配对了，就直接把第二个栈的左括号删去
saveCount--;
}
} else {  //如果输入进来的是左括号，就直接将其存入第二个栈
save[++saveCount] = ch;
}
} else if (choice == 2) {
if (inputCount) {
if (wrong) {
inputCount--;
if (wrong >
inputCount) {  //如果有问题的部分已经被pop，则直接重置错误位置
wrong = 0;
}
} else {
if (input1[inputCount] == '(' ||
input1[inputCount] == '[' ||
input1[inputCount] == '{') {
saveCount--;
} else if (input1[inputCount] == ')') {
save[++saveCount] = '(';
} else if (input1[inputCount] == ']') {
save[++saveCount] = '[';
} else if (input1[inputCount] == '}') {
save[++saveCount] = '{';
}
inputCount--;
}
}
} else if (choice == 3) {
if (inputCount) {
cout << input1[inputCount] << '\n';
}
} else if (choice == 4) {
if (wrong == 0 &&
saveCount == 0) {  //没有错误同时第二个栈没东西了才输出YES
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
#include <cstdio>
using namespace std;
char rstack[1000001],istack[1000001],c;
int rtop,itop,n,x;
bool match[1000001];
void push(char c){
if (rstack[rtop-1]=='('&&c==')') {
rtop--;
match[itop]=true;
}
else if (rstack[rtop-1]=='['&&c==']') {
rtop--;
match[itop]=true;
}

else if (rstack[rtop-1]=='{'&&c=='}') {
rtop--;
match[itop]=true;
}
else rstack[rtop++]=c;
}
void raw_push(char c){
if (rstack[rtop-1]=='('&&c==')') rtop--;
else if (rstack[rtop-1]=='['&&c==']') rtop--;
else if (rstack[rtop-1]=='{'&&c=='}') rtop--;
else rstack[rtop++]=c;
}
void pop(){
switch (istack[itop-1]) {
case '(':
raw_push(')');
break;
case ')':
if (match[itop-1]) {raw_push('('); match[itop-1]=false;}
else rtop--;
break;
case '[':
raw_push(']');
break;
case ']':
if (match[itop-1]) {raw_push('['); match[itop-1]=false;}
else rtop--;
break;
case '{':
raw_push('}');
break;
case '}':
if (match[itop-1]) {raw_push('{'); match[itop-1]=false;}
else rtop--;
break;
}
itop--;
}
int main() {
scanf("%d",&n);
for (int i=0;i<n;++i)
{
scanf("%d",&x);
if (x==1){
scanf(" %c",&c);
push(c);
istack[itop++]=c;
}
if (x==2&&itop>=1) pop();
if (x==3&&itop>=1) printf("%c\n",istack[itop-1]);
if (x==4){
if (!rtop) printf("YES\n");
else printf("NO\n");}
}
return 0;
}
``````