본문 바로가기
CS+PS/data structure

[Stack] 스택 - 괄호 짝 검사

by SolaBreeze 2023. 7. 3.

괄호 짝이 맞는지 검사

입력 되는 문자열에 대한 아래 요건을 만족하는 괄호 검사 프로그램을 만드시오.

  • 소괄호“()”, 중괄호“{}”, 대괄호“[]” 의 짝이 맞는지 확인

INPUT

”EOF“를 입력 받을 때까지 문자열을 입력

OUTPUT

괄호 검사 성공 여부에 따라 출력문은 아래와 같고 오류 시 오류가 생긴 문장의 라인,문자까지만 인정

1) 성공 : OK, Line_count : (문장 수), bracket_count : **(괄호 짝 수)**

2) 오류 : Error, Line_count : (문장 수), bracket_count : (괄호 짝 수)

- 아래 main 함수를 참조하여 checkMatching() 함수를 만드시오.

int main(){   

std::string Str,temp;   

while(true){       

std::getline(std::cin,temp);

        if(temp=="EOF")break;

        Str.append(temp);

        Str.append("\n"); 

       std::cin.clear();

    }    checkMatching(Str);

return 0;

}

Sample Input

[ { } [] ( )]

EOF

Sample Output

OK, Line_count : 3, bracket_count : 4

Sample Input

{ } [] ( )

EOF

Sample Output

OK, Line_count : 2, bracket_count : 3

Sample Input

{

EOF

Sample Output

Error, Line_count : 1, bracket_count : 0

 

정답 :

#include <iostream>
#include <string>
// #include "ArrayStack.h"
using namespace std;
 
const int MAX_STACK_SIZE = 20;
 
// inline void error(char *message){
//     cout << message <<endl;
//     exit(1);
// }
 
 
class ArrayStack
{
    int top;    //요소 개수
    int data[MAX_STACK_SIZE]; //요소의 배열
 
public :
    ArrayStack(){top = -1;} //스택의 생성자
    //반환자가 bool 타입이기 때문에 return top==-1일때 True를 반환하고, top!=-1이면 False를 반환한다.
    bool isEmpty(){return top == -1;}
    bool isFull(){return top == MAX_STACK_SIZE-1;}
 
    void push(int e){
        //만약 스택이 가득 찼다면
        // if(isFull()) error ("스택 포화 에러");
        data[++top] =e; //top에 먼저 1 더하고, 그 자리에 새로운 e값 넣기
    }
 
    int pop(){
        // if(isEmpty()) {
        //     error ("EOF");
        // }
        //
        return data[top--];
    }
 
    int peek(){
        // if(isEmpty()) {
        //     error ("EOF");
        // }
        return data[top];
    }
 
    void display(){
        printf("[스택 항목의 수 = %2d] ==> ", top+1);
        for(int i=0; i<=top; i++){
            printf("<%2d>", data[i]);
            printf("\n");
        }
    }
};
 
void checkMatching(string Str, int cnt){
    ArrayStack stack;
    string ans = "OK";
    int a;
    // int lc = 1;
    int bc = 0;
    // char ch;
    a = Str.length();
    for(int i=0; i<a; i++){
        if(Str[i] == '[' || Str[i] =='(' || Str[i] =='{'){
            stack.push(Str[i]);
        }
 
        else if(Str[i] == ']' || Str[i]==')' || Str[i]=='}'){
            if(stack.isEmpty()){
                ans = "Error";
            }
            else{
                int prev = stack.peek();
                if((Str[i] == ']'&& prev !='[')||(Str[i] == ')'&& prev !='(')||(Str[i] == '}'&& prev !='{')){
                    ans = "Error";
                    continue;
                }
                bc++;
                stack.pop();
            }
        }
    }
     
    if (stack.isEmpty()){
        ans = "OK";
    }
    else{
        ans = "Error";
    }
 
    // cout << "괄호개수 : " <<a<<endl;
    cout << ans <<", Line_count : "<< cnt <<", bracket_count : "<<bc<<endl;
 
}
 
int main(){
    string Str,temp;
    int cnt;
    while(true){
        getline(cin,temp);
        if(temp=="EOF")break;
        cnt ++;
        Str.append(temp);
        // Str.append("\n");
        cin.clear();
    }
    // cout << Str << endl;
    checkMatching(Str, cnt);
     
 
    return 0;
}