[SWEA] #1224 - 계산기3

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14tDX6AFgCFAYD 

SW Expert Academy

 

💡 문제

---

[설명]

문자열로 이루어진 계산식이 주어질 때, 이 계산식을 후위 표기식으로 바꾸어 계산하는 프로그램을 작성하시오.

예를 들어

“3+(4+5)*6+7”

라는 문자열로 된 계산식을 후위 표기식으로 바꾸면 다음과 같다.

"345+6*+7+"

변환된 식을 계산하면 64를 얻을 수 있다.

 

💡 아이디어

---

[후위 표기식 변환]

후위 표기식을 이용한 계산은 Stack을 사용하는 대표 유형이라고 볼 수 있다.

우선 Infix로 표현된 수식을 하나씩 확인하며 숫자일 경우에는 Postfix에 추가한다.

반면, 연산자가 나올 경우 Stack의 상단을 보고 우선순위를 비교해 Stack에 있는 것이 우선순위가 높거나 같으면

POP 해서 Postfix에 추가하고,  방금 확인한 연산자는 Stack에 넣는다.

닫는 괄호이면 여는 괄호가 나올 때까지 Postfix에 추가한다.

수식을 모두 확인했다면 Stack에 남아있는 것을 모두 Postfix에 추가해준다.

 

[계산]

계산을 위한 Stack은 별도로 선언한다.

그 후 Postfix를 보면서 숫자가 나오면 Stack에 넣는다.

연산자가 나오면 연산자에 해당하는 계산의 결과를 Stack에 넣는다.

이 과정을 반복하면 마지막에 Stack에 최종 결과 하나만 남을 텐데 이 결과를 반환하면

계산은 완료된다.

 

💡 소스코드

---

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Stack;

public class P_1224 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for (int TC = 1; TC <= 10; TC++) {
			int T = Integer.parseInt(br.readLine());
			
			String str = br.readLine();
			String postfix = InfixToPostfix(str);//Infix를 Postfix로 바꾸는 Method 호출
			
			System.out.println("#" + TC + " " + calculator(postfix));//결과로 받은 Postfix를 계산하는 Calculator Method 호출
		}
		
		br.close();
	}

	public static int priority(char c) {//연산자 우선순위 결정
		switch (c) {
		case '+':
		case '-':
			return 1;

		case '*':
			return 2;
		}

		return 0;
	}

	public static String InfixToPostfix(String str) {
		Stack<Character> stack = new Stack<Character>();
		String postfix = "";

		for (int i = 0; i < str.length(); i++) {
			char c = str.charAt(i);

			if (c == '(')//여는 괄호이면 stack에 push
				stack.push(c);
			
			else if (Character.isDigit(c))//숫자면 postfix에 붙이기
				postfix += c;
			
			else if (c == '*' || c == '+') {//연산자 *, + 일 때 우선순위를 비교해 stack에 있는 것이 우선순위가 같거나 높으면 pop함
				if(priority(stack.peek()) >= priority(c))
					postfix += stack.pop();
				
				stack.push(c);//입력받은 것은 stack에 push
			} 
			
			else if (c == ')') {//닫는 괄호이면
				while (stack.peek() != '(')//stack의 top이 '('일 때까지  
					postfix += stack.pop();//pop한 뒤에 postfix에 추가함
				
				stack.pop();//현재 stack top에는 '('가 있으므로 pop해줌
			}
		}
		
		while (!stack.isEmpty())//stack에 남아있는 것들 postfix에 붙여줌
			postfix += stack.pop();
		
		stack.clear();
	
		return postfix;//return
	}

	public static int calculator(String str) {
		Stack<Integer> stack = new Stack<>();

		for (int i = 0; i < str.length(); i++) {
			char c = str.charAt(i);

			if (Character.isDigit(c))//숫자면 stack에 그대로 push
				stack.push(c - '0');

			else if (c == '*')//'*'이면 pop을 2번 해서 곱하기
				stack.push(stack.pop() * stack.pop());

			else if (c == '+')//'+'이면 pop을 2번 해서 더하기
				stack.push(stack.pop() + stack.pop());
		}

		return stack.pop();//return
	}
}

 

💡 결과

---

자료구조를 배울 때 똑같은 문제를 꽤 힘들게 이해한 적이 있었다.

아마 일상적으로 사용하는 수식이 아니기 때문에 이해가 어려웠던 것 같다.

하지만, 다행히 그때 제대로 이해한 덕에 이번 문제는 조금 수월하게 풀 수 있었다.