백준 1918 후위표기식

https://www.acmicpc.net/problem/1918

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 중위표기식을 입력받아 후위표기식으로 바꾸는 문제이다.

연산자들의 우선순위를 고려하고, 스택을 이용하면 해결이 된다.

 

연산자의 우선순위는 *,/ 가 가장 높고 +,-  '(' 순이다. 스택에 들어 갈 때

*,/ 는 자기 자신들을 만나면 pop 시키고 그 이외엔 push 된다.

+,- 는 '(' 을 만나면 push 되고 그 이외의 연산자를 만나면 계속 pop시킨다.

'(' 연산자는 우선순위가 가장 낮으므로 push되고 ')' 연산자가 들어오면 그사이의 연산자들을 pop시킨다.

 

스택이 비어있을때는 top를 호출하면 안되고, 연산자가 같거나 우선순위가 높은 연산자가 스택의 top에 들어있으면 아닐때 까지 pop을 해주는 것이 중요한 포인트이다.

변경한 후위표기식을 이용해서 하나의 스택에 문자들을 집어넣고 연산자를 만나면 두개를 꺼내서 연산후 다시 집어 넣는 방식으로 스택계산기를 구현 할 수 도 있다.

 

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main(void) {
	
	stack<char> s;
	char arr[101];
	string postfix;
	int i = 0;
	cin>>arr;	
	
	while(arr[i] != '\0') { //문자열의 끝까지 반복 
	if('A' <= arr[i] && arr[i] <= 'Z') //A~Z 면 string에 더해준다 
		postfix += arr[i];
	else {
	switch(arr[i]) { //연산자일 경우 각 연산자에 맞게 push,pop을 해준다 
		case ')' :
			while(s.top() != '(') {
				postfix += s.top();
				s.pop(); 
			}
			s.pop(); break;
			
		case '+' :
		case '-' :
			while(s.size() != 0 && (s.top() != '(')) { // +,- 같은경우 '(' 연산자를 제외하고 가장 우선순위가 낮다. 
			postfix += s.top();
			s.pop(); 
			}
			s.push(arr[i]); break;
		
		case '*' : 
		case '/' :
			while(s.size() != 0 && (s.top() == '*' || s.top() == '/')) { //*,/는 우선순위가 가장 높으므로 자기 자신들과 만날때만 pop해주면 된다. 
			postfix += s.top();
			s.pop(); 
			}
			s.push(arr[i]); break;
		case '(' :
			s.push(arr[i]); break;
		
		default :
			return 0;
	}
}
	i++;
}
	while(!s.empty()) { //스택에 남아있는 연산자들을 pop한다. 
		postfix += s.top();
		s.pop();
	}
	
	cout<<postfix;
	
	return 0;
}