[Stack] 백준 1918번: 후위 표기식

 이번에는 백준 스택 문제를 풀면서 꽤 중요하다고 생각한 1918번 후위표기식에 대해 알아보자! (ت)

1918번 후위표기식 문제

 

후위 표기식이란?

 문제에 나와있지만, 한번 더 설명을 하자면 우리는 a+b나 a*b+(c-d)와 같은 중위 표기식이 익숙하다. 수식은 일반적으로 중위표기식을 포함해 3가지 표기법으로 표현할 수 있다. 

1. 중위 표기식

우리들이 일반적으로 알고 있는 표기식 
Ex) a+b, a*b-c, A+B*(C-D)

2. 전위 표기식(Prefix notation)

연산자가 피연산자 앞에 위치하는 표기식
Ex) +ab, -*abc, +A*B-CD

3. 후위 표기식(Postfix notation)

 연산자가 피연산자 뒤에 위치하는 표기식 
Ex) ab+, ab*c-, ABCD-*+

 이 위 세가지 방법 중 이 문제에서 다룰 표기식은 후위 표기식이다. 우리가 흔히 쓰는 중위 표기식을 입력값으로 주면 후위 표기식으로 출력되는 알고리즘을 작성해보자. 

 기본적으로 스택을 이용해서 풀었기 때문에 이 포스터에서는 스택위주로 설명하지만, queue나 heap같은 다른 방식으로 푸는 방법도 있기 때문에 다른 방법으로도 풀어보길 바란다! 일단 이 알고리즘의 rule에 대해 정리하고 시작해보자.

 

스택으로 푸는 중위 표기식 -> 후위표기식

 이 알고리즘은 다음과 같은 규칙과 step으로 풀면 된다. 

1. 피연산자는 그냥 바로 출력한다. 

2. *나 /가 나오면 스택에 넣는다.
    2-1. 스택이 비어있지 않고, top에 *나 /가 있는 경우 -> top을 출력하고 pop한다. 그 후 스택에 넣는다.

3. +나 -가 나오면 스택에 넣는다.
   3-1. 스택이 비어있지 않은 경우 -> 스택이 빌 때까지 top을 출력하고 pop한다. 그 후 스택에 넣는다.
        3-1-1. 스택에 (이 있는 경우 -> (가 나올 때까지 출력하고 pop한다. 그 후 스택에 넣는다.

4. (가 나오면 스택에 넣는다.

5. )가 나오면 ( 전까지 스택에 있는 값을 출력한다.

6. 모든 과정이 끝나는데 스택이 안비어있으면, 모두 출력한다.

 음, 생각보다 간단하지 않은가? 개인적으로 이 문제는 고민하는데 제일 시간이 오래걸렸고, 결국에는 인터넷에 찾아보고 진행했다. 처음에는 아예 감을 못 잡다가 스택을 두 개 써서 피연산자랑 연산자를 나눠서 넣어보면 어떨까 까지 생각했지만 실패하고 구글링 진행...（´＿｀） 

 이 step을 보고 나서의 그 자괴감이란.. (´・＿・`)  아무튼, 이제라도 알았으니 다행이라고 생가한다. 

 여기서 주의할 점이 있다. 후위표기식은 출력값에 variation이 존재한다. A*B*C를 어떻게 표현할것인가? 

AB*C*? ABC**?

 사실 두 개를 그냥 눈으로 풀 때는 결과값은 같다. 하지만 중위표기식에서도 결국에는 같은 우선순위 연산자가 있다면 왼쪽부터 푸는 것이 정석이기 때문에 여기서도 출력값은 AB*C*가 정답이 된다. 그래서 아무도 나에게 안 알려주었던 2-1 스탭을 추가하는데 나름 고생했다. 반례를 못찾겠다면 백준 slack에 가서 물어보는게 가장 빠르고 좋은  것 같다. 커뮤니티 같은 느낌인데 그냥 qna에 물어보면 똑똑한 사람들이 답해준다. (나도 답해주는 사람이 되고싶다 ( ﾟoﾟ))

>  https://acmicpc.slack.com

Slack

 

(코드는 한번씩 풀어보고 참고하세요 c++)

 

코드

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

using namespace std;


int main() {

	string line;
	getline(cin, line);

	stack<char> s;

	int len = line.length();

	for (int i = 0; i< len; i++) {

		if (line[i] == '*' || line[i] == '/') {
			if (!s.empty()) {
				if (s.top() == '*' || s.top() == '/') {
					cout << s.top();
					s.pop();
				}
			}
			s.push(line[i]);
		}
		else if (line[i] == '+' || line[i] == '-') {
			if (s.empty()) s.push(line[i]);
			else {
				while (!s.empty()) {
					if (s.top() == '(') break;
					cout << s.top();
					s.pop();
				}
				s.push(line[i]);
			}
		}
		else if (line[i] == '(') {
			s.push(line[i]);
		}
		else if (line[i] == ')') {
			while (s.top() != '(') {
				cout << s.top();
				s.pop();
			}
			s.pop();
		}
		else {
			cout << line[i];
		}

	}

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

	return 0;
}