/ SWEA

SWEA_1224_계산기3_JAVA

문제 : 계산기3

SWEA문제는 로그인을 해야 열람할 수 있습니다.

링크 : SWEA_1224_계산기3

접근 방식

덧셈, 뺄셈, 괄호가 있는 중위표기법의 계산식을 후위표기법으로 바꾸고, 해당 후위표기법대로 계산하여 결과를 출력하라는 요청이다.

중위표기법을 스택을 통해 후위표기법으로 먼저 바꾸는 작업을 거친다. 그 규칙은 다음과 같다.

  1. 피연산자는 바로 표기식에 더한다.

  2. 연산자가 들어왔을 경우, 자신보다 우선순위가 높거나 같은 것들을 모두 꺼내 표기식에 더하고 자신을 스택에 푸시한다.

  3. ’(‘는 무조건 스택에 푸시한다.

  4. ’)’를 만나면, ‘(‘를 만날때까지 스택에서 꺼내 표기식에 더한다.

위의 방법으로 후위표기법으로 바꾸는데 성공했다면 다음은 계산이다. 스택을 통해 후위표기법의 계산식을 계산해보자.

  1. 피연산자는 스택에 푸시한다.

  2. 연산자를 만날 경우 스택에서 2번 숫자를 꺼내서 연산을 진행하고, 그 연산된 값을 다시 스택에 푸시한다.

  3. 연산을 모두 마친 후 스택에 남아있는 수가 계산 결과이다.

풀이 방법

  1. 중위표기식 문자열을 읽어와서 char형 배열로 저장한다.

  2. 후위표기식 문자열을 저장할 List 객체와 후위표기식으로 변환하기 위한 Stack을 생성한다.

  3. 문자열의 길이만큼 반복하고, 내부는 switch문을 통해 문자열과 숫자를 구분하여 위의 후위표기법 규칙대로 후위표기식을 만든다.

  4. 생성된 후위표기식을 스택을 이용해 계산한다. 기존 생성한 스택은 문자형이었으므로, 정수형 스택을 새로 생성해준다.

  5. 계산된 결과를 출력한다.

소스 코드


import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class D4_1224_계산기3 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		System.setIn(new FileInputStream("input_1224.txt"));

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		for(int tc=1;tc<=10;tc++) {
			int N = Integer.parseInt(in.readLine());

			char[] chars = in.readLine().toCharArray();
//			char[] chars = "3+(4+5)*6+7".toCharArray();

			Stack<Character> stack = new Stack<>();
			List<Character> list = new ArrayList<>();
			// 후위표기법으로 만들기
			for(int i=0;i<N;i++) {
				char m = chars[i];
				switch(m) {
				case '*':
					stack.push(m);
					break;
				case '+':
					while(!stack.isEmpty()) {
						if(stack.peek() == '(') {
							break;
						}
						list.add(stack.pop());
					}
					stack.push(m);
					break;
				case '(':
					stack.push(m);
					break;
				case ')':
					while(!stack.isEmpty()) {
						if(stack.peek() == '(') {
							stack.pop();
							break;
						}
						list.add(stack.pop());
					}
					break;
				default:
					list.add(m);
				}
			}
			while(!stack.isEmpty()) {
				list.add(stack.pop());
			}
	//		// 잘 변환 되었다.
//			System.out.println(list+"\n");
			Stack<Integer> stack2 = new Stack<>();
			// 후위표기법 계산하기
			for(int i=0,n = list.size();i<n;i++) {
				char m = list.get(i);
				switch(m) {
				case '+':
					stack2.push(calcul(stack2.pop(),stack2.pop(),m));
					break;
				case '*':
					stack2.push(calcul(stack2.pop(),stack2.pop(),m));
					break;
				default:
					stack2.push(m-'0');
				}
			}
			int answer = stack2.pop();
			System.out.printf("#%d %d\n",tc,answer);
		}
	}

	public static int calcul(int A, int B, char cal) {
		switch(cal) {
		case '+':
			return A + B;
		case '*':
			return A * B;
		}
		return -1;
	}
}