[Baekjoon] 1918_후위 표기식

Gold II

문제(출처: https://www.acmicpc.net/problem/1918)

---

< 후위 표기식 >

 

문제 풀이 

 

우선순위가 (괄호), (*,/), (+,-) 순이므로 순서대로 후위 표기식으로 바꾼다.

 

 

 my solution (Java)

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

public class _1918_ { // 후위 표기식
	static ArrayList<String> arr;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		String str = bf.readLine();

		Stack<String> stack = new Stack<>();
		arr = new ArrayList<>();

		// (, )
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == ')') {
				while (!stack.peek().equals("(")) {
					arr.add(stack.pop());
				}
				checkPriority("*", "/");
				checkPriority("+", "-");

				stack.pop();
				stack.add(arr.get(0));
				arr.clear();
			} else {
				stack.add(Character.toString(str.charAt(i)));
			}
		}

		// *, /
		init(stack);
		checkPriority("*", "/");

		// +, -
		checkPriority("+", "-");

		System.out.println(arr.get(0));
	}

	private static void init(Stack<String> stack) {
		arr.clear();
		while (!stack.isEmpty()) {
			arr.add(stack.pop());
		}
	}

	private static void checkPriority(String op1, String op2) {
		Stack<String> stack2 = new Stack<>();
		for (int i = arr.size() - 1; i >= 0; i--) {
			String temp = arr.get(i);
			if (arr.get(i).equals(op1) || arr.get(i).equals(op2)) {
				temp = stack2.pop();
				temp += arr.get(i - 1);
				temp += arr.get(i);
				i -= 1;
			}
			stack2.add(temp);
		}
		init(stack2);
	}
}

변수)
str : 중위 표기식
stack : Stack <String>
arr : ArrayList <String>

 

중위 표기식을 입력받은 후 괄호, (*,/), (+,-) 순으로 후위 표기식으로 바꾼다.

 

중위 표기식을 순환하면서 stack에 값을 넣는다. 만약 값이 ')' 라면 괄호 안의 값을 후위 표기식으로 바꾸기 위해 다음과 같은 과정을 따른다.

1) '('을 만날 때까지 stack에서 pop 한 값을 ArrayList에 저장

2) 괄호 안에 값이 ArrayList에 저장된 것이므로 checkPriority 함수를 이용해 *, / 연산자를 먼저 후위 표기식으로 교체

3) checkPriority 함수를 이용해 +, - 연산자를 후위 표기식으로 교체

4) stack에서 '(' 제거 후 위에서 구한 후위 표기식을 stack에 추가

5) 다음 작업을 위해 ArrayList 초기화

 

괄호를 후위 표기식으로 고친 후 *, /를 후위 표기식으로 바꾸기 위해 다음과 같은 과정을 따른다.

1) init 함수를 통해 stack에 있는 값을 ArrayList에 저장

2) checkPriority 함수를 이용해 *, / 연산자를 후위 표기식으로 교체

 

마지막으로 +,-를 후위 표기식으로 바꾸기 위해 다음과 같은 과정을 따른다.

1) init 함수를 통해 stack에 있는 값을 ArrayList에 저장

2) checkPriority 함수를 이용해 +,- 연산자를 후위 표기식으로 교체

 

ArrayList에 있는 값이 최종 후위 표기식으로 바뀐 식 이므로 값을 출력한다.

 

init(Stack <String> stack)

stack에 있는 값을 pop 해서 ArrayList에 저장

 

checkPriority(String op1, String op2)

먼저, 새로운 stack을 선언한다.

ArrayList에는 원래 식과 반대로 저장되어 있으므로 ArrayList를 뒤에서부터 순환한다. 만약 값이 매개변수로 들어온 연산자와 같다면 stack에서 피연산자 1개, 연산자, ArrayList의 다음 값인 피연산자 1개를 문자열로 만들어 stack에 저장한다. 값이 매개변수로 들어온 연산자와 같지 않다면 바로 stack에 저장한다. 

모든 순환을 마친 뒤 init 함수를 통해 stack의 값을 ArrayList로 옮긴다.

---

---