[C++] 문자열 계산기

참고자료 : https://www.swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AV184uV6I70CFAZN

어느 회사 오프라인 코딩 테스트 문제로 문자열 계산기가 나왔었다.

중위표기를 후위표기법로 바꿔서 풀면 풀린다는 개념은 알고 있었지만 당시엔 제대로 생각이 안나서 시간만 허비했었다....

시험은 이미 끝났지만 그래도 다시 한번 풀어보기로 했다.

사칙연산을 할 때 연산 우선 순위는 다음과 같다.

1. 괄호를 먼저 계산하라.

2. 곱셈 또는 나눗셈

3. 덧셈 또는 뺄셈

하지만, 이는 사람이 쉽게 이해할 수 있는 형태의 논리이며 컴퓨터가 이해할 수 있는 논리로 바꾸면 다음과 같다.

- Step1. 중위 표기법 수식을 후위 표기법 수식으로 변환하기 -

1. 입력 값이 피연산자이면 출력

2. 입력 값이 연산자일 경우

 - 스택에 있는 top 값보다 연산자 우선순위가 높으면 push

 - 스택에 있는 top 값보다 연산자 우선순위가 높지 않으면 우선순위가 높아질 때까지 pop하여 출력 후 자기 자신을 push

3. 입력 값이 괄호일 경우

 - ( 의 경우는 stack에 push 하고 연산자 우선 순위를 최하위로 둠 (괄호 위에 연산자가 쌓일 수 있게 하기 위해)

 - ) 의 경우 stack에서 ( 를 만날 때까지 pop 하여 출력

4. 후위표기 형태로 변환 완료

5. stack을 pop 하면서 연산

- Step2. 후위 표기법 수식을 스택으로 계산하기 -

1. 숫자를 만났을 경우 숫자 스택에 push

2. 연산자를 만났을 경우 스택에서 숫자를 2개 pop 하여 연산하고 다시 숫자 스택에 push

3. 모든 연산이 끝나면 남은 스택의 원소는 하나가 되며 그게 정답이 된다.

이러한 원리에 따라 구현하면 문자열 계산기를 풀이할 수 있다.

다만, Step1과 Step2를 굳이 따로 나눠서 할 필요 없이 숫자 스택, 연산자 스택을 각각 별도로 만들어서 풀이를 해도 된다.

괄호를 기준으로 연산자의 우선 순위가 정해지기 때문에 ( 를 만난 이후 )를 만났을 때 바로바로 연산을 해도 된다.

어짜피 이 방법이나 저 방법이나 똑같이 후위순회 계산 방식이므로 큰 차이는 없다.

이 경우는 아래와 같은 방법으로 연산할 수 있다.

- 숫자와 연산자를 따로 구분하여 계산하기 -

1. 숫자를 만났을 경우 숫자 스택에 push

2. 연산자를 만났을 경우

 - 연산자 스택에 있는 top 값보다 우선순위가 높으면 push

 - 연산자 스택에 있는 top 값보다 우선순위가 높지 않으면 우선 순위가 높아질 때까지 pop 하면서 계산

 - 계산을 할 때는 숫자 스택에서 2개의 원소를 pop 하여 계산한 후 그 결과를 다시 숫자 스택에 push

3. 괄호를 만났을 경우

 - ( 의 경우는 stack에 push 하고 연산자 우선 순위를 최하위로 둠 (괄호 위에 연산자가 쌓일 수 있게 하기 위해)

 - ) 의 경우 stack에서 ( 를 만날 때까지 pop 하면서 계산

4. 입력이 다 끝났을 경우 스택에 남아있는 모든 연산자를 pop 하면서 계산

"15 + 32 * ( 1 - 8 ) / 2" 의 계산 결과는 다음과 같다.

모든 과정을 자세히 보려면 클릭

↓↓↓

// String Calculator
#include <iostream>
#include <string>
#include <stack>
#include <sstream>
 
using namespace std;
 
struct oper{
    int p; // 연산자 우선순위
    string o; // 연산자
};
 
stack<int> num; // 숫자 스택
stack<oper> op; // 연산자 스택
 
void calc() {
    int a, b, result;
    b = num.top();
    num.pop();
    a = num.top();
    num.pop();
    string oper = op.top().o;
    op.pop();
 
    if (oper == "*")
        result =  a * b;
    else if (oper == "/")
        result = a / b;
    else if (oper == "+")
        result = a + b;
    else if (oper == "-")
        result = a - b;
    // 결과 값 스택에 다시 저장
    num.push(result);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    string input = "15 + 32 * ( 1 - 8 ) / 2"; // -97
    stringstream ss(input);
 
    // 연산자 우선순위에 따라 스택에 push
    // 0 : ( )
    // 1 : + -
    // 2 : * /
    string tok;
    while (ss >> tok) {
        // ( 는 무조건 연산자 스택에 push
        if (tok == "(") {
            op.push({0, tok});
        } // ) 가 나오면 ( 가 나올 때 까지 계산
        else if (tok == ")") {
            while (op.top().o != "(")
                calc();
            op.pop();
        }
        else if (tok == "*" || tok == "/" || tok == "+" || tok == "-") {
            int prior; // 연산자 우선순위
            if(tok == "*")
                prior = 2;
            else if(tok == "/")
                prior = 2;
            else if(tok == "+")
                prior = 1;
            else if(tok == "-")
                prior = 1;
 
            // 연산자 우선 순위 낮은게 top으로 올 때까지 계산
            while (!op.empty() && prior <= op.top().p)
                calc();
            // 스택에 연산자 push
            op.push({prior, tok});
        }
        else // 숫자일 경우 숫자 스택에 push
            num.push(stoi(tok));
    }
    // 남은 연산자 계산
    while (!op.empty())
        calc();
 
    cout << num.top();
 
    return 0;
}