궤도
[백준] 1918번 : 후위 표기식 본문
문제
풀이
1년 반전에 자료구조 시간에 이미 배운 문제라...풀이 방법도 그때에서 전혀 달라지지 않았다. 이게 정석이기도 하구
스택에 연산자를 쌓다가 적절한 때에 출력하는게 중요한데, 여기에 연산자 우선순위를 사용한다.
다들 알겠지만 연산자의 우선순위는 괄호, 곱셈나눗셈, 덧셈뺄셈이다.
그리고 스택에 연산자를 쌓을 건데 절대로 나보다 우선순위가 높거나 같은 연산자 위에 쌓일 수는 없다.
그니까 곱셈이 이미 스택에 들어온 상태에서 덧셈이 들어오려 한다면 곱셈이 스택에서 나와야 한단 것이다.
피연산자인 A~Z는 스택에 쌓이지 않는다. 그냥 간단히 말해서 우선순위가 그 어떤 연산자보다 높다고 생각하는게 맘 편할 수도 있겠다.
그래서 이 2가지 규칙
1. 스택에 쌓이는건 오직 연산자
2. 나보다 우선순위가 높은 연산자위에 쌓일 수 없음
을 가지고 예제 입력 1을 해보자.
피연산자는 스택에 쌓이지 않으므로 바로 출력하고 '*'에 왔다. 스택이 비어 있으니 '*'는 그냥 넣어준다.
그리고 '('가 나왔는데 이는 '*'보다 우선순위가 높기 때문에 '*'위에 그냥 쌓인다.
B를 출력했고 '+'가 나왔다.
근데 앞서 괄호는 모든 연산자보다 우선순위가 높다고 말했다. 그럼 '('를 출력해야 하나?
다들 알다시피 괄호는 짝이 있다. 그래서 '('의 짝인 ')'가 나올 때까지 '('는 나올 수 없다.
굳이 말하자면 괄호는 들어갈 땐 우선순위가 가장 높지만, 나오려 할 땐 우선순위가 가장 낮아지는 것이다.
그럼 이걸 코드로는 어떻게 구현할까?
그냥 간단하게 처음부터 괄호들의 우선순위를 제일 낮게 설정하고 '('가 나오면 무조건 스택에 push하면 된다.
아무튼 그래서 '('위에 '+'이 쌓인다.
피연산자 C를 출력했고, ')'가 나왔다.
')'가 나오면 짝을 맞춰주기 위해 스택의 top이 '('일 때까지 스택의 모든 값을 출력하며 pop한다.
출력이 끝나고 마지막으로 '('를 pop하면 괄호를 출력하지 않고 없앨 수 있다.
더이상 탐색할 문자가 없는데 여전히 스택에 값이 남아있다.
그러므로 마지막에 스택을 탐색하며 남은 값들을 모조리 출력한다.
이렇게 후위표기식이 완성됐다.
소스코드
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int score(char ch) { //우선 순위
switch (ch) {
case '(': case ')':
return 3;
case '+': case '-':
return 2;
case '*': case '/':
return 1;
default:
return 0;
}
}
int main() {
string str;
stack<char> s;
cin>>str;
for(int i=0;i<str.size();i++){
switch(str[i]){
case '(': //왼쪽 괄호는 무조건 스택에
s.push(str[i]);
break;
case ')':
while(s.top()!='('){ //왼쪽 괄호 만날 때 까지 스택 출력
cout<<s.top();
s.pop();
}
s.pop();
break;
case '+': case '-': case '*': case '/': //str[i]보다 우선순위가 높거나 같은 것 출력
while(!s.empty()&&(score(s.top())<=score(str[i]))){
cout<<s.top();
s.pop();
}
s.push(str[i]);
break;
default: //문자는 바로 출력
cout<<str[i];
break;
}
}
while(!s.empty()){ //스택에 남은 연산자 출력
cout<<s.top();
s.pop();
}
}전체 소스코드다.
int score(char ch) { //우선 순위
switch (ch) {
case '(': case ')':
return 3;
case '+': case '-':
return 2;
case '*': case '/':
return 1;
default:
return 0;
}
}연산자의 우선순위를 계산하는 score 함수이다.
리턴값이 작을 수록 우선 순위가 높다.
for(int i=0;i<str.size();i++){
switch(str[i]){
case '(': //왼쪽 괄호는 무조건 스택에
s.push(str[i]);
break;
case ')':
while(s.top()!='('){ //왼쪽 괄호 만날 때 까지 스택 출력
cout<<s.top();
s.pop();
}
s.pop();
break;
case '+': case '-': case '*': case '/': //str[i]보다 우선순위가 높거나 같은 것 출력
while(!s.empty()&&(score(s.top())<=score(str[i]))){
cout<<s.top();
s.pop();
}
s.push(str[i]);
break;
default: //문자는 바로 출력
cout<<str[i];
break;
}
}메인에선 str[i]에 따른 연산을 한다.
'('라면 무조건 스택에 넣고
')'라면 s.top()=='(' 일때까지 스택을 출력하고 마지막으로 '('를 s.pop()으로 지워준다.
'+', '-', '*', '/'라면 s.top()과의 우선순위를 비교하며 스택의 값을 출력한 뒤 마지막으로 str[i] 자신을 스택에 넣는다.
마지막으로 피연산자인 문자는 바로 출력한다.
while(!s.empty()){ //스택에 남은 연산자 출력
cout<<s.top();
s.pop();
}문자열의 탐색이 끝난 후엔 스택에 남아있던 연산자들을 전부 출력한다.
