문제 개요
오늘의 코딩 테스트 문제는 중위 표기식을 후위 표기식으로 변환하는 것이다. 백준 1918번 문제다.
문제 분석
핵심은 다음과 같다:
1.
연산자 우선순위 처리
2.
괄호 처리
3.
스택 활용
문제에서 주어진 조건:
•
피연산자는 알파벳 대문자
•
연산자는 +, -, *, /
•
괄호 사용 가능
•
길이는 100을 넘지 않음
해결 방법
스택을 사용해 해결했다. 알고리즘의 핵심 로직:
1.
피연산자는 바로 출력
2.
여는 괄호는 스택에 push
3.
닫는 괄호를 만나면 여는 괄호까지 pop하며 출력
4.
연산자는 우선순위 비교 후 처리
연산자 우선순위:
•
/ > + -
#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
int getPriority(char op) {
if (op == '*' || op == '/')
return 2;
if (op == '+' || op == '-')
return 1;
return 0;
}
int main()
{
string input;
cin >> input;
stack<char> st;
string output;
for (auto c : input)
{
if (isalnum(c)) {
output += c;
} else if (c == '(') {
st.push(c);
} else if (c == ')') {
while (!st.empty() && st.top() != '(') {
output += st.top();
st.pop();
}
if (!st.empty() && st.top() == '(') {
st.pop();
}
} else if (isOperator(c)) {
while (!st.empty() && getPriority(st.top()) >= getPriority(c)) {
output += st.top();
st.pop();
}
st.push(c);
}
}
while (!st.empty())
{
output += st.top();
st.pop();
}
cout << output << endl;
return 0;
}
C++
복사
구현 과정
1.
문자열 순회하며 각 문자 처리
2.
isOperator(), getPriority() 함수로 연산자 처리 로직 분리
3.
스택 사용해 연산자와 괄호 관리
회고
이 문제로 깨달은 점:
1.
스택 활용의 중요성
2.
연산자 우선순위 처리의 복잡성
3.
edge case 고려의 필요성
이번 문제는 생각보다 오래 걸렸다. 특히 연산자 우선순위 처리 부분에서 시간을 많이 썼다. 스택을 사용한 알고리즘은 익숙했지만, 실제 구현에서 예외 케이스 처리가 까다로웠다. 앞으로 이런 유형의 문제를 더 연습해야겠다.
