https://www.acmicpc.net/problem/1918
해당 문제는 후위 표기식에 관한 문제이다.
후위 표기식에 대한 규칙을 알고 있다면 생각보다는 쉽게 풀릴수도..?
먼저 후위 표기식에 대한 규칙을 설명해보겠다
1.당연히 사칙연산에 관해서는 +와 -보다는 * 와 / 가 먼저 나와야 한다. (우선순위 " +,- "< " * / " < " () "
2.해당 연산자가 이미 존재하는 연산자이며, 자신보다 우선순위가 낮지 않다면, 먼저 들어와있는 연산자를 출력한다. 단 (와 )는 제외한다.
3.괄호가 나온 후 닫는 괄호가 나올 경우, 모든 연산자를 출력한다. 괄호는 출력하지 않는다.
이런 방식을 사용하기 위해서는 스택을 사용할 것이다.
왜냐면 후위표기식에 방법에 따르면 A+B*C같은 경우 ABC*+가 뜨는 것처럼, 자신보다 낮은 우선순위의 연산자가 앞에있으면 높은 우선순위의 연산자가 먼저 뜨기 때문이다.
또한 2번에 대한 규칙에 대해 설명을 해 보자면, A*B*C의 경우 AB*이후 C*가 된다는 뜻이다.
*는 같은 우선순위니까
그럼 A+B*C와 A*B*C를 스택을 가지고 설명을 해 보겠다
후위 표기식의 예시를 본 것 처럼 모든 피연산자(여기서는 알파벳)는 순서대로 들어오기 때문에 단순히 출력 배열안에만 넣어주면 된다.
그다음 연산자에 대해서는 스택을 사용할 것이라고 얘기햇는데
A+B*C의 경우
먼저 A + B가 들어가면
AB는 출력 배열에 +는 스택에 들어가게 된다
arr : AB
이후 *C가 들어오게 되는 경우를 보자
*가 들어가게 되는 경우 +는 *보다 낮지않은 연산자가 아니므로 스택에 고대로 들어가게 될 것이다.
arr : ABC
이제 모든것을 입력했으니 스택에 순서대로 출력해주게되면
ABC*+ 로 나오게 되는 것이다.
그렇다면 A*B*C를 보자
똑같이 A*B먼저 들어가면
arr :AB
그리고 이후 *가 들어오게 되면
앞선 *는 현재 *보다 "낮지않은 우선순위의 연산자" 이므로, 스택에 있는 내용물을 모두 빼준다
AB*이후 *를 스택에 넣고
arr : AB*
C를 넣어주면 끝
그렇다면 AB*C*가 되는 것이다.
이젠 괄호를 써볼까?
A*(B+C)를 해본다 하자
그럼 아마
A*부터 들어가게 되면
arr : A
인 상태인데 (가 들어오게 될 경우
우선 단순히 스택에 (를 넣어준다
arr : A
이후 B+C가 들어오는데, 당연하게도 앞선 연산자가 "(" 이므로 낮지 않지만 우선 패스를 해준다
그후 B+C를 하게해주면
arr: ABC
가 진행되고 이후 )가 들어오게 되면 (까지 모두 스택을 비워주는데, ( 와 ) 은 출력하지 않으므로
arr : ABC+ 가 되며, 이후 남은 *를 출력해주게되면 ABC+*가 되게 된다.
이걸 코드로 옮겨보자
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
stack<char> st;
string temp;
cin >> temp;
int checknum = 0;
char order[temp.length()] = {0};
int seq = 0;
for (int i = 0; i < temp.length(); i++)
{
if (temp[i] <= 90 && temp[i] >= 65)
{
order[seq++] = temp[i];
}
else if (temp[i] == '+' || temp[i] == '-')
{
if (st.empty() || st.top() == '(')
{
st.push(temp[i]);
}
else
{
while (!st.empty() && st.top() != '(')
{
order[seq++] = st.top();
st.pop();
}
st.push(temp[i]);
}
}
else if (temp[i] == '/' || temp[i] == '*')
{
while (!st.empty() && (st.top() == '*' || st.top() == '/'))
{
order[seq++] = st.top();
st.pop();
}
st.push(temp[i]);
}
else if (temp[i] == '(')
{
st.push(temp[i]);
}
else if (temp[i] == ')')
{
while (!st.empty() && st.top() != '(')
{
order[seq++] = st.top();
st.pop();
}
if (!st.empty())
st.pop();
}
}
while (!st.empty())
{
order[seq++] = st.top();
st.pop();
}
for (int i = 0; i < seq; i++)
cout << order[i];
}
if (temp[i] <= 90 && temp[i] >= 65)
{
order[seq++] = temp[i];
}
대문자 알파벳인 경우 그저 출력배열에 입력
else if (temp[i] == '+' || temp[i] == '-')
{
if (st.empty() || st.top() == '(')
{
st.push(temp[i]);
}
else
{
while (!st.empty() && st.top() != '(')
{
order[seq++] = st.top();
st.pop();
}
st.push(temp[i]);
}
}
+나 - 연산자가 올 경우, 스택이 비어있거나 top이 (면, 단순히 연산자를 넣어주지만
다른 연산자가 존재할 경우, ( +와 -보다 낮지않은 연산자는 모든 연산자 이기 때문에) 출력배열에 합류 후 pop을 해준다.
else if (temp[i] == '/' || temp[i] == '*')
{
while (!st.empty() && (st.top() == '*' || st.top() == '/'))
{
order[seq++] = st.top();
st.pop();
}
st.push(temp[i]);
}
곱셈 나눗셈일 경우, 단순하다 , 이들보다 낮지않은 연산자는 *와 /이기 때문에 이것이 아니라면 단순히 PUSH
else if (temp[i] == '(')
{
st.push(temp[i]);
}
(가 나올경우는 그냥 먼저 스택에 넣어준다.
else if (temp[i] == ')')
{
while (!st.empty() && st.top() != '(')
{
order[seq++] = st.top();
st.pop();
}
if (!st.empty())
st.pop();
}
그리고 )를 만나는 순간 스택안에서 (가 나오기 전까지 모든 값들을 pop해준다.
그 후 마지막 (에 대해서는 pop을 한다.
while (!st.empty())
{
order[seq++] = st.top();
st.pop();
}
이후 입력이 끝나면 남은값들을 모두 pop한다.
사실 이 문제는, 코딩테스트에 본격적으로 빠지기 전, 학부 2학년때 겨우겨우 풀었던 코드이다 그래서 굉장히 허점도 많아 보이는데 시간이 된다면 다른 사람들은 내 코드를 보기전 혹은 설명만 듣고 고쳐보거나 풀기를 추천한다