[프로그래머스] 카카오 인턴 - 수식 최대화

       문제 요약        

- 문제

https://school.programmers.co.kr/learn/courses/30/lessons/67257

 

         아이디어        

중위 표기식을 연산자 우선순위에 따라 후위 표기식으로 변환하고 

이에 대한 연산을 수행하는 계산기 문제

 

1. 연산자 우선순위를 정한다 

2. 연산자가

1) 아니라면 결과에 추가한다

2) 맞다면 연산자스택에서 현재 연산자보다 우선순위가 크거나 같은 연산자를 모두 결과에 추가한다 

 

3. 연산자 배열을 순서대로 접근하며 연산자인경우 (최신 연산자 그다음최신)를 수행한다

 

         소스코드        

 

 

import java.io.*;
import  java.util.*;
class Solution {

    public long solution(String expression) {
        long answer = 0;
        // + - * 
        List<String> tokens = new ArrayList<>();
        String num  =  "";
        for(int i = 0; i < expression.length(); i++) {
            if(expression.charAt(i) == '+' || expression.charAt(i) == '-' || expression.charAt(i) == '*') {
               if(!num.equals("")) {
                   tokens.add(num);
                   num  =  "";
                   tokens.add("" + expression.charAt(i));
               }
            } else {
                num +=  expression.charAt(i);
             }
            
        }
        if(!num.equals("")) {
            tokens.add(num);
        }
        for(int i  = 1; i <= 3; i++) {
            for(int j = 1; j  <= 3; j++) {
                for(int k = 1; k <= 3; k++) {
                    if(i == j || j == k || i == k)continue;
                    long result = calculate(tokens, i, j, k);
                    answer = Math.max(answer, result);
                }
            }
        }
        return answer;
    }
    static long calculate(List<String> tokens, int i, int j, int k) {
        Stack<String> operators  =  new Stack<>();
        Map<String, Integer> prio = new HashMap<>();
        prio.put("+", i);
        prio.put("-", j);
        prio.put("*", k);
        
        List<String> postfix = new ArrayList<>();
        for(String token : tokens) {
            if(!(token.equals("+") || token.equals("-") || token.equals("*"))) {
                postfix.add(token);
            } else {
                while(!operators.isEmpty() && prio.get(operators.peek()) >= prio.get(token)) {
                    postfix.add(operators.pop());
                }
                operators.push(token);
            }
        }
        while(!operators.isEmpty()) {
            postfix.add(operators.pop());
        }
        
        Stack<Long> numbers = new Stack<>();
        for(String v : postfix) {
            if(v.equals("+") || v.equals("-") || v.equals("*")) {
                long value2 = numbers.pop();
                long value1 = numbers.pop();
                if(v.equals("+")) {
                    numbers.push(value1 + value2);
                } else if(v.equals("-")) {
                    numbers.push(value1 - value2);
                } else {
                    numbers.push(value1 * value2);
                }
            } else {
                numbers.push(Long.parseLong(v));
            }
        }
        return Math.abs(numbers.pop());
    }
}