백준 1918 : 후위표기식

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

1918번: 후위 표기식

 

스택을 사용하여 중위표기식을 후위표기식으로 바꾸는 문제이다.

괄호는 재귀 호출로 처리하였고, 연산자 간 우선순위는 연산자를 스택에 넣고 이전에 들어온 연산자와 우선순위를 비교하는 방식으로 처리하였다.

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string str;
enum { LOW, HIGH }; //LOW for +-, HIGH for */

void parsing(string& s, int& idx) {
	vector<pair<char, int>> op; // operator, lvl
	char oper = 0;
	int cur_oper_lvl = 0;

	while (idx < s.size()) {
		if (s[idx] == '(') parsing(s, ++idx);
		else if (s[idx] == ')') break;
		else if (s[idx] >= 'A' && s[idx] <= 'Z') str.push_back(s[idx]);
		else {
			oper = s[idx];
			if (oper == '+' || oper == '-') cur_oper_lvl = LOW;
			else cur_oper_lvl = HIGH;

			// until op.empty() || prev_oper_lvl < cur_oper_lvl
			while (!op.empty() && op.back().second >= cur_oper_lvl) {
				str.push_back(op.back().first);
				op.pop_back();
			}
			op.emplace_back(oper, cur_oper_lvl);
		}
		++idx;
	}

	while (!op.empty()) {
		str.push_back(op.back().first);
		op.pop_back();
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	string input; cin >> input;
	int idx = 0;

	parsing(input, idx);
	cout << str << '\n';
	return 0;
}

메모리: 2024 kb

시간: 0 ms