[S/W 문제해결 기본] 6일차 - 계산기3 (D4)

문제 링크

• 계산기1에서는 + 만 사용했고, 계산기3 문제는 ()괄호와 +, * 사용

• stack 활용 문제

• 문자열 수식 계산의 일반적 방법
  1. 중위표기법 수식을 후위표기법으로 변경 (스택 이용)
  2. 후위표기법 수식을 스택을 이용하여 계산

  • 중위표기법 : 연산자를 피연산자 가운데 표기하는 방법 ex) A+B
  • 후위표기법 : 연산자를 피연산자 뒤에 표기하는 방법 ex) AB+

중위표기법 -> 후기표기법

1. 입력 받은 표기식의 앞에서부터 토큰을 읽는다
2. 토큰이 피연산자(숫자)이면 토큰 출력
3. 토큰이 연산자일 때,
   • 스택이 비었다면 push
   • 아니라면
     • 스택의 top의 우선순위보다 현재 토큰의 우선순위가 높으면 push
     • 그렇지 않으면 스택의 top의 우선순위가 토큰의 우선순위보다 낮을때까지 pop한 후, push
4. 토큰이 괄호일때
   • '(' 인 경우, 스택에 push
   • ')' 인 경우, 스택의 top이 '(' 일때까지 pop한 후 '('는 pop하여 버린다
5. 토큰을 다 읽고 스택에 남아있는 연산자를 모두 pop한다
   cf> 스택 밖의 왼쪽 괄호는 우선순위가 가장 높고, 스택 안에서의 왼쪽괄호는 우선순위가 가장 낮다

// 후위표기식으로 변경
	public static String change(String str) {
		Map<Character, Integer> isp = new HashMap<>();
		Map<Character, Integer> icp = new HashMap<>();
		isp.put('*', 2);
		isp.put('+', 1);
		isp.put('(', 0);
		icp.put('*', 2);
		icp.put('+', 1);
		icp.put('(', 3);

		Stack<Character> stack = new Stack<>();
		String output = "";

		for (int i = 0; i < str.length(); i++) {
			char curr = str.charAt(i);
			if (curr == ')') { // 닫힌 괄호일때
				while (stack.peek() != '(') { // 열린괄호 나올때까지
					output += stack.pop();
				}
				stack.pop(); // ( 괄호 날리기
			} else if (icp.containsKey(curr)) { // 연산자일때
				if (stack.size() == 0 || icp.get(curr) > isp.get(stack.peek())) {
					stack.push(curr); // 스택이 비었거나, 들어오는 연산자의 우선순위가 더 클때 push
				} 
				else { // 들어오는 연산자의 순위가
					while (!stack.isEmpty() && (isp.get(stack.peek()) >= icp.get(curr))) {
						output += stack.pop();
					}
					stack.push(curr);
				}
			} else { // 숫자일때
				output += str.charAt(i);
			}
		}
		while (stack.size() != 0) {
			output += stack.pop();
		}
		return output;
	}

후위표기식 계산

1. 피연산자(숫자)를 만나면 스택에 push
2. 연산자를 만나면 피연산자 두개를 pop하여 연산, 계산 결과를 push
   • num2, num1 순서대로 pop 한 후, (num1 연산 num2) 로 계산해야 마이너스나 나누기 등 헷갈리지 않음
3. 수식이 끝나면 마지막 스택을 pop 하여 출력

	// 후위표기식 계산
	public static int calculator(String str) {
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < str.length(); i++) {
			char curr = str.charAt(i);
			if (curr == '+' || curr == '*') { // 연산자일때
				int num2 = stack.pop();
				int num1 = stack.pop();

				switch (curr) {
				case '+':
					stack.push(num1 + num2);
					break;
				case '*':
					stack.push(num1 * num2);
					break;
				}
			}
			else { // 피연산자일때
				stack.push(Character.getNumericValue(curr));
			}
		}
		return stack.pop();
	}

Solution

package swea;

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

// [S/W 문제해결 기본] 6일차 - 계산기3
public class p1224 {
	// 후위표기식으로 변경
	public static String change(String str) {
		Map<Character, Integer> isp = new HashMap<>();
		Map<Character, Integer> icp = new HashMap<>();
		isp.put('*', 2);
		isp.put('+', 1);
		isp.put('(', 0);
		icp.put('*', 2);
		icp.put('+', 1);
		icp.put('(', 3);

		Stack<Character> stack = new Stack<>();
		String output = "";

		for (int i = 0; i < str.length(); i++) {
			char curr = str.charAt(i);
			if (curr == ')') { // 닫힌 괄호일때
				while (stack.peek() != '(') { // 열린괄호 나올때까지
					output += stack.pop();
				}
				stack.pop(); // ( 괄호 날리기
			} else if (icp.containsKey(curr)) { // 연산자일때
				if (stack.size() == 0 || icp.get(curr) > isp.get(stack.peek())) {
					stack.push(curr); // 스택이 비었거나, 들어오는 연산자의 우선순위가 더 클때 push
				} 
				else { // 들어오는 연산자의 순위가
					while (!stack.isEmpty() && (isp.get(stack.peek()) >= icp.get(curr))) {
						output += stack.pop();
					}
					stack.push(curr);
				}
			} else { // 숫자일때
				output += str.charAt(i);
			}
		}
		while (stack.size() != 0) {
			output += stack.pop();
		}
		return output;
	}

	// 후위표기식 계산
	public static int calculator(String str) {
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < str.length(); i++) {
			char curr = str.charAt(i);
			if (curr == '+' || curr == '*') { // 연산자일때
				int num2 = stack.pop();
				int num1 = stack.pop();

				switch (curr) {
				case '+':
					stack.push(num1 + num2);
					break;
				case '*':
					stack.push(num1 * num2);
					break;
				}
			}
			else { // 피연산자일때
				stack.push(Character.getNumericValue(curr));
			}
		}
		return stack.pop();
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for(int t=1; t<=10; t++) {
			sc.next(); // 테스트케이스 길이 안씀
			String tc = sc.next();
			System.out.printf("#%d %d\n", t, calculator(change(tc)));
		}
	}
}