문제

연산자와 피연산자로 이루어진 문자열을 구분하여 연산을 수행하는 문제이다. 순열을 이용하여 연산자 우선순위를 구하고 해당 우선순위에 대한 결과 값을 비교한다.

풀이

순서

1.문자열에서 연산자와 피연산자를 구분
2.순열로 만들어질수 있는 연산자우선순위 경우들 계산
3.연산자 우선순위로 연산

문자열에서 연산자와 피연산자를 구분

	public static ArrayList<Long> operand = new ArrayList<>();
    public static ArrayList<String> operator = new ArrayList<>();
    
    	int index=0;
        
        //피연산자, 연산자 배열 만들기
        for(int i=0;i<expression.length();i++){
            if(expression.charAt(i) == '+' || expression.charAt(i) == '-' || expression.charAt(i) == '*'){
                operand.add(Long.parseLong(expression.substring(index,i)));
                index = i + 1;
                operator.add(expression.substring(i,index));
            }
        }
        operand.add(Long.parseLong(expression.substring(index,expression.length())));

한단어씩 비교하며 +, -, *같이 연산자가 나오면 operator에 저장하고, 이전에 저장해둔 숫자들은 operand에 저장한다. 연산자가 나오지 않으면 단순히 숫자들을 이어 붙힘.

순열로 만들어질 수 있는 연산자우선순위 경우들 계산

처음에 잘못된 우선순위 비교를 하였는데

public static String[] priority ={"-+*", "-*+", "+-*", "+*-", "*-+", "*+-"};

배열로 -+*, -*+, +-*, +*-, *-+, *+-로 우선순위를 지정해 놓고 차례대로 바꾸어가며 결과값을 비교하였다. 하지만 연산자가 3개일 경우는 제대로 동작하였으나 2개인 경우, 1개인 경우는 잘 작동하지 않았다.

	public static String[] oper = {"+","-","*"}; //연산자 목록
    public static String[] priority = new String[3]; //우선순위 순열
    public static boolean[] visited = new boolean[3]; //여부확인용
    
    permutation(0,oper.length); //순열
    
    
    //순열
	static void permutation(int depth,int r) {
		if(depth == r) {
			getMax(); //우선순위에 맞게 계산
			return;
		}
		for(int i=0;i<oper.length;i++) {
			if(!visited[i]) {
				visited[i] = true;
				priority[depth] = oper[i];
				permutation(depth+1,r);
				visited[i] = false;
			}
		}
	}

순열(Permutation)에 대한 이해가 필요하다. 연산자의 갯수와 종류도 중요하기 때문에 순열을 사용하여 필요한 경우를 생각해야 한다.

연산자 우선순위로 연산

	//연산자 우선순위 별로 결과 구함
	public static void getMax() {
        long result=0;
        int index;
        ArrayList<Long> temp_operand = new ArrayList<Long>();
        temp_operand.addAll(operand); //피연산자 불러오기
        ArrayList<String> temp_operator = new ArrayList<String>();
        temp_operator.addAll(operator); //연산자 불러오기
        
        for(int i=0;i<priority.length;i++){ //연산자 별로
        	String opt = priority[i]; //연산자 불러오기
            
            for(index=0;index<temp_operator.size();index++){ //연산자 하나하나씩 비교
                
                if(temp_operator.get(index).equals(opt)){ //현재 우선순위 연산자면
                    long num1 = temp_operand.get(index);
                    long num2 = temp_operand.get(index+1); //피연산자 가져오기
                    switch(opt){ //연산
                        case "+":
                            result = num1 + num2;
                            break;
                        case "-":
                            result = num1 - num2;
                            break;
                        case "*":
                            result = num1 * num2;
                            break;
                    }
                    temp_operand.set(index+1,result);
                    temp_operand.remove(index); //2개의 피연산자는 1개로
                    temp_operator.remove(index); //1개의 연산자는 0개로
                    
                    index--; //계산후 인덱스 조정
                }
            }
            
           
        }
        if(answer < Math.abs(temp_operand.get(0))) //최댓값보다 크면
            answer = Math.abs(temp_operand.get(0)); //최대값으로
	}

연산자의 우선순위 순서대로, 연산자 하나하나씩 계산한다. 이때 연산자 n개에 대하여 피연산자는 항상 n+1개 이므로 i번째 연산자는 i번째 피연산자와 i+1번째 연산자로 연산한다.
2개의 피연산자는 연산후 결과 1개의 피연산자로, 1개의 연산자는 더이상 사용 하지않으므로 0개로 조절한다.

GitHub

https://github.com/ds02168/Study_Algorithm/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%EC%9E%90%EB%B0%94/Level2/MaximumArith.java