[Java] 후위 표기법 (PostfixNotation) 스택 활용하여 구현하기

안녕하세요 오늘은 후위 표기법(PostfixNotation)에 대해 알아보겠습니다. 우리가 일반적으로 사용하는 표기법은 연산자 사이에 피연산자가 오는 중위 표기법입니다. 후위 표기법은 연산자를 피연산자의 뒤에 놓는 방법입니다. 스택의 응용의 대표적인 예이며, 수식은 계산기에서나 컴퓨터 프로그래밍을 할 때 자주 나타납니다.

 

---

1. 코드 구현 과정

1.선언 및 분해

public class PostfixNotation {
	public static void main(String[] args) {
		PostfixNotation pfn = new PostfixNotation();
		Stack<String> ms = new Stack<>();

		String a = "113 + 11 - ( 32 - ( 9 - 2 + 6 ) )";
		String[] arr = a.split(" "); //공백을 기준으로 잘라줌
		String result = "";

PostfixNotation 클래스를 만들고 main 함수 안에 문제를 그대로 넣고 split 메서드로 공백을 기준으로 잘라줍니다.

 

2. for문으로 분류

		switch (s) {
		case "+":
			if (ms.isEmpty()) { 
				ms.push(s);
			} else if (ms.peek().equals("(")) {
				ms.push(s);
			} else {
				result += ms.pop() + " "; 
				ms.push(s);
			}
			break;
		case "-":
			if (ms.isEmpty()) {
				ms.push(s);
			} else if (ms.peek().equals("(")) {
				ms.push(s);
			} else {
				result += ms.pop() + " ";
				ms.push(s);
			}
			break;
		case "(":
			ms.push(s);
			break;
		case ")":
			while (true) {
				if (ms.peek().equals("(")) {
					ms.pop();
					break;
				} else {
					result += ms.pop() + " ";
				}
			}
			break;
		default:
			result += s + " ";
			break;
		}
	}

for 문안에 +,-,(,)를 switch 문을 사용하여 분류합니다. isEmpty는 비어있는지 확인하는 메서드인데, 비어있다면 push 메서드를 활용해 s를 스택에 넣어줍니다. pop은 다른 연산자가 들어오면 스택에 있던 기존 연산자를 pop으로 빼냅니다.

 

3. 출력문

if (!ms.isEmpty()) {
		result += ms.pop();
		System.out.println("Expression> " + a);
		System.out.println("Postfix> " +result);
	}
		
	System.out.println("Result :  " + pfn.calC(result));
}

기존식을 첫 줄에 출력하고, 후위 표기법으로 변환된 식을 두 번째 줄에 출력합니다. 연산 결과도 Result에 출력했습니다.

 

4. 후위표기식을 결과값 계산

public int calC(String resultStr) {
	Stack<String> st = new Stack<>(); //스택 생성
	String[] cal_result = resultStr.split(" ");
	int result = 0;

	for (String s : cal_result) {
		switch (s) {
		case "+":
			result = Integer.valueOf(st.pop()) + Integer.valueOf(st.pop());
			st.push(String.valueOf(result));
			break;
		case "-":
			result = -Integer.valueOf(st.pop()) + Integer.valueOf(st.pop());
			st.push(String.valueOf(result));
			break;
		default:
			st.push(s);
			break;
		}
	}
	return result;
    }
}

후위 표기식으로 변환된 결과값을 계산해 주는 부분입니다. 스택을 생성하고 +연산자가 나오면 더해주고, - 연산자가 나오면 빼줘야 하기 때문에 - 연산자 result 앞에 -를 붙여줍니다. 마지막으로 결과를 반환합니다.

---

2. 결과

기존 식과 후위 표기법 변환, 연산 결과까지 잘 출력된 것을 확인할 수 있습니다.