[SWEA] 1222. [S/W 문제해결 기본] 6일차 - 계산기1

문제

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

예를 들어

“3+4+5+6+7”

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

"34+5+6+7+"

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

문자열 계산식을 구성하는 연산자는 + 하나뿐이며 피연산자인 숫자는 0 ~ 9의 정수만 주어진다.

 

풀이방법

문제에서는 2가지를 요구하고 있다. 주어진 계산식을 후위표기식으로 바꾸는 것과 후위표기식으로 바꾼 식을 계산하는 것이다.

 

[1. 주어진 계산식을 후위표기식으로 바꾸는 것]

 

후위 표기식으로 바꾸기 위해서는 스택을 이용한다.

 

주어진 계산식을 한 글자씩 읽어들일 때, 숫자일 경우 그대로 출력하고, '+'기호일 경우 스택에 담거나 출력한다.

 

즉, 아래와 같은 조건과 과정을 따른다.

 

입력을 한 문자씩 읽을 때,

 

1) 숫자일 경우는 바로 출력

 

2) '+'기호일 경우, 스택이 비었는지 확인

 

   2-1) 스택이 비었을 경우, push

 

   2-2) 스택이 차 있을 경우, pop하고 출력

 

3) 입력을 끝까지 읽었을 때, 스택에 들어있는 내용을 모두 출력

 

 

[2. 후위표기식으로 표현된 식을 계산하는 것]

 

후위표기식을 계산하는 방법 또한 스택을 이용한다. 1의 과정에서 출력내용을 문자열에 담았을 때, 한 문자씩 읽어들인다.

 

읽어들인 문자가 숫자일 경우 스택에 담고, '+'기호일 경우 스택에 담긴 두 숫자를 뽑아 더하고 다시 스택에 담는다.

 

즉, 아래와 같은 조건과 과정을 따른다.

 

입력을 한 문자씩 읽을 때,

 

1) 숫자일 경우 스택에 push

 

2) '+'기호일 경우 pop으로 스택에 담겨진 두 개의 숫자를 뽑아 덧셈하고 이 결과를 다시 스택에 push

 

3) 입력을 끝까지 읽었을 때, 스택에 들어있는 결과를 출력

 

소스코드

package samsung;

import java.util.*;

public class s_1222 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for(int t = 1; t <= 10; t++) {
			int n = sc.nextInt();
			String s = sc.next();
			Stack <Character> st = new Stack();
			String result = "";
			for(int i = 0; i < s.length(); i++) {
				char c = s.charAt(i);
				if(c - '0' >= 0 && c - '0' <= 9) result += String.valueOf(c);
				else {
					if(st.isEmpty()) {
						st.push(c);
					}else {
						result += String.valueOf(st.pop());
						st.push(c);
					}
				}
			}
			while(!st.isEmpty()) {
				result += String.valueOf(st.pop());
			}
			
			Stack <Integer> st2 = new Stack();
			for(int i = 0; i < result.length(); i++) {
				char c = result.charAt(i);
				if(c - '0' >= 0 && c - '0' <= 9) {
					st2.push(c - '0');
				}
				else {
					int op1 = st2.pop();
					int op2 = st2.pop();
					st2.push(op1 + op2);
				}
			}
			System.out.println("#" + t + " " + st2.pop());
		}
	}
}