Stack - 2

계산기

1. 중위 표기식을 후위 표기식으로 변환 (스택 활용)
2. 후위 표기식을 계산 (스택 활용)

• 문자열로 된 계산식이 주어질 때, 스택을 이용하여 이 계산식의 값을 계산할 수 있다.
• 중위 표기법 : 연산자를 피연산자의 가운데에 표기 (A+B)
• 후위 표기법 : 연산자를 피연산자 뒤에 표기하는 방법 (AB+)

---

후위 표기식 변환 방법 A*B-C/D

1단계 : 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 표현한다.
((A*B) - (C/D))
2단계 : 각 연산자를 그에 대응하는 오른쪽 괄호 뒤로 이동시킨다.
((A B)* (C D)/)-
3단계 : 괄호를 제거한다.
AB*CD/-

→ 복잡하고, 해당 방식을 구현하는데 어려움이 있을 수 있다.

후위 표기식 알고리즘

1. 입력 받은 중위 표기식에서 토큰을 읽는다.
2. 토큰이 피연산자면, 토큰을 출력한다.
3. 토큰이 연산자(괄호포함)일 때,
   3-1. 스택의 top에 저장이 되어있는 연산자보다 우선순위가 높으면 push
   3-2. 우선 순위가 낮으면 토큰의 우선 순위가 낮을 때까지 pop(같아도 pop 한다), 이후에 push
   3-3. 비어있다면, 그냥 push를 한다.
   3-4. 여는 괄호는 그냥 push하면 된다.
4. 토큰이 오른쪽 괄호 ) 이면, 스택 top에 (가 올 때까지 pop. 왼쪽 괄호만 만나면 pop하고 출력하지 않는다.
   → 스택에 밖의 왼쪽 괄호는 우선 순위가 가장 높으며, 스택 안의 왼쪽 괄호는 우선 순위가 가장 낮다.
   (일반적으로 괄호가 우선순위가 높지만, 스택 내부에서는 의미가 없다.)
5. 중위 표기식이 더 읽을 것이 없다면 중지.
   있다면 부터 반복한다.
6. 스택에 남아있는 연산자를 모두 pop하여 출력한다.

<예시>
(6 + 5 * (2 - 8) / 2)

pop을 해준다는 것은, 그냥 출력한다는 것으로 이해하면 된다.

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Stack_계산기 {
	public static void main(String[] args) {
		String expression = "(6+5*(2-8)/2)";
	
		System.out.println(infixToPostfix(expression));
		
	}
	
	
	static Map<Character, Integer> map = new HashMap<>();
	
	// 프로그램 실행 단계에서 바로 생성이 되기 때문에, 우선 순위가 높아진다. 
	// 중복해서 만들지 않아도 된다. 
	static {
		map.put('+', 1);
		map.put('-', 1);
		map.put('*', 2);
		map.put('/', 2);
	}
	
	// 중위 표기식을 후위 표기식으로 바꾸는 
	static String infixToPostfix(String infix) {
		
		String postfix = "";
		Stack<Character> stack = new Stack<>();
		
		for (int i = 0; i < infix.length(); i++) {
			// 숫자가 2개 이상 함께 겹쳐진다면, 다른 방식을 써야 한다. 
			char c = infix.charAt(i);
			
			// 피연산자가 나오는 경우, 바로 출력 
			if( c >= '0' && c <= '9' ) {
				postfix += c;
			}	
			// 괄호 연산자 처리 
			 else if ( c == '(') {
				stack.push(c);
			} else if ( c == ')') {
				while(stack.peek() != '(') {
					char popItem = stack.pop();
					postfix += popItem;
				}
				stack.pop();
			}
			// 괄호가 아닌 연산자 처리 
			 else {
				
				//연산자 우선순위가 낮은 게 올 때까지 pop 
				// 여는 괄호의 조건은 뺀다. 
				while(!stack.isEmpty() && stack.peek() != '('&& map.get(stack.peek()) >= map.get(c)) {
					char popItem = stack.pop();
					postfix += popItem;
				}
				stack.push(c);
			}
		}
		
		// 스택 비워주기 
		while (!stack.isEmpty()) {
			postfix += stack.pop();
		}
		return postfix;
	}
	
}

---

후위 표기식 계산 알고리즘

1. 피연산자를 만나면 스택에 push 한다.
2. 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산
3. 연산 결과를 다시 스택에 push
4. 수식이 끝나면 마지막으로 스택을 pop하여 출력

static int evalPostfix(String postfix) {
		
	Stack<Integer> stack = new Stack<>();
		
	for(int i = 0; i < postfix.length(); i++) {
		char c = postfix.charAt(i);
			
		if( c >= '0' && c <= '9') {
			stack.push( c - '0' );
		} else {
			int num2 = stack.pop(); // 처음 pop은 위에 있는 값이 뽑히게 되므로 
			int num1 = stack.pop();
				
			int result = 0;
				
			if (c == '+') {
				result = num1 + num2;
			} else if ( c == '-') {
				result = num1 - num2;
			} else if ( c == '*') {
				result = num1 * num2;
			} else if ( c == '/') {
				result = num1 / num2;
			}
				
			stack.push(result);
		}
	}
	return stack.pop();
}

• 후위 표기식으로 작성이 된 것을 계산하게 된다.

	static int evaluate(String expression) {
		String postfix = infixToPostfix(expression);
		return evalPostfix(postfix);
	}

만약 두 개의 메서드가 하나로 정의되는 경우, 위와 같이 작성하면 돌아가면서 한 번에 진행이 된다.