ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1223.계산기2
    알고리즘/SW Expert Academy 2020. 3. 23. 21:59

    이번에 풀어볼 문제는 SW expert에 있는 계산기2이다.

    계산기1과 달라진 점은 예상했던대로 예외처리가 늘어나  '+' 뿐아니라 '*'도 비교해야 한다는 것이다.

    역시나 예외처리를 잘해주면 쉽게 풀 수 있을 것 같다.

    나는 연산자의 경우 Stack에 넣고 피연산자는 Queue에 넣어서 계산하도록 했다.

    후위계산법의 방식은 다른 블로그에 많으니 참고하면 될 거 같다.

     

    < Code 설명 >

    #include <iostream>
    #include <stack>
    #include <queue>
    
    using namespace std;
    
    
    int main()
    {
        int n;
        for(int k=1; k<=10; k++){ //문제에서 10번의 테스트케이스를 요구함
            cin >> n;
            string str;    // 문자열 입력
            cin >> str;
            stack<char> s; // 연산자 저장공간
            queue<char> q; // 피연산자 및 후위계산식이 완성될 공간
            for(int i=0; i<n; i++){
                if(str[i]=='*'){  // 문자가 '*'일 경우
                    if(s.empty()) // stack이 비어있다면
                        s.push(str[i]); // 그냥 바로 넣는다.
                    else if(s.top()=='+'){ // 문자가 '*'인데 stack 최상위가 '+'인 경우
                        s.push(str[i]);    // '+'보다 '*'가 우선순위가 높으므로 push
                    }
                    else if(s.top()=='*'){ // 문자가'*'인데 stack 최상위도 '*'인 경우
                        q.push(s.top());   // 같은 경우에는 최상위를 queue에 넣고
                        s.pop();           // '*'를 queue에 담았으니 stack에서 제거
                        s.push(str[i]);    // 연산자 '*'를 스택에 넣는다.
                    }
                }
                else if(str[i]=='+'){     //문자가 '+'인 경우
                    if(s.empty())         // stack이 비어있다면
                        s.push(str[i]);   // 그냥 바로 넣는다.
                    else if(s.top()=='*'){ // 문자가 '+'인데 stack 최상위가 '*'인 경우
                        q.push(s.top());   // 우선순위가 낮으므로 '*'를 빼서 queue에 넣음
                        s.pop();           // '*'를 queue로 옮겼으니 stack에서 제거
                        if(!s.empty()){    // stack에서 빼고 나서도 스택이 비어있지 않다면
                            if(s.top()=='*'){ // 그 다음 최상위도 '*'인 경우
                                q.push(s.top()); // 해당 '*'를 queue에 넣는다.
                                s.pop();         // queue로 옮겼으니 stack에서 제거
                            }
                            else if(s.top()=='+'){ // 그 다음 최상위가 '+'라면
                                q.push(s.top()); // '+''+'이므로 최상위는 queue로 옮김
                                s.pop();         // queue로 옮겼으므로 stack에서 제거
                            }
                        }
                        s.push(str[i]);   // 비교한 새로운 연산자니까 stack에 당연히 push 
                    }
                    else if(s.top()=='+'){ // 문자가 '+'인데 stack 최상위도 '+'인 경우
                        q.push(s.top());   // 스택의 최상위 '+'를 queue로 옮긴다.
                        s.pop();           // 우선순위가 같으므로 옮긴후 stack에서 제거
                        s.push(str[i]);    // 비교한 새로운 연산자 '+'를 stack에 push
                    }
                }
                else{                      // 피연산자인 경우
                    q.push(str[i]);        // 바로 queue에 넣는다.
                    if(!s.empty()&&i==n-1){// str 끝까지 비교, stack이 비어있지않다면
                        while(!s.empty()){ // 스택이 빌 때까지
                            q.push(s.top()); // queue에 스택의 연산자를 넣는다.
                            s.pop();         // queue로 옮긴 연산자는 stack에서 제거
                        }
                    }
                }
            }
            stack<int>ans;                  // 정답을 넣을 stack 생성
            int v=0;                        // 정답 만드는걸 도와줄 임시공간
            for(int i=0; i<n; i++){         // queue의 길이는 str의 길이와 같으므로 n
                if(q.front()=='+'){         // queue의 제일 앞이 '+'인 경우
                    ans.pop();              // 이미 v에 값이 저장되어있으므로 stack 제거
                    if(!ans.empty())        // stack이 비어있지 않다면
                        v+=ans.top();       // 아까저장한 임시값에 stack의 최상위값 더함
                    ans.pop();              // stack값을 사용했으므로 필요없음 -> 제거
                    ans.push(v);            // 더하기 계산이 완료된 값 v를 stack에 저장
                    q.pop();                // 다음 queue를 비교하기위해 해당 queue 제거
                }
                else if(q.front()=='*'){    // queue의 제일 앞이 '*'인 경우
                    ans.pop();              // 이미 v에 값이 저장되어있으므로 stack 제거
                    if(!ans.empty())        // stack이 비어있지 않다면
                        v*=ans.top();       // 아까 저장한 임시값에 stack의 최상위값 곱함
                    ans.pop();              // stack 값을 사용했으므로 필요없음 -> 제거
                    ans.push(v);        // 곱하기 계산이 완료된 값 v를 stack에 저장
                    q.pop();            // 다음 queue값을 비교하기위해 해당 queue값 제거
                }
                else {                     // 시작은 무조건 숫자이므로 여기서부터 보면된다.
                    ans.push(q.front()-48);// 해당숫자-48로 문자->숫자로 변환 후 push
                    v=ans.top();       // 스택에 들어간 최상위를 임시 v에 저장
                    q.pop();           // 다음 queue값 비교하기위해 해당 queue값 제거 
                }
            }
            cout << "#" << k << " "<< ans.top() << endl; 
            // 결국 모든계산이 끝난 값이 stack에 최상위로 존재
        }
        return 0;
    }
    

    아직까지 예외를 떠올리는 건 쉽지 않은 것 같다. 

    -> 테스트 케이스들을 이용해서 부족하거나 빼먹은 로직을 추가하면서 구현했다.

    -> 이렇게 테스트 케이스를 이용해서 비교하며 구현하는 것은 좋은 방법은 아닌거 같다..
         그 이유는 이보다 복잡한 로직을 구현할 때 구조가 엉망이 되어 처음부터 짜야할 경우가 생길 수 있기 때문이다.
         처음 구현전에 설계를 조금 더 생각하고 진행하는 능력을 길러야겠다...

     

     

     

    반응형

    '알고리즘 > SW Expert Academy' 카테고리의 다른 글

    1226.미로1 & 1227.미로2  (0) 2020.03.26
    1225. 암호생성기  (0) 2020.03.24
    1224.계산기3  (0) 2020.03.24
    1222.계산기1  (0) 2020.03.23
    1218. 괄호 짝짓기 풀이  (0) 2020.03.04

    댓글

Designed by Tistory.