[ICPC] Parentheses

백준 16362번으로 풀어본 icpc 예선 문제

 

예전에 인턴 프로젝트 할 때 코드 tokenizer 만들면서 lex,yacc 쓰기 전에 아무것도 모르고 손수 코드를 작성한 적이 있었는데

그 생각하면서 코드 그냥 노가다로 작성해보았다

분명 재귀로 예쁘게 짤 수 있을 것 같은데 막상 짜려니까 코드가 잘 안나왔다ㅠㅠ

 

#include <iostream>
#include <string>
#include <stack>
#include <set>
 
using namespace std;
stack<char> st;
 
int count(string command,char token){
    int c = 0;
    int len = command.length();
    for(int i = 0 ; i < len ; i++){
        if(command[i]==token) c++;
    }
    return c;
}
 
int main(){
    set<char> op;
    op.insert('+');
    op.insert('-');
    op.insert('*');
    op.insert('/');
    op.insert('%');
 
    string command;
    getline(cin,command);
    int len = command.length();
 
    // (,) 개수가 다르면 무조건 error
    if(count(command,'(')!=count(command,')')){
        cout << "error\n";
        return 0;
    }
    bool improper = false;
    
    for(int i = 0 ; i < len ; i++){
        while(i < len && command[i]== ' '){
            i++;
        }
 
        if(i>=len) break;
 
        if(command[i]=='(') { 
            // (인 경우
            // ( 앞에 올 수 있는 것은 (와 연산자
            // 변수가 있는 경우에는 error
            if(!st.empty() && st.top() == 's'){
                cout << "error\n";
                return 0;
            }
            st.push('(');
        }
        else if(op.find(command[i]) != op.end()){
            // 연산자인 경우
            // 연산자 앞에 올 수 있는 것은 변수
            // 변수가 아닌 경우는 error
            // )도 가능한 경우지만 stack에 )는 애초에 넣지 않는다
            if(st.top()!='s'){ 
                cout << "error\n";
                return 0;
            }
            else st.push('o');
        }
        else if(command[i]==')'){
            // )인 경우
            // )앞에 올 수 있는 것은 변수
            // 변수가 아닌 연산자나 (가 있는 경우는 error
 
            if(st.empty() || st.top()!='s'){
                cout << "error\n";
                return 0;
            }
            st.pop();
 
            // 변수가 있는 것은 확인
            // (를 만날때까지 error, improper의 경우가 생기는지 확인
 
            bool opTurn = true;
            int cnt=0;
            while(!st.empty()){
                if(opTurn){
                    if(st.top()=='o') cnt++;
                    else if(st.top()=='('){
                        if(cnt!=1) improper = true;
                        break;
                    }
                    opTurn = false;
                }
                else{
                    if(st.top()!='s'){
                        cout << "error\n";
                        return 0;
                    }
                    opTurn = true;
                }
                st.pop();
            }
 
            // (s (o s )* )를 하나의 변수로 대치
            // proper하지 않은 경우는 따로 improper 변수에 체크
            st.pop();
            st.push('s');
        }else{
            // 변수인 경우
            // 변수 앞에 올 수 있는 것은 (나 연산자
            // )은 불가능 하지만 stack에 push X
            if(st.empty() || st.top()!='s') st.push('s');
            else{
                cout << "error\n";
                return 0;
            }
        }
    }
    if(improper){
        cout << "improper\n";
        return 0;
    }
 
    bool strTurn = true;
    int cnt = 0;
    while(!st.empty()){
        if(strTurn){
            if(st.top()!='s'){
                cout << "error\n";
                return 0;
            }
            st.pop();
            strTurn = false;
        }
        else{
            if(st.top()!='o'){
                cout << "error\n";
                return 0;
            }
            st.pop();
            strTurn = true;
            cnt++;
        }
    }
    if(cnt==1) cout << "proper\n";
    else cout << "improper\n";
    return 0;
}

 

알고리즘 코드가 150줄이나 나오다니ㅋㅋㅋ

먼저 입력을 받을 때 공백 단위로 나누면 안되니까 getline을 사용해주었다

그 후 공백은 무시하고 변수(s), 연산자(o), (, )로 나누어 stack에 변화를 주었다

각 입력이 어떤 상황에서 오면 안되는지와 improper인 경우를 체크해주었다

에러인 경우는 바로 에러 출력 후 종료해주었고

improper인 경우는 improper라도 후에 error의 경우가 생기면 error라고 해야하니까 바로 출력은 안하고 저장만 해주었다

improper를 알아내는 경우는 a + b + c와 같이 틀린 문장은 아니지만 연산자가 proper인 경우보다 많은 경우를 체크해주었다

(가 입력으로 들어온 경우 미리 저장된 연산자와 변수 순서대로 스택에서 pop을 하지만 개수가 맞지 않으면 체크해주고 ( a + ... b ) 이 꼴 전체를 하나의 operand로 바꾸어주었다

 

생각하기도 쉬웠고 코드 작성도 어렵지 않았지만 찝찝함이 남은 문제..