11605: 【原1605】Brackets Stack
题目
题目描述
author: 2017-data-structure TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1605
Description
模拟一个括号栈，其元素是三种括号()、[]、{}。
给出长为n的操作序列，按序列要求完成以下几种操作：
- push
- pop（栈空则忽略此操作）
- 输出栈顶元素（栈空则忽略此操作）
- 询问当前括号是否匹配（栈空则认为匹配）
Input Format
第1行一个整数n，代表总共有n次操作。
第2~n+1行，每行1个整数，第一个数代表操作种类，对于操作1，在同行给定一个入栈元素。
Output Format
对于每次询问操作，输出一行代表答案。
操作3：输出栈顶元素
操作4：匹配输出“YES”,否则输出“NO”
e.g.
{[()]} 匹配
{[}] 不匹配
Sample Input
6
1 (
1 )
3
4
2
4
Sample Output
)
YES
NO
Limits
对于\(40\%\)的数据，只有前三种操作。
对于\(60\%\)的数据，元素只有小括号。
对于\(80\%\)的数据，n < 1000.
对于\(100\%\)的数据, n < 10^6.
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;
}