[프로그래머스#JS] 수식 최대화

[링크]

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

[풀이]

• for문을 연산자(+, -, *)들이 가질 수 있는 경우의 수만큼 돌린다.
  1. 중위표기법을 후위표기법 변환한다.
  • for문을 i=0부터 수식 문자열의 길이만큼 돌린다.
  • [문자가 연산자라면]스택에서 자기보다 우선순위가 높거나 같은 연산자를 후위표기법에 표기하고 연산자는 스택에 넣는다.
  • [문자가 연산자가 아니라면]후위표기법에 표기한다.
  • 스택에 남은 문자열을 후위표기법에 표기해준다.
  2. 후위표기법 연산한다.
  • for문을 i=0부터 후위표기법의 길이만큼 돌린다.
  • [문자열이 연산자라면]스택에서 2개의 수를 꺼내 계산한뒤 넣는다.
  • [문자열이 연산자가 아니라면]스택에 넣는다.
  3. 각각의 경우의 수의 결과값을 비교하여 제일 큰 값을 return한다.

[코드]

const prioritys = [{'+':0, '-':1, '*':2}
                  ,{'+':2, '-':0, '*':1}
                  ,{'+':1, '-':2, '*':0}
                  ,{'+':0, '-':2, '*':1}
                  ,{'+':1, '-':0, '*':2}
                  ,{'+':2, '-':1, '*':0}];
                  
function solution(expression) {
    let answer = 0;
    for(const priority of prioritys) {
        let postfix = [''];
        const stack = new Array();
        
        /* 중위표기법 -> 후위표기법 변환 */
        for(let i = 0; i < expression.length; i++) {
            if(expression[i] == '+' || expression[i] == '-' || expression[i] == '*') {
                while(stack.length) {
                    let top = stack.pop();
                    if(priority[expression[i]] <= priority[top]) {
                        postfix.push(top);
                    } else {
                        stack.push(top);
                        break;
                    }
                }
                stack.push(expression[i]);
                postfix.push('');
            } else {
                let temp = postfix.pop();
                postfix.push(temp + expression[i]);
            }
        }
        while(stack.length) {
            postfix.push(stack.pop());
        }
        
        /* 후위표기법 연산 */
        for(let i = 0; i < postfix.length; i++) {
            if(postfix[i] == '+') {
                stack.push(stack.pop() + stack.pop());
            } else if(postfix[i] == '-') {
                let b = stack.pop();
                let a = stack.pop();
                stack.push(a - b);
            } else if(postfix[i] == '*') {
                stack.push(stack.pop() * stack.pop());
            } else {
                stack.push(parseInt(postfix[i]));
            }
        }
        answer = Math.max(answer, Math.abs(stack.pop()));
    }
    return answer;
}