1918번: 후위 표기식
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의
www.acmicpc.net
문제 분석
- 시간 제한 2초: Big-O 기준 2억연산
- 다루는 값들의 수 100
- 문자열로 입력된 값을 우선순위에 맞춰 출력 해줘야 함
- 우선순위 : A~Z > *,/ > +,-
- '()'에 대한 처리도 해줘야함
주의 사항
- '()'안에 들어 있는 식은 독자적인 하나의 식으로 생각하기
- '(',')'는 출력하지 않는다.
풀이 방식
- 문자 하나씩 stack에 쌓기
- stack.top 이 문자보다 우선순위가 높거나 같으면 출력하고 pop
- '('의 우선순위는 A~Z 보다 낮고 연산자 보다 높다.
- ')'가 나오면 가장 위에 있는 '(' 까지 pop
- 마지막으로 stack에 남아있는 문자 전부 pop
stack<char> opr;
string exp;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> exp;
for (char &c: exp) {
if (c >= 'A' && c <= 'Z') { // 가장 우선순위 높음 pop해줄 거 없음
opr.push(c);
} else if (c == '(') { // 우선순위 두번째
while (!opr.empty() && opr.top() != '(') {
//괄호 안에 있는 식은 독자적인 식으로 생각하기 위해
//stack이 비거나 괄호 안에 있는 식일때 까지 반복
if (opr.top() >= 'A' && opr.top() <= 'Z') {//A~Z 만 pop
cout << opr.top();
opr.pop();
} else break;
}
opr.push(c);
} else if (c == '*' || c == '/') {//우선순위 세번째
//'('와는 비교하지않음, 괄호안에 있는 식은 독자적인 식
while (!opr.empty() && opr.top() != '(') {
if (opr.top() >= 'A' && opr.top() <= 'Z') {
cout << opr.top();
opr.pop();
} else if (opr.top() == '*' || opr.top() == '/') {
cout << opr.top();
opr.pop();
} else {
break;
}
}
opr.push(c);
} else if (c == '+' || c == '-') {
while (!opr.empty() && opr.top() != '(') {
//우선순위가 가장 낮으므로 비교없이 전부 pop
cout << opr.top();
opr.pop();
}
opr.push(c);
} else if (c == ')' && !opr.empty()) {
//')' 가 나오면 '('까지 pop
while (!opr.empty() && opr.top() != '(') {
cout << opr.top();
opr.pop();
}
opr.pop();
}
}
//stack에 남은거 pop
while (!opr.empty()) {
cout << opr.top();
opr.pop();
}
return 0;
}
느낀 점
- 괄호연산이 없는 후위표기식 문제는 풀어봤기에 어렵지 않게 풀 수 있을 거라 생각했다.
- 괄호를 처리해 주기 위해 연산과정을 그림을 그려가며 스스로 후위 표기식으로 식을 바꿔 봤다.
- stack 그림을 그려가며 푸니까 스스로 어떤 사고방식으로 후위 표기식으로 바꾸는지 파악하고, 이 사고방식을 코드로 옮겨 봤다.
- 그럼에도 구현이 쉽지는 않았지만 큰 어려움 없이 해결했다.
'Algorithm > baekjoon' 카테고리의 다른 글
[BOJ 1655] 가운데를 말해요 (0) | 2022.07.30 |
---|---|
[BOJ 5052] 전화번호 목록 (0) | 2022.07.27 |
[BOJ 2493] 탑 (0) | 2022.07.26 |
[BOJ 17299] 오등큰수 (0) | 2022.07.26 |
[BOJ 17298] 오큰수 (0) | 2022.07.26 |