후위 표기식 1918

문제

접근 방법

피연산자는 그대로 붙여주고 연산자는 후입 선출의 방식으로 출력되니 스택을 활용해주면 된다.
A+B+C를 후위 표기식으로 표기하면 어떻게 될까?
AB+C+일 것이다.
A*B*C=AB*C*
A+B*C=ABC*+
A*B+C=AB*C+
스택에 존재하는 연산자가 집어넣으려는 연산자보다 높거나 같으면 빼주면 된다.

괄호는 다른 영역이라고 생각하면 된다. (이 나왔다면 스택에 집어넣어 준다. 이후 )이 나올 때까지 똑같이 작동하다가 )이 나오면 (이 나올 때까지 스택에서 빼주면 된다.

코드

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
    stack<char> opStack;
    string infix, postfix = "";
    cin >> infix;
    for (char c : infix)
    {
        if (c >= 'A' && c <= 'Z')
        {
            postfix += c;
        }
        else if ((c == '+' || c == '-'))
        {
            while (!opStack.empty())
            {
                if (opStack.top() == '(')
                    break;
                postfix += opStack.top();
                opStack.pop();
            }
            opStack.push(c);
        }
        else if ((c == '*' || c == '/'))
        {
            if (!opStack.empty() && (opStack.top() == '*' || opStack.top() == '/'))
            {
                postfix += opStack.top();
                opStack.pop();
            }
            opStack.push(c);
        }
        else if (c == ')')
        {
            while (!opStack.empty())
            {
                if (opStack.top() == '(')
                {
                    opStack.pop();
                    break;
                }
                postfix += opStack.top();
                opStack.pop();
            }
        }
        else
        {
            opStack.push(c);
        }
    }
    while (!opStack.empty())
    {
        postfix += opStack.top();
        opStack.pop();
    }
    cout << postfix;
    return 0;
}

풀이

A~Z 사이의 값은 문자열에 추가해주면 된다.

+ 또는 -인 경우 스택에 있는 값을 모두 빼주고 집어넣어 준다. (스택에 있는 값이 무조건 +, -보다 높거나 같은 우선순위이다.)

* 또는 /인 경우 같은 경우만 If 문으로 체크해준다. (While 문이 아닌 이유는 스택에 있는 값은 낮거나 같은 우선순위인데 pop 해줘야 할 같은 우선순위가 여러 번 반복될 순 없기 때문이다.)

)인 경우 (이 나올 때까지 pop 해준다.