2504번 - 괄호의 값
#include<iostream>#include<stdio.h>#include<string>using namespace std;typedef struct node {char data;int val = 0;struct node* nextNode;}Node;class Stack {private:Node* top;Node* bottom;int count = 0;public:static bool identifier(char data) { if (data == '(' || data == ')' || data == '[' || data == ']') return true; else return false;}void pushval(int data) {Node* item = new Node; item->data = '\\';item->val = data; if (bottom == nullptr && top == nullptr) { bottom = item; } else { item->nextNode = top; } top = item; count++;
}void push(char data) { Node* item = new Node; item->data = data; if (bottom == nullptr && top == nullptr) { bottom = item; } else { item->nextNode = top; } top = item; count++;}char pop() { if (count == 0) { return -1; } else {int res = top->data;if(res == '\\') res = top->val; top = top->nextNode; count -= 1; return res; }}int size() { return count;}int empty() { if (count > 0) return 0; else return 1;}char Top() { if (count > 0) return top->data; else return -1;}void clear() { top = nullptr; bottom = nullptr; count = 0;}};int main() {int n, i, pos = 0, anspos = 0;string input;cin >> input;Stack stack;bool isOK = true;int small = 0, large = 0;for (i = 0; i < input.length(); i++) { if (input[i] == '(' || input[i] == '[') { if (input[i] == '(') small += 1; else large += 1; stack.push(input[i]); } else if (input[i] == ')') { if (small == 0) { isOK = false; break; } small -= 1; int num = 0; while (stack.Top() != '(') { if (!stack.identifier(stack.Top())) num += stack.pop(); else { isOK = false; break; }
} stack.pop(); if (num != 0) stack.pushval(2 * num); else stack.pushval(2); } else if (input[i] == ']') { if (large == 0) { isOK = false; break; } large -= 1; int num = 0; while (stack.Top() != '[') { if (!stack.identifier(stack.Top())) num += stack.pop(); else { isOK = false; break; }
} stack.pop(); if (num != 0) stack.pushval(3 * num); else stack.pushval(3); }}if (!isOK) { cout << "0" << endl; return 0;}int sum = 0;while (!stack.empty()) { if (stack.identifier(stack.Top())) { sum = 0; break; } else { sum += stack.pop(); }}cout << sum << endl;}
10%도 못넘기고 틀려보네요 막 집어넣어도 다 맞는것 같은데.. 반례 찾아주실 분 있으신가요?
댓글을 작성하려면 로그인해야 합니다.
superl3 5년 전
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
typedef struct node {
char data;
int val = 0;
struct node* nextNode;
}Node;
class Stack {
private:
Node* top;
Node* bottom;
int count = 0;
public:
static bool identifier(char data) {
if (data == '(' || data == ')' || data == '[' || data == ']')
return true;
else
return false;
}
void pushval(int data) {
Node* item = new Node;
item->data = '\\';
item->val = data;
if (bottom == nullptr && top == nullptr) {
bottom = item;
}
else {
item->nextNode = top;
}
top = item;
count++;
}
void push(char data) {
Node* item = new Node;
item->data = data;
if (bottom == nullptr && top == nullptr) {
bottom = item;
}
else {
item->nextNode = top;
}
top = item;
count++;
}
char pop() {
if (count == 0)
{
return -1;
}
else {
int res = top->data;
if(res == '\\')
res = top->val;
top = top->nextNode;
count -= 1;
return res;
}
}
int size() {
return count;
}
int empty() {
if (count > 0) return 0;
else
return 1;
}
char Top() {
if (count > 0)
return top->data;
else
return -1;
}
void clear() {
top = nullptr;
bottom = nullptr;
count = 0;
}
};
int main() {
int n, i, pos = 0, anspos = 0;
string input;
cin >> input;
Stack stack;
bool isOK = true;
int small = 0, large = 0;
for (i = 0; i < input.length(); i++) {
if (input[i] == '(' || input[i] == '[') {
if (input[i] == '(')
small += 1;
else
large += 1;
stack.push(input[i]);
}
else if (input[i] == ')') {
if (small == 0) {
isOK = false;
break;
}
small -= 1;
int num = 0;
while (stack.Top() != '(') {
if (!stack.identifier(stack.Top()))
num += stack.pop();
else {
isOK = false;
break;
}
}
stack.pop();
if (num != 0)
stack.pushval(2 * num);
else
stack.pushval(2);
}
else if (input[i] == ']') {
if (large == 0) {
isOK = false;
break;
}
large -= 1;
int num = 0;
while (stack.Top() != '[') {
if (!stack.identifier(stack.Top()))
num += stack.pop();
else {
isOK = false;
break;
}
}
연습하는김에 스택도 구현해서 조금 소스가 복잡합니다만..stack.pop();
if (num != 0)
stack.pushval(3 * num);
else
stack.pushval(3);
}
}
if (!isOK) {
cout << "0" << endl;
return 0;
}
int sum = 0;
while (!stack.empty()) {
if (stack.identifier(stack.Top())) {
sum = 0;
break;
}
else {
sum += stack.pop();
}
}
cout << sum << endl;
}
10%도 못넘기고 틀려보네요 막 집어넣어도 다 맞는것 같은데.. 반례 찾아주실 분 있으신가요?