개요

백준1918번: 후위 표기식

• 입력
  첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 * 가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.

• 출력
  첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

접근방법

이런 계산기 류의 문제는 스택으로 괄호나 사칙연산 기호를 처리하는게 편하다는 걸
알고 있어서 스택으로 접근했다.

후위 표기식으로 표현하기 위한 방법은
1. 입력값을 string값으로 받아온 후, 한 글자 한글자를 char형으로 읽어온다.
2. 읽어온 char 값이 문자라면 바로 출력, 사칙연산기호나 '(',')'라면 스택으로 처리
3. '+'나 '-'가 들어왔을때,' * ', ' / '들어왔을 때, ')', '('값이 들어왔을때로 나누어 처리하였다.

코드

#include<iostream>
#include<stack>

using namespace std;
string inputStr;
stack<char> s;

void input() {
	cin >> inputStr;

}
void solution() {
	for (int i = 0; i < inputStr.length(); i++) {
		//'+'나 '-'가 들어왔을 때, 
		if (inputStr[i] == '+' || inputStr[i] == '-') {
			// 비어있을때까지 혹은 '(' 나 ')' 나오기 전까지 순서대로 top부터 밑까지 다 출력
			while (!s.empty()&&(s.top()!='('&&s.top()!=')')) {
				cout << s.top();
				s.pop();
			}
			//출력후 들어온 값 넣어주기
			s.push(inputStr[i]);
		}
		//*이나 /들어왔을 때
		else if (inputStr[i] == '*' || inputStr[i] == '/') {
			//스택 비어있다면 그냥 push
			if (s.empty()) {
				s.push(inputStr[i]);

			}
			//+나 -,'(',')' 들어있을 때도 그냥 push
			else if (s.top() == '+' || s.top() == '-' ||s.top()=='(') {
				s.push(inputStr[i]);
			}
			//*나 / 들어오면 전에 들어있던 값 넣어줌
			else {
				cout << s.top();
				s.pop();
				s.push(inputStr[i]);
			}
		}
		// '('들어오면 그냥 push
		else if (inputStr[i] == '(') {
			s.push('(');
		}
		//')'들어오면 스택안은 어차피 정렬되있을 것이므로 stack의 top()값이 '('나올때까지 top부터 순서대로 출력. 
		else if (inputStr[i] == ')') {
			while (s.top() != '(') {
				cout << s.top();
				s.pop();
			}
			s.pop();
		}
		else {
			cout << inputStr[i];
		}
	}
	//마지막에 스택 남은것 처리
	while (!s.empty()&&s.top()!='('&&s.top()!=')') {
		cout << s.top();
		s.pop();
	}
}

int main() {
	input();
	solution();
}

문풀후생

사칙연산 우선순위랑 '(' , ')'값이 들어올 때처리가 까다로웠다.
나머지 문법적인 부분은
비교문에서 예를들어 밑에와 같은 조건이 있을때

stack<int> s;
if (!s.empty() && s.top() == 1 || s.top()==2) 

단순히 스택 s가 비어있을 때 !s.empty()에서 걸러질 줄 알았는 데,
!s.empty() && s.top() == 1가 먼저 연산이 되고, s.top()==2를 비교하게 되어
s.top()==2 여기서 empty back()불러온다고 오류가 떴다.

해결하려면 (s.top() == 1 || s.top()==2) 이렇게 괄호 쳐줘야한다.