[자료구조] 스택 Stack 활용: 후위 표기식 계산기 (자바/Java)

목차

스택을 활용하여 후위 표기식 계산기를 구현할 수 있다.

먼저 중위표기식을 후위 표기식으로 바꾸고, 이를 다시 계산해야 한다.

 

1. 중위 표기식 → 후위 표기식

이 과정이 상대적으로 까다롭다.

먼저 연산자 우선순위를 고려해야 한다.

연산자는 사칙 연산(+ - * /)과 괄호만 들어온다고 가정한다.

1. 입력이 연산자가 아닌 경우 바로 출력해준다. StringBuilder를 사용하여 sb에 append하였다.

2. 입력이 연산자인 경우

    2-1. 괄호인 경우

        괄호는 연산자 중에서도 특수한 경우이다. 먼저 좌괄호 '('인 경우 stack에 그냥 push한다.

        그리고 우괄호 ')'가 나오면, 좌괄호가 나올 때까지 stack에 있는 연산자들을 모두 pop하여 출력한다.

        그리고 좌괄호는 연산에 포함되지 않으니, 출력하지 않고 pop만 한다.

   괄호 안의 연산이 가장 우선순위가 높기 때문에 이처럼 특수한 방법으로 처리해야 한다.

if (c == '(')
	stack.push(c); // 좌괄호는 그냥 push

	// 우괄호는 좌괄호가 나올 때까지 pop하여 sb에 추가
else if (c == ')') {
	while (stack.peek() != '(') {
		sb.append(stack.pop());
	}
	stack.pop(); // 좌괄호는 그냥 pop
}

    2-2. 괄호가 아닌 경우

        a. 스택이 비어 있으면 그냥 push

        b. 스택이 비어 있지 않을 때에는 stack의 top 연산자가 자신의 우선순위보다 크거나 같으면 pop한다.

            이때 중요한 것은 while문을 통해 자신의 우선순위가 작은 연산자가 나올 때까지 pop을 계속해줘야 한다는 것이다. 

            pop이 끝나면(더 이상 pop할 원소가 없다면) 자신을 push한다.

    3. 모든 연산자를 한 번씩 검토한 후, stack에 남아 있는 연산자가 있다면 모두 pop한다.

else if (operator.containsKey(c)) {
	if (stack.isEmpty()) // 비어 있으면 push
		stack.push(c);
	else {
		// 비어있지 않으면 stack의 peek의 우선순위가 자신보다 크거나 같으면 pop
		// 작을때는 그냥 push
		while (!stack.isEmpty() && operator.get(c) <= operator.get(stack.peek())) {
			sb.append(stack.pop());
		}
		stack.push(c);
	}
} else { // 연산자가 아닐 때 출력
	sb.append(c);
	}
	
while (!stack.isEmpty()) // stack에 있는 것 모두 pop
	sb.append(stack.pop());

2. 후위 표기식 계산

후위 표기식을 계산할 때는 연산자 대신, 피연산자(숫자)를 stack에 넣는다.

숫자는 모두 stack에 넣고, 연산자를 만나면 숫자 2개를 pop하여 계산하고, 그 결과를 다시 stack에 넣는다.

연산이 모두 끝나면 stack에는 결과값 하나만 남아 있고, 이를 pop하여 출력하면 된다.

	static int cal(String postfix) {
		Stack<Integer> numStack = new Stack<>();
		for (int i = 0; i < postfix.length(); i++) {
			char c = postfix.charAt(i);

			if (c >= '0' && c <= '9')
				// 숫자일 경우 stack에 push
				numStack.push(c - '0');
			else {
				int num1 = numStack.pop();
				int num2 = numStack.pop();
				switch (c) {
				case '+':
					numStack.push(num2 + num1);
					break;

				case '-':
					numStack.push(num2 - num1);
					break;

				case '*':
					numStack.push(num2 * num1);
					break;
				case '/':
					numStack.push(num2 / num1);
					break;

				}
			}

		}
		return numStack.pop();

3. 전체 코드

package myds;

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

public class Stack_후위표기계산기 {
	static Stack<Character> stack = new Stack<>();
	static StringBuilder sb = new StringBuilder();
	static HashMap<Character, Integer> operator = new HashMap<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		operator.put('+', 1); // 우선순위
		operator.put('-', 1);
		operator.put('*', 2);
		operator.put('/', 2);
		operator.put('(', 0);
		operator.put(')', 0);
		String postfix = toPostfix(input);
		System.out.println(postfix);
		System.out.println(cal(postfix));

	}

	static String toPostfix(String input) {
		for (int i = 0; i < input.length(); i++) {
			char c = input.charAt(i);

			if (c == '(')
				stack.push(c); // 좌괄호는 그냥 push

			// 우괄호는 좌괄호가 나올 때까지 pop하여 sb에 추가
			else if (c == ')') {
				while (stack.peek() != '(') {
					sb.append(stack.pop());
				}
				stack.pop(); // 좌괄호는 그냥 pop
			}

			else if (operator.containsKey(c)) {

				if (stack.isEmpty()) // 비어 있으면 push
					stack.push(c);
				else {
					// 비어있지 않으면 stack의 peek의 우선순위가 자신보다 크거나 같으면 pop
					// 작을때는 그냥 push
					while (!stack.isEmpty() && operator.get(c) <= operator.get(stack.peek())) {
						sb.append(stack.pop());
					}
					stack.push(c);
				}

			} else { // 연산자가 아닐 때 출력
				sb.append(c);
			}
		}

		while (!stack.isEmpty()) // stack에 있는 것 모두 pop
			sb.append(stack.pop());

		return sb.toString();
	}

	static int cal(String postfix) {
		Stack<Integer> numStack = new Stack<>();
		for (int i = 0; i < postfix.length(); i++) {
			char c = postfix.charAt(i);

			if (c >= '0' && c <= '9')
				// 숫자일 경우 stack에 push
				numStack.push(c - '0');
			else {
				int num1 = numStack.pop();
				int num2 = numStack.pop();
				switch (c) {
				case '+':
					numStack.push(num2 + num1);
					break;

				case '-':
					numStack.push(num2 - num1);
					break;

				case '*':
					numStack.push(num2 * num1);
					break;
				case '/':
					numStack.push(num2 / num1);
					break;

				}
			}

		}
		return numStack.pop();

	}
}