[Java] 토이 프로젝트 1 : 계산기 만들기 - 후위 표기법 이용

Eclipse의 플러그인 windowbuilder를 사용해 계산기를 만들었다.

 

계산기의 형태는 Google에 계산기를 검색했을 때 나오는 다음 그림을 참고했다.

내가 완성한 계산기의 모습은 다음과 같다.

계산기를 구현했을때 가장 중요하게 생각했던 점은 두 가지다.

1. 연산자의 우선순위 처리

2. 예외처리

 

이번 포스팅에는 연산자의 우선순위 처리를 기술하겠다.

1. 우선순위

연산자의 우선순위를 계산하기 위해서는 후위 표기법을 사용했다.

 

중위 표기법 : 연산자가 피연산자 사이에 위치한 표기법

A+B

 

후기 표기법 : 연산자가 피연산자 뒤에 위치한 표기법

AB+

 

후위 표기법을 구현하기 위해는 Stack을 사용했고 연산자 별로 우선순위를 지정했다.

우선순위가 높다는 것은 크다고 표시했다.

//연산자 우선순위
// % > X == / > + == - > 나머지

	static int opOrder(char op) {
		switch(op) {
			case '+':
			case '-':
				return 1;
			case 'X':
			case '/':
				return 2;
			case '%':
				return 3;
			default:
				return -1;
		}
	}

 

사용한 변수는 다음과 같다.

char operation[] = {'+', '-', 'X', '/', '(', ')', '%'};
		
ArrayList<String> postfix = new ArrayList<>(); // 후위 표기법
Stack<Character> opStack = new Stack<>(); // 연산자 Stack
Stack<String> calStack = new Stack<>(); // 후위 표기법 계산을 위한 Stack
String num = ""; // 피연산자 저장

 

입력받은 결괏값 String에 다음과 같은 알고리즘을 적용한다.

1. 피연산자는 스택(opStack)에 넣지 않고 num에 저장하고 연산자가 나올 때 num에 저장된 피연산자를 ArrayList(postfix)에 저장한다.

2. "(" 이면 무조건 스택(opStack)에 push 한다.
 
3. ")"이면 스택(opStack)에서 "("가 나올 때까지 pop을 한 후 출력한다. 

4. 그밖에 연산자라면 
   4-1. 연산자는 스택(opStack)이 비었으면 push 한다. 
   4-2. 연산자는 스택(opStack)이 비어있지 않으면 스택(opStack)에 있는 연산자와의 우선순위를 비교해
          4-2-1. 스택에 있는 연산자의 우선순위가 같거나 크다면
                  스택(opStack)에 있는 연산자를 pop을 해 ArrayList(postfix)에 저장하고
                  현재 연산자는 스택(opStack)에 push한다.
          4-2-2. 만약 3번에서 우선순위가 현재 연산자가 더 크면 현재 연산자를 push한다.

7. 수식이 끝나면 마지막 num에 저장된 피연산자를 ArrayList(postfix)에 저장한다.

8. 수식이 끝나면 스택(opStack)이 빌 때까지 pop을 해서 ArrayList(postfix)에 저장한다.

 

다음 알고리즘 구현은 다음과 같다.

// 후위 연산자로 변경
for(int i = 0; i < str.length(); i++) {
	boolean checkOp = false;
	for(int j = 0; j < operation.length; j++) {
		if(str.charAt(i) == operation[j]) {
					
			checkOp = true;
					
			if(!num.equals("")) { // 피연산자 저장
				postfix.add(num);
				num = "";
			}
					
			if(operation[j] == '(') { // '(' 이면 무조건 push
				opStack.push(operation[j]);
			}else if(operation[j] == ')') { 
				// '(' 나오기 전까지 
				while(opStack.peek() != '(' && !opStack.isEmpty()) {
					postfix.add(opStack.pop().toString());
				}
				// '(' pop
				opStack.pop();
			}else {
				if(opStack.isEmpty()) {
					opStack.push(operation[j]);
				}else {
					if(opOrder(opStack.peek()) < opOrder(operation[j])) {
						opStack.push(operation[j]);
					}else {
						postfix.add(opStack.pop().toString());
						opStack.push(operation[j]);
					}
				}
			}
		}
	}
			
	if(!checkOp) {
		num += str.charAt(i);
	}
			
}
		
// 남은 숫자 처리
if(!num.equals("")) {
	postfix.add(num);
}
		
// 남은 연산자 처리
while(!opStack.isEmpty()) {
	postfix.add(opStack.pop().toString());
}

ArrayList에 저장된 후위 표기법을 계산해야 한다.

1. 우선 ArrayList(postfix)의 값을 스택(calStack)에 저장한다.

2. 스택(calStack)의 top값이 연산자라면 pop을 한 뒤 연산자에 맞는 계산을 수행한다.

3. 계산을 전부 마치면 스택(calStack)의 top값이 계산의 최종 결과가 된다.

4. 3의 결과를  "."으로 구분해 실수인지 정수인지 판단하고 결과를 return 한다.

 

알고리즘 구현은 다음과 같다.

// 후위 연산자를 이용해 최종 결과 구하기
for(int i = 0; i < postfix.size(); i++) {
	calStack.push(postfix.get(i));
	for(int j = 0; j < operation.length; j++) {
		if(postfix.get(i).charAt(0) == operation[j]) {
			calStack.pop();
			Double n2 = Double.parseDouble(calStack.pop());
			String re = "";
					
			if(operation[j] == '%') {
				re = Double.toString(n2 * 0.01);
			}else {
				Double n1 = Double.parseDouble(calStack.pop());
				if(operation[j] == '+') {
					re = Double.toString(n1 + n2);
				}else if(operation[j] == '-') {
					re = Double.toString(n1 - n2);
				}else if(operation[j] == 'X') {
					re = Double.toString(n1 * n2);
				}else if(operation[j] == '/') {
					re = Double.toString(n1 / n2);
				}
			}
			
			calStack.push(re);
		}
	}
}
		
Double result = Double.parseDouble(calStack.pop());
String calResult[] = Double.toString(result).split("\\.");

if(Double.parseDouble(calResult[1]) == 0) {  
	if(3 <= calResult[1].length() && calResult[1].substring(0, 2).equals("0E")) {
		return Double.toString(result);
	}else { // 정수 일때, 
		return calResult[0];
	}
}else { //실수일때
	return String.format("%.10f", result);
}

 

전체 코드는 github에서 확인할 수 있다.