[BOJ] 후위 표기식 1918번

후위 표기식 문제 정리

문제를 두 가지 방법으로 풀어보았습니다. 첫 번째는 switch case 문을 사용하여 모든 연산자에 대한 처리를 해주었고, 두 번째는 map을 사용하여 +, -, *, /에 우선순위를 미리 부여하여 문제를 풀었습니다.

• 첫 번째 방법 
  1. A-Z의 문자는 바로 출력
  2. '(' 문자가 들어올 시 우선순위를 0으로 지정하여 stack에 push
  3. ')' 문자가 들어올 시 '('를 만나기 전까지 stack에 들어있는 연산자 pop
  4. +, -, *, /가 들어올 시 stack의 top에 있는 문자와 새로 들어온 문자의 우선순위를 비교하여 새로 들어온 문자의 우선순위가 top 문자의 우선순위와 같거나 작을 경우 stack의 top 문자 출력
  5. stack에 남아있는 연산자가 있다면 마지막에 모두 출력

 

• 두 번째 방법
  
  1. 첫 번째 방법과 1번 과정은 동일
  2. switch case 문으로 나머지 문자들 처리.
  3. '(' 문자가 들어올 시 stack에 push, ')' 문자가 들어올 시 '(' 문자를 만날 때까지 pop
  4. 나머지 연산자는 우선순위에 따라 처리
  5. 최종적으로 stack에 남아있는 연산자 모두 출력

 

후위 표기식 소스코드

첫 번째 코드

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

using namespace std;


int main(void) {
	string s, result;
	stack<char> stop;
	
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] >= 'A' && s[i] <= 'Z') cout << s[i];
		else {
			switch (s[i]) {
			case '(':
				stop.push('(');
				break;
			case ')':
				while (!stop.empty() && stop.top() != '(') {
					cout << stop.top();
					stop.pop();
				}
				stop.pop();
				break;
			case '+':
			case '-':
				while (!stop.empty() && stop.top()!='(') {
					cout << stop.top();
					stop.pop();
				}
				stop.push(s[i]);
				break;

			case '*':
			case '/':
				while (!stop.empty() && (stop.top() != '+' && stop.top()!='-' && stop.top()!='(')) {
					cout << stop.top();
					stop.pop();
				}
				stop.push(s[i]);
				break;
			}
			
		}
	}

	while(!stop.empty()) {
		cout << stop.top();
		stop.pop();
	}
	
}

 

두 번째 코드

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

using namespace std;


int main(void) {
	string s, result;
	map<char, int> mp = { {'+',1}, {'-',1}, {'*',2}, {'/',2} };
	stack<pair<char, int>> stop;
	
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] >= 'A' && s[i] <= 'Z') cout << s[i];
		else {
			if (s[i] == '(') stop.push(make_pair('(', 0));
			else if (s[i] == ')') {
				while (!stop.empty() && stop.top().first != '(') {
					cout << stop.top().first;
					stop.pop();
				}
				stop.pop();
			}
			else {
				int qsize = stop.size();
				for (int j = 0; j < qsize; j++) {
					if (stop.top().second >= mp[s[i]]) {
						cout << stop.top().first;
						stop.pop();
					}
				}

				if (s[i] == '+') stop.push(make_pair('+', 1));
				if (s[i] == '-') stop.push(make_pair('-', 1));
				if (s[i] == '*') stop.push(make_pair('*', 2));
				if (s[i] == '/') stop.push(make_pair('/', 2));
 			}
		}
	}

	while(!stop.empty()) {
		cout << stop.top().first;
		stop.pop();
	}
	
}