#1918 : 후위 표기식

풀이방법

사용된 것:

Stack

 

 

 

 

2023.01.10

주어진 중위 표기식을 앞에서부터 한 글자씩 훑으면서, 이번 글자의 종류가 무엇인지에 따라 아래와 같은 작업을 수행해주면 문제를 풀 수 있다.

 

1. 이번 글자가 피연산자인 경우

이번 글자를 즉시 화면에 출력한다.

 

2. 이번 글자가 왼쪽 괄호인 경우

스택에 '('를 넣어준다.

 

3. 이번 글자가 오른쪽 괄호인 경우

스택의 top에 '(' 가 올라올 때까지 계속해서 pop()을 하여 하나씩 화면에 출력한다.

스택의 top에 '('가 올라왔다면 그 '('는 화면에 출력하지 않고 pop()만 해준다.

 

4. 이번 글자가 + 혹은 -인 경우

현재 스택이 비어있지 않다면, 스택이 비거나 top에 '('가 올라올 때까지 계속해서 pop()을 하여 하나씩 화면에 출력한다.

그 다음 이번 글자를 스택에 넣어준다.

 

5. 이번 글자가 * 혹은 /인 경우

현재 스택이 비어있지 않고 스택의 top에 * 혹은 / 가 있다면, 스택이 비거나 * 과 / 이 아닌 다른 문자가 top에 올라올 때까지 계속해서 pop()을 하여 하나씩 화면에 출력한다.

그 다음 이번 글자를 스택에 넣어준다. 

 

 

 

설명은 다음과 같다.

 

문제를 해결하는 핵심 아이디어는 두 가지이다.

 

첫째는 피연산자는 무조건 즉시 화면에 출력하고, 스택에 연산자와 괄호만 넣으면 된다는 것이다.

후위 표기식의 특성을 생각해보면 쉽게 그 이유를 알 수 있다.

 

둘째는 연산자 사이의 계산 우선순위를 고려해야 한다는 것이다.

덧셈, 뺄셈보다 곱셈, 나눗셈의 우선순위가 높으므로 순서를 잘 맞추어 연산자를 적어주어야 한다. 이것은 손으로 후위 표기식을 적을 때에는 어렵지 않다. 그러나 코드로 어떻게 구현해야 하는지 생각해내는 것은 조금 어려웠다.

생각해내기가 어려울 뿐, 구현 자체는 까다롭지 않다. 수식에 +, -, *, / 가 등장할 때마다 스택의 top에 어떤 연산자가 있는지를 확인해주면 된다. 만약 스택의 top에 있는 연산자의 계산 우선순위가 자신보다 낮다면, 그냥 아무것도 하지 않고 자신을 push하기만 하면 된다. 그러나 스택의 top에 자신보다 계산 순위가 높거나 같은 연산자가 있다면, 자신보다 우선순위가 낮은 연산자가 top에 올라오거나, 괄호가 올라오거나, 스택이 아예 빌 때까지 모든 연산자를 pop()하여 출력해버린 뒤에 자신을 push해야 한다.

 

코드

Java(2023.01.10)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		/*
		 * 입력값 읽어오기
		 */
		//수식 읽어와 char[]에 저장하기
		char[] ex = br.readLine().toCharArray();
		
		/*
		 * 계산하기
		 */
		//정답 문자열을 만들어줄 StringBuilder 선언
		StringBuilder sb = new StringBuilder();
		//스택 선언
		Stack<Character> stack = new Stack<Character>();
		//식의 앞부터 살피기
		for(char c: ex) {	//각 글자마다 반복
			//이번 글자가 피연산자인 경우
			if(c>='A' && c<='Z') sb.append(c);	//StringBuilder에 c를 추가
			//이번 글자가 '('인 경우
			if(c=='(') stack.add(c);	//스택에 c를 넣기
			//이번 글자가 ')'인 경우
			if(c==')') {
				//스택의 top에 '('가 올라올 때까지 모든 연산자를 StringBuilder에 추가
				while(!stack.isEmpty()) {
					if(stack.peek() != '(') sb.append(stack.pop());					
					else break;
				}
				stack.pop(); //스택에서 '('을 꺼내주기
			}
			//이번 글자가 * 혹은 /인 경우
			if(c=='*' || c=='/') {
				//스택의 top의 연산자가 c보다 우선순위가 낮지 않다면 pop()하여 StringBuilder에 추가
				while(!stack.isEmpty()) {
					if(stack.peek() == '*' || stack.peek() == '/') sb.append(stack.pop());
					else break;
				}
				//스택에 c를 넣기
				stack.add(c);
			}
			//이번 글자가 + 혹은 -인 경우
			if(c=='+' || c=='-') {
				//스택의 top의 연산자가 c보다 우선순위가 낮지 않다면 pop()하여 StringBuilder에 추가
				while(!stack.isEmpty()) {
					if(stack.peek() != '(') sb.append(stack.pop());
					else break;
				}
				//스택에 c를 넣기
				stack.add(c);
			}
		}

		//스택에 남은 모든 연산자를 StringBuilder에 추가
		while(!stack.isEmpty()) {
			sb.append(stack.pop());
		}
		
		//StringBuilder에 쌓인 문자열을 화면에 출력
		System.out.print(sb);

	}

}