백준 16228 GCC의 유산

https://www.acmicpc.net/problem/16228

16228번: GCC의 유산

 

 

계산식이 주어졌을 때 이를 계산하는 문제다.

주어지는 연산자는 () [괄호], +, - ,<?(최대값) , >?(최소값)이다.

 

우선 괄호 같은 경우는 스택을 이용하여 가장 안쪽 괄호를 찾을 수 있다..

( '괄호'가 나올때마다 그 index를 스택에 쌓고

')' 괄호가 나올떄 스택에서 pop하면 ')'에 대칭되는 '(' 의 index를 구할수 있다.

이 두 index를 이용하여 가장 안쪽 괄호의 부분 문자열을 구할수 있다.

 

단 ((30+44)) 처럼 무의미하게 괄호가 여러번 쳐져있을 수도 있으므로

String 의 replace함수를 이용하여 안전하게 제거해준다.

 

이제 괄호 속의 계산식을 계산해줘야한다.

40>?3+4<?1>?49 같은 문자열이 들어올것이다.

Java의 StringTokenizer나 split 함수를 이용하면 쉽게 이 문자열을

operand(피연산자)와 operator(연산자)로 나눌수 있다.

이를 리스트에 따로따로 저장해준다.

따로 저장된 연산자와 피연산자를 이용해서

연산자가 높은 >? <? 부터 먼저 계산하고 (미리 >? <? 연산자를 한글자 짜리 !,~,*,/ 등으로 바꾸면 더 쉽게 처리할수 있다.)

연산자가 낮은 + - 를 나중에 계산해주면 끝이다.

 

PS) 카카오 인턴에 이보다 약간 쉬운 버전이 출제되었다.(괄호가 없는 버전)

한번쯤 파싱을 연습해보면 좋은 문제다

 

package 백준;

import java.io.*;
import java.util.*;

public class Gcc의유산 {
	public static class MyScanner {
		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {
			bf = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}

			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

	}

	static String s;
	static Map<String, Integer> priority;
	static int lastLeft = -1;
	static Stack<Integer> lp;

	static int cal(StringBuilder s, int idx, boolean flag) {
		if (idx == s.toString().length() - 1 && flag == true || idx == s.toString().length()) {
			String t = s.toString().replace("(", "");
			t = t.replace(")", "");
			List<String> operatorList = new ArrayList<String>();
			List<String> operandList = new ArrayList<String>();
			StringTokenizer st = new StringTokenizer(t, "~!+-()", true);

			while (st.hasMoreTokens()) {
				String token = st.nextToken();

				if ("+-!~".contains(token)) {
					operatorList.add(token);
				} else {
					operandList.add(token);
				}
			}

			for (int i = 0; i < operatorList.size(); i++) {
				if (operatorList.get(i).equals("~")) {// 최소값
					String left = operandList.get(i);
					String right = operandList.get(i + 1);
					String res = Integer.toString(Math.min(Integer.parseInt(left), Integer.parseInt(right)));
					operandList.set(i, res);
					operandList.remove(i + 1);
					operatorList.remove(i);
					i--;

				} else if (operatorList.get(i).equals("!")) {
					// 최대값
					String left = operandList.get(i);
					String right = operandList.get(i + 1);

					String res = Integer.toString(Math.max(Integer.parseInt(left), Integer.parseInt(right)));
					operandList.set(i, res);
					operandList.remove(i + 1);
					operatorList.remove(i);
					i--;
				}
			}

			for (int i = 0; i < operatorList.size(); i++) {
				if (operatorList.get(i).equals("+")) {// 최소값
					String left = operandList.get(i);
					String right = operandList.get(i + 1);
					String res = Integer.toString((Integer.parseInt(left) + Integer.parseInt(right)));
					operandList.set(i, res);
					operandList.remove(i + 1);
					operatorList.remove(i);
					i--;

				} else if (operatorList.get(i).equals("-")) {
					String left = operandList.get(i);
					String right = operandList.get(i + 1);
					String res = Integer.toString(Integer.parseInt(left) - Integer.parseInt(right));
					operandList.set(i, res);
					operandList.remove(i + 1);
					operatorList.remove(i);
					i--;
				}
			}
			return Integer.parseInt(operandList.get(0));
		}
		if (s.charAt(idx) == '(') {
			lp.push(idx);
			flag = false;
		} else if (s.charAt(idx) == ')') {

			int r = lp.pop();
			StringBuilder substr = new StringBuilder(s.substring(r + 1, idx));
			flag = true;
			int p = cal(substr, 0, flag);

			s = s.replace(r, idx + 1, Integer.toString(p));

			idx -= (idx + 1 - r);
			idx += Integer.toString(p).length();
		}

		return cal(s, idx + 1, flag);

	}

	public static void main(String[] args) {
		MyScanner sc = new MyScanner();

		s = sc.next();
		s = s.replaceAll("<[?]", "~");
		s = s.replaceAll(">[?]", "!");
		StringBuilder sb = new StringBuilder();
		sb.append(s);
		lp = new Stack<Integer>();
		System.out.println(cal(sb, 0, true));

	}

}