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

문제

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

예를 들어

“3+4+5*6+7”

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

"34+56*+7+"

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

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

 

풀이방법

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

 

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

 

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

 

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

 

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

 

입력을 한 문자씩 읽을 때,

 

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

 

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

 

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

 

   2-2) 스택이 차 있을 경우 ('*'기호가 '+'기호보다 우선순위가 높다)

       2-2-a) 읽어들인 입력이 스택의 top에 있는 값보다 우선순위가 높을 경우 push

       2-2-b) 읽어들인 입력의 스택의 top에 있는 값보다 우선순위가 낮거나 같은 경우 스택의 값을 pop한 뒤 입력을 push

 

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

 

 

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

 

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

 

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

 

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

 

입력을 한 문자씩 읽을 때,

 

1) 숫자일 경우 스택에 push

 

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

 

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

 

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

 

소스코드

package samsung;

import java.util.*;

public class s_1223 {
	public static int get_prior(char c) {
		if(c == '*')
			return 1;
		else if(c == '+')
			return 3;
		else
			return -1;
	}
	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> op = new Stack();
			String r = "";
			for(int i = 0; i < s.length(); i++) {
				char c = s.charAt(i);
				if(c - '0' >= 0 && c - '0' <= 9) {
					r += String.valueOf(c);
				}
				else {
					if(op.isEmpty()) {
						op.push(c);
					}
					else {
						if(get_prior(op.peek()) <= get_prior(c)) {
							r += String.valueOf(op.pop());
							op.push(c);
						}
						else {
							op.push(c);
						}
					}
				}
			}
			while(!op.isEmpty()) {
				r += String.valueOf(op.pop());
			}
			
			Stack <Integer> nums = new Stack();
			for(int i = 0; i < r.length(); i++) {
				char c = r.charAt(i);
				if(c - '0' >= 0 && c -'9' <= 0) nums.push(c - '0');
				else {
					int tmp1 = nums.pop();
					int tmp2 = nums.pop();
					if(c == '*') nums.push(tmp1 * tmp2);
					else if(c == '+') nums.push(tmp1 + tmp2);
				}
			}
			System.out.println("#" + t + " " + nums.pop());
		}
	}
}