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

 

 풀이 과정

1. A-Z가 오면 ex에 담습니다.

2. A-Z가 아닌 연산자가 오면 stack에 쌓습니다.

3. ( 조건을 만족하는 동안 계속 ) stack의 맨 위 연산자가 새로 들어오는 연산자보다 가중치가 높거나 같으면 ex에 옮겨담습니다. 

4. '(' 가중치에 상관 없이 무조건 stack에 쌓는다.

5. ')'를 만나면 '(' 위에 있는 모든 연산자를 ex에 옮긴다.

 

(A+B*C-D) → ABC*+D- 이 반례에서 문제가 생겨서 보니까 3번 과정의 조건을 만족하는 동안 계속 진행해줘야 해서 문제가 발생했다.

 

 Code

#pragma warning(disable:C4996)
#include <iostream>
#include <stack>
#include <vector>
#include <string>

using namespace std;

char cmd[105];
char ex[105];
stack<char> st;

bool compOper(char _top, char _new) {
	if ((_top == '+' || _top == '-') && (_new == '*' || _new == '/'))
		return false;

	return true;
}

int main() {
	ios_base::sync_with_stdio(false);

	cin >> cmd;

	int idx = 0;
	int eidx = 0;
	while (cmd[idx] != '\0') {
		if (cmd[idx] >= 'A' && cmd[idx] <= 'Z') {
			ex[eidx++] = cmd[idx];
		}
		else {
			if (cmd[idx] == ')') {
				while (st.top() != '(') {
					ex[eidx++] = st.top();
					st.pop();
				}
				st.pop();
			}
			else if (cmd[idx] == '('){
				st.push(cmd[idx]);
			}
			else {
				while (!st.empty() && st.top() != '(' && compOper(st.top(), cmd[idx])) {
					ex[eidx++] = st.top();
					st.pop();
				}
				st.push(cmd[idx]);
			}
		}
		idx++;
	}

	while (!st.empty()) {
		ex[eidx++] = st.top();
		st.pop();
	}

	cout << ex;
	return 0;
}