SW Expert 1224. [S/W 문제해결 기본] 6일차 - 계산기3(D4)

문제 출처 : SW Expert

SW Expert Academy

 

Q. 덧셈, 곱셈, 괄호 연산으로 구성된 식이 주어졌을 때, 후위식으로 변환하여 계산하는 프로그램을 작성하시오.

이 문제는 저번 문제에서 괄호 연산이 추가된 문제에요. 따라서 기본 방향은 같고 괄호 연산에 대한 케이스를 추가하는 방향으로 문제를 해결했습니다.

추가된 케이스는 1. 기본 괄호 연산(중첩 포함) 2. 곱하기 연산 뒤에 괄호가 나오는 것, 이 두 가지로 설정했습니다.

 

1. 기본 괄호 연산 해결 방향

기존 문제의 더하기 연산은 더하기 연산의 개수 만큼 후위식으로 변환할 때, 마지막에 추가하는 방향이었죠. 

괄호 안에 더하기 연산도 같은 방향으로 생각했어요. 그 괄호에 해당하는 더하기 연산을 괄호가 끝날 때, 추가해주는 것이죠. 

중첩괄호 일때, 따로 케이스를 나누지 않더라도 위의 방법으로 해결가능합니다.

 

2. 곱하기 연산 뒤에 괄호

이 케이스는 괄호마다 곱하기 연산의 피연산자인지 구별할 수 있는 check flag를 두었습니다.

check flag가 1이면 "* (숫자1 + 숫자2)" => "숫자1숫자2+*" 처럼 괄호가 끝날 때, *연산을 추가했습니다.

 

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
 
using namespace std;
 
string s;
 
int num[10000];
int top = 0;
 
int pnum[10000]; // 괄호에 해당하는 더하기 연산의 개수
int mcheck[1000]; // 곱하기 연사의 피연산자로 괄호이면 1, 숫자면 0
int ptop = -1; // 현재 괄호의 번호
 
int main() {
    int T = 10;
    int idx = 0;
 
    while (idx++ < T) {
        int n;
 
        cin >> n;
        cin >> s;
 
        string postfix;
 
        int plus_num = 0; // 본문의 더하기 연산의 개수
        int check = 0; // 곱셈 연산 뒤 괄호일 때를 판단하는 flag
 
        for (int i = 0; i < n; i++) {
            char c = s[i];
 
            if (c >= '0' && c <= '9') { // 숫자일 때, 후위식에 추가
                postfix += c;
            }
 
            else if (c == '+' && check == 0) { // 더하기 일 때, 본문의 더하기 연산 개수 +1
                plus_num++;
            }
 
            else if (c == '+' && check == 1) { // 괄호 안일 때, 그 괄호에 해당하는 더하기 연산 개수 +1
                pnum[ptop]++;
            }
            else if (c == '*') {
                if (s[++i] != '(') { // 곱하기 연산 뒤에 피연산자가 숫자이면 피연산자 먼저 후위식에 추가한다음 곱하기 연산 추가
                    postfix += s[i];
                    postfix += '*';
                }
                else { // 곱하기 연산 뒤에 괄호 일때,
                    check = 1; //flag 1로 바꿔줌
                    ptop++; // 괄호 번호  
                    mcheck[ptop] = 1; 
                }
            }
            else if (c == '(') {
                check = 1; // 괄호 flag 1로 바꿔줌
                ptop++; // 괄호 번호 
            }
            else if (c == ')') {
                if (ptop == 0)
                    check = 0;
                for (int j = 0; j < pnum[ptop]; j++) {
                    postfix += '+';
                }
                pnum[ptop] = 0;
                if (mcheck[ptop] == 1) { // 곱하기 연산의 피연산자로 괄호가 나오면, 후위식으로 변환할 때 나중에 곱하기 연산을 더해줘야함
                    postfix += '*';
                    mcheck[ptop] = 0; // 초기화
                }
                ptop--; // 괄호 리셋
            }
        }
        for (int i = 0; i < plus_num; i++) {
            postfix += '+';
        }
 
        for (int i = 0; i < postfix.size(); i++) { // 후위연산 계산, stack 이용
            char c = postfix[i];
 
            if (c >= '0' && c <= '9') {
                num[top++] = c - '0';
            }
            else if (c == '+') {
                int a = num[--top];
                int b = num[--top];
                int cal = a + b;
                num[top++] = cal;
            }
            else if (c == '*') {
                int a = num[--top];
                int b = num[--top];
                int cal = a * b;
                num[top++] = cal;
            }
        }
        cout << "#" << idx << " " << num[0] << endl;
        
        ptop = -1; //초기화
        top = 0;
        memset(mcheck, 0, sizeof(mcheck));
    }
}

 

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!