[C++] BOJ 1918 후위 표기식

문제

백준 1918번 후위 표기식

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

1918번: 후위 표기식

코드

#include<iostream>
#include<stack>
#include<string>
using namespace std;

int main() {
	stack<char>op;//연산자
	string str;

	cin >> str;

	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') {//괄호가 시작될 경우
			op.push(str[i]);
		}
		else if (str[i] == '+' || str[i] == '-') {//덧셈이나 뺄셈 입력될 경우
			while (!op.empty()) {
				if (op.top() == '(')break;
				cout << op.top();
				op.pop();
			}
			op.push(str[i]);
		}
		else if (str[i] == '*' || str[i] == '/') {//곱셈, 나눗셈 입력될 경우
			while (!op.empty()) {
				if (op.top() == '('||op.top()=='+'|| op.top()=='-')break;
				cout << op.top();
				op.pop();
			}
			op.push(str[i]);
		}
		else if (str[i] == ')') { //괄호로 묶인 부분의 연산자 출력
			while (op.top() != '(') {
				cout << op.top();
				op.pop();
			}
			op.pop();
		}
		else //문자는 그대로 출력
			cout << str[i];
	}
	while (!op.empty()) { //마지막 남은 연산자 출력
		cout << op.top();
		op.pop();
	}
}

풀이방법

입력값을 string에 입력받은 뒤, 각 자리마다 연산을 수행한다. 연산자가 입력된 경우 stack에 각 연산자를 char형태로 push해준다. + 또는 - 가 입력되는 경우 ( 가 나오기 전까지, 즉 +, -, *, / 연산자만 출력해준다. * 또는 / 가 입력되는 경우, 앞에 있는 *와 /을 모두 출력해준다. ) 가 입력되는 경우, ( 사이에 있는 연산자들을 모두 출력해주고, ( 은 제거한다. 연산자가 아닌 문자가 입력되는 경우에는 그대로 출력해준다. 마지막으로, 스택에 남아있는 연산자들을 모두 출력해준다.

고민과정

일단 문제를 읽었을 때, 모든 계산과정에 대해 괄호가 주어지는건지, 덧셈 뺄셈/곱셈나눗셈의 순서는 알아서 해야하는건지 헷갈렸다. 채점해보니 알아서 해야하는 것 같았다.

stack이 크기가 0인 경우를 예외처리하지 않아서 오류가 났었다.

곱셈 또는 나눗셈이 입력되는 경우에도 앞의 연산자들을 출력해야 하는 것을 빠뜨렸다. 뒤에 (가 바로 오는 경우를 고려하지 않았었다.

한 문제 푸는 데에 너무 오래걸렸다. 아마 코딩테스트나 대회였다면 시간압박때문에 못 풀었을 것 같다...