3 minute read

백준 1918번: 후위 표기식

문제:

수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

https://upload.acmicpc.net/5aad2feb-d9fc-430a-954d-73a06ba0215f/-/preview/

결과: ABC*+DE/-

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

입력:

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

풀이:

우선 이 문제를 풀기 전에 후위 표기식이 어떤식으로 표현이 되는지 이 링크를 보고 다양한 경우를 보고 이해를 한 뒤 풀면 훨씬 수월하게 풀릴 것이다. 그래도 이해가 안된다면 삼쓰의 개발 블로그를 참고한 뒤 구현 해봐도 좋을 것이다. 그림과 함께 이해하기 쉽도록 차근 차근 설명이 되어 있다.

이제 문제로 넘어가서 이 문제는 크게 2가지 경우로 나뉠 수 있다. 연산자인 경우와 피연산자인 경우인데 연산자인 경우가 많이 복잡하여 연산자인 경우에서도 3가지 경우로 나뉜다.

  1. 연산자인 경우
    1. 연산자인 경우에는 처음에 연산자가 스택에 있는 경우와 없는 경우로 한번 나뉜다. 스택에 없으면 무조건 넣어주고 아닐 경우에는 3가지로 나뉜다.
      1. 괄호 끝인 경우 - 괄호 처음에 도달 할 때가지 모든 연산자를 출력한다.
      2. 새로 들어오는 연산자가 우선 순위가 높은 경우 / 스택 제일 위에 ‘(’인 경우 - 스택에 집어 넣는 경우
        • 우선 순위가 높기 때문에 스택에 넣어준다.
        • ‘(’인 경우를 넣은 이유는 ‘(’의 우선 순위는 3인데 다음 연산자는 무조건 3보다 우선순위가 작지만 그렇다고 연산자가 우선 순위가 낮아서 출력을 할 수 없으므로 추가한 것이다.
      3. 새로 들어오는 연산자가 우선 순위가 낮은 경우 - 스택에서 출력하는 경우
        • 우선 순위가 낮거나 같기 때문에 스택 제일 위에 연산자를 출력한 뒤 pop해주고 그 뒤에 올라오는 스택 값도 같은 우선 순위일 경우 계속 출력하고 pop해준다.

        🔎 만약에 while loop 조건을 크거나 같다고 하게 되면 ‘(‘ 연산자도 같이 pop 해버리기 때문에 ‘)’일 때 while loop을 무한으로 돌게 된다. 그래서 같은 우선 순위에만 출력하는 것이다.

  2. 피연산자인 경우
    1. 그냥 출력 해주면 된다.
      • 추가적으로 우선 순위를 return 해주는 함수도 우선순위 비교시에 필요하므로 만들어주자

코드:

#include<iostream>
#include<stack>

using namespace std;

int priority(char operators){
	switch(operators){
		case '(': return 3;
		case '*': return 2;
		case '/': return 2;
		case '+': return 1;
		case '-': return 1;
	}
}

int main(){
	stack<char> operators;
	string equation;
	//입력
	getline(cin, equation);
	for(int i = 0; i < equation.size(); i++){
		//연산자인 경우
		if(equation[i]=='+'||equation[i]=='-'||equation[i]=='*'
				||equation[i]=='/'||equation[i]=='('||equation[i]==')'){
			//연산자가 있는 경우 
			if(!operators.empty()){
				//괄호가 끝나므로 그 사이에 있는 연산자 모두 출력 
				if(equation[i] == ')'){
					while(operators.top() != '('){
						cout<<operators.top();
						operators.pop();
					}
					operators.pop();
				}
				//새로 들어오는 연산자가 우선순위가 높은 경우
			  //operators.top()이 '('일때 priority가 작아도 다음 연산자가 들어올 수 있도록 함
				else if(priority(operators.top()) < priority(equation[i])||operators.top()=='('){
					operators.push(equation[i]);
				}
				//새로 들어오는 연산자가 우선순위가 낮거나 같은 경우
				else{
					cout<<operators.top();
					operators.pop();
					/*한번 pop을 한 이후 다음 operator는 pop한 연산자와 같은 우선순위일 수가 없으므로
						(같은 크기면 전에 이미 pop 됐어야 함) 들어오는 연산자와 같은 경우만 고려해준다*/ 
					while(!operators.empty()&&priority(operators.top()) == priority(equation[i])){
						cout<<operators.top();
						operators.pop();
					}
					operators.push(equation[i]); 
				}
			}
			//저장된 연산자가 아무것도 없는 경우
			else{
				operators.push(equation[i]);
			}
		}
		//피연산자인 경우
		else cout<<equation[i];
	}
	while(!operators.empty()){
		cout<<operators.top();
		operators.pop();
	}
}

Leave a comment

You may also enjoy