1223.계산기2

이번에 풀어볼 문제는 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;
}

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

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

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