티스토리 뷰

https://www.acmicpc.net/problem/4949

 

4949번: 균형잡힌 세상

문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단

www.acmicpc.net

스택 C++ (2011 ICPC japan)

괄호가 섞인 문자열이 주어지고 괄호가 균형이 맞는지 조사하는 문제

(, [ 가 입력되면 stack에 push하고 ), ]가 입력되면 stack에서 pop한 값이 짝이 맞는지 검사한다.

이때 짝이 맞지 않으면 균형잡힌 문자열이 아닌걸로 판단하고 결과를 출력하고

또 마지막에 stack이 비어있지 않으면 균형잡힌 문자열이 아닌걸로 판단하고 출력한다.

 

소스코드

#include <iostream>
#include <cstring>
using namespace std;
class Stack{
public:
    int size;
    char* stack;
    Stack(){
        size = 0;
        stack = new char[101];
    }
    void push(char ch){
        stack[size++] = ch;
    }
    char pop(){
        if(isEmpty()){
            return -1;
        }
        else{
            return stack[--size];
        }
    }
    int getSize(){
        return size;
    }
    bool isEmpty(){
        if(size == 0)
            return true;
        else
            return false;
    }
    char top(){
        if(isEmpty()){
            return -1;
        }
        else{
            return stack[size-1];
        }
    }
};
int main(){
    string cstr;
    bool isVPS;
    while(1){
        isVPS = true;
        Stack s = Stack();
        getline(cin, cstr);
        if(cstr[0] == '.')
            break;
        for(int i = 0 ; i < cstr.size() ; i++){
            if(cstr[i] == '(' || cstr[i] == '['){
                s.push(cstr[i]);
            }
            else if(cstr[i] == ')'){
                if(s.pop() != '('){
                    isVPS = false;
                    break;
                }
            }
            else if(cstr[i] == ']'){
                if(s.pop() != '['){
                    isVPS = false;
                    break;
                }
            }
        }
        
        if(!s.isEmpty())
            isVPS = false;
        if(isVPS)
            cout << "yes\n";
        else
            cout << "no\n";
    }
    return 0;
}
댓글
댓글쓰기 폼