Java - 중위 - 후위 표기법 변환 & 후위 표기법 계산

간단하게 계산기를 만들던 중 식을 후위로 변환하고 계산할 필요가 생겨 이를 정리해보고자 한다.

 

간단하게 만들어본 계산기인데 연산자 우선순위에 맞게 계산하려고 하니 막히는 부분이 많았다.

그래서 검색을 한 결과 식을 후위 표기법으로 바꾼 후 계산하는 것이 일반적이라는 것을 알았다.

 

중위 - 후위 변환

먼저 중위 표기법인 위 식을 후위 표기법으로 변환해 보자.

위 식 "22 + 4 * 36 - 7"을 이진트리 형태로 보면 아래와 같다.

중위 표기법은 22 + 4 * 36 - 7

후위 표기법은 22 4 36 * + 7 - 이다.

 

이제 변환하는 코드를 짜보자.

 

변환을 위해 HashMap, Stack, ArrayList를 활용했다.

HashMap은 굳이 써야 할까 고민했지만 함수를 공부한다는 느낌으로 사용했다.

String getResult(String str) {
	//식이 담겨있는 str을 " "로 나눠서 strArr에 담음
	String[] strArr = str.split(" ");
	
	//연산자 우선순위를 위한 HashMap
	HashMap<String, Integer> pri = new HashMap<>();
	pri.put("+", 0);
	pri.put("-", 0);
	pri.put("*", 1);
	pri.put("/", 1);
	pri.put("%", 1);

	//우선순위에 맞게 담기 위한 stack
	Stack<String> stack = new Stack<>();
    
	//출력 결과를 담기 위한 ArrayList
	ArrayList<String> reverseStrArr = new ArrayList<>();
    
	//strArr을 순서대로 접근
	for(String s : strArr) {
		//s가 연산자인 경우
		if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("%")) {
			//스택이 비어있는 경우 - 바로 push
			if(stack.isEmpty())
				stack.push(s);
                
			//스택이 비어있지 않은 경우
			else { 
				//스택에 담겨있는 연산자보다 s가 우선순위가 더 높으면 바로 push
				if(pri.get(stack.peek()) < pri.get(s)) 
					stack.push(s);
                    
				//스택에 담겨있는 연산자 우선순위가 더 높으면 pop한 후 push
				else {
					while(true) {
						if(stack.isEmpty() || pri.get(stack.peek()) < pri.get(s)) {
							stack.push(s);
							break;
						}
						reverseStrArr.add(stack.pop());
					}
				}
			}
		} 
		//s가 피연산자인 경우 바로 ArrayList에 담음
		else {
			reverseStrArr.add(s);
		}
	}
    
	//위 작업이 끝난 후 스택에 남아있는 연산자를 모두 ArrayList에 담음
	while(!stack.isEmpty()) {
		reverseStrArr.add(stack.pop());
	}
}

 

과정을 설명하자면 다음과 같다.

1. 식을 나눈다.
2. 연산자 우선순위를 정한다.
3 - 1. 문자열이 연산자인 경우
    - 스택이 비어있는 경우 바로 push
    - 스택이 비어있지 않은 경우 연산자 우선순위를 확인한 후 pop or push
3 - 2. 문자열이 피연산자인 경우 리스트에 바로 add
4. 스택에 남은 문자열을 리스트에 add

 

후위 표기법 계산

이제 후위 표기법으로 바꾼 식을 계산해 보자.

코드가 어렵지 않으므로 바로 보면 다음과 같다.

for(String s : reverseStrArr) {
	if(!(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("%")))
		stack.add(s);
	else {
		BigDecimal num2 = new BigDecimal(stack.pop());
		BigDecimal num1 = new BigDecimal(stack.pop());
		switch(s) {
			case "+":
				stack.push(num1.add(num2).toString());
				break;
			case "-":
				stack.push(num1.subtract(num2).toString());
				break;
			case "*":
				stack.push(num1.multiply(num2).toString());
				break;
			case "/":
				stack.push(num1.divide(num2, 4, RoundingMode.HALF_UP).toString());
				break;
			default:
				stack.push(num1.remainder(num2).toString());
				break;
		}
	}
}
return stack.pop();

1. 피연산자는 stack에 담는다.

2. 연산자가 나오면 stack에서 피연산자 2개를 pop해 계산한다.

3. 결과를 다시 stack에 push 한다.

 

 

계산 범위를 최대한 늘리고 소수도 계산하기 위해서 BigDecimal을 활용했다.

후위 표기법으로 바꿨기 때문에 매우 간단하게 계산이 가능하다.

모든 계산을 마치면 stack엔 계산 결과 하나만 남아있으므로 pop해 return한다.