题目源自SJTU OJ 1599
模拟一个括号栈,其元素是三种括号()、[]、{}。
给出长为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
#include <iostream>
using namespace std;
char getPair(char c) {
if (c == ')')
return '(';
else if (c == ']')
return '[';
else if (c == '}')
return '{';
else
return '@';
}
bool isMatch(char* seq, int length) {
if (length == 0) {
return true;
}
char* stack = new char[length];
int top = 0;
for (int i = 0; i < length; i++) {
if (top == 0) {
stack[top] = seq[i];
top++;
continue;
}
if (stack[top - 1] == getPair(seq[i])) {
top--;
}
else {
stack[top] = seq[i];
top++;
}
}
delete[] stack;
if (top == 0) {
return true;
}
return false;
}
int main() {
int n = 0, ins = 0;
char op = 0;
scanf(" %i", &n);
// cin >> n;
char* stack = new char[n];
int top = 0;
for (int i = 0; i < n; i++) {
// cin >> ins;
scanf(" %d", &ins);
switch (ins) {
case 1: {
// push
// cin >> op;
scanf(" %c", &op);
stack[top] = op;
top++;
break;
}
case 2: {
// pop
if (top != 0) {
top--;
}
break;
}
case 3: {
// cout << top
if (top != 0) {
// cout << stack[top - 1] << endl;
printf("%c\n", stack[top - 1]);
}
break;
}
case 4: {
// is match?
if (isMatch(stack, top)) {
// cout << "YES" << endl;
printf("YES\n");
}
else
// cout << "NO" << endl;
printf("NO\n");
break;
}
default:
break;
}
}
delete[] stack;
return 0;
}