1918 후위 표기식

1918 후위 표기식 (c++)

문제

https://www.acmicpc.net/problem/1918

접근 방식

스택, 자료구조

1. 중위 표기식의 수식을 후위 표기식으로 바꾼다.
   1. 문자는 문자열에 바로 추가
   2. 연산자는 스택의 탑 보다 우선순위가 높으면 추가
      1. 높지 않으면 스택을 위에서부터 우선순위가 나보다 높거나 같은 것들을 문자열에 추가
      2. 후 스택에 현재 연사자를 추가
2. 그랬더니 괄호가 문제였다.
   1. 처음엔 재귀형식으로 풀려고 했다.
      1. 괄호가 나오면 해당 괄호와 짝이 되는 닫는 괄호 위치를 파악
      2. 여는 괄호부터 닫는 괄호까지를 다시 함수에 넣어 재귀 진행
   2. 시간초과가 나왔다.
3. 시간초과를 어떻게하면 해결할 수 있을까 (어떻게 재귀 없이 한번의 연산으로 다 처리할 수 있을까)
   1. 지금 골자가 우선순위를 보고 스택에 바로 넣을지 한번 뱉어내고 넣을지를 정하기 때문에 괄호로 우선 순위를 조절할 수 있지 않을까 생각
   2. 연산자는 +, -, *, / 총 4개이므로 각각을 번호로 0,1,2,3 을 매기고
   3. 여는 괄호가 나오면 score+=10, 닫는 괄호가 나오면 score-=10
4. 얼추 굴러가긴 하는데, 정확히 원하는 계산값이 나오지 않았다, 뱉을지 말지 여부를 결정하는 조건이 문제였다.
   1. score가 높다면 (더 안쪽괄호의 연산자라면) 무조건 스택에 삽입
   2. score가 같다면 (같은 괄호에 있는 연산자라면)
      1. /2를 해준다 (덧뺄셈, 곱나눗셈을 구분지어줌)
      2. 스택의 탑이 현재 연산자보다 높거나 같다면 뱉어준다.
         (여기서 문제가 있었다. 높기만 하면 되는 줄 알았는데, 같은 우선순위여도 한번 뱉고 넣어야했다.)
      3. 그 후 스택에 삽입
5. 마지막으로 스택에 남아있는 연산자들도 문자열에 추가해준다.

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <string>
#include <stack>
#include <map>
using namespace std;

inline bool Check(int A, int B) { return (A / 10 > B > 10 || ((A / 10 == B / 10) && (A % 10 / 2 >= B % 10 / 2))); }

string str;
map<char, int> m = { {'+', 0}, {'-', 1}, {'*', 2}, {'/', 3} };
map<int, char> m2 = { {0, '+'}, {1, '-'}, {2, '*'}, {3, '/'} };

string Solve()
{
    string result = "";
    int score = 0;
    stack<int> oStack;

    for (int i = 0; i < str.size(); ++i)
    {
        if (str[i] >= 'A' && str[i] <= 'Z')
        {
            result += str[i];
        }
        else if (str[i] == '(') score += 10;
        else if (str[i] == ')') score -= 10;
        else
        {
            if (!oStack.empty())
            {
                if (Check(oStack.top(), score + m[str[i]]))
                {
                    while (!oStack.empty() && Check(oStack.top(), score + m[str[i]]))
                    {
                        int now = oStack.top(); oStack.pop();
                        result += m2[now % 10];
                    }
                }
            }

            oStack.push(m[str[i]] + score);
        }
    }

    while (!oStack.empty())
    {
        int now = oStack.top(); oStack.pop();
        result += m2[(now % 10)];
    }

    return result;
}

int main()
{
    cin >> str;

    str = Solve();

    cout << str << '\n';

    return 0;
}

다시 생각해 볼 점

1. 이것도 거의 1시간 반을 잡아먹은 것 같다.
2. 1시간 넘어갈즘 문제 분류를 봤지만 별다른 힌트가 될만한 건 없었다.
3. 그래도 일단 괄호를 재귀로 해결해보려고 하고, 시간초과가 났을 때 더 시간효율이 높은 방법으로 괄호에 점수를 부여해보면 어떨까 생각했던 점은 잘한 것 같다.
4. 이런 전위 중위 후위 표기 (혹은 순회)는 스택과 관련이 깊다는 걸 염두해둬야겠다.