[プログラマ]式の最大化(Javascript)



ソース:プログラマ

質問する


ITベンチャーを運営するライアンは、毎年社内のハッカー大会を開き、勝者にボーナスを支給している.
今大会は、これまでの大会とは異なる方式で優勝者の賞金を決める.
「ハッカートン」大会に参加するすべての参加者に対して、1つの数値と3つの演算子(+、-、*)を渡すだけで演算式が得られます.参加者のタスクは、伝達された式に含まれる演算子の優先度を自由に再定義できる最大の数値を提出することです.
ただし、演算子の優先度を再定義する場合は、同じ優先度の演算子は使用できません.すなわち、+>->または->+などの演算子優先度を定義できますが、演算子優先度を定義することはできません.2つ以上の演算子(+、>-または>+、-)が同じ優先度になるようにします.式に2つの演算子が含まれている場合、定義できる演算子の優先度は2になります!=2つの演算子、3つの演算子の場合は3!=6種類の組み合わせがあります.
計算結果が負数の場合は、その数値の節値に変換してコミットし、コミットされた数値の最大の参加者を優勝者として選択し、優勝者がコミットした数値を優勝者ボーナスとして選択します.
たとえば、参加者の4人が次の式を受け取ったとします.
"100-200*300-500+20"
通常、加算および減算は、数学および計算で約束された演算子の優先度に基づいて等しく、加算および減算の優先度が高く、それぞれ>+および-と定義されます.
競争ルールに従って、+>->または->>+などの演算子の優先度を定義できますが、演算子の優先度を定義することはできません.2つ以上の演算子(+、>-または>+、-)が同じ優先度になります.
式には3つの演算子があるので、可能な演算子の優先度は3!=+>->を使用して6つの演算子を優先順位付けすると、結リンゴの値は22000ウォンになります.
逆に、*>+>-を使用して演算子を優先順位付けすると、式の結リンゴ値は-60420になりますが、ルールによっては優勝時のボーナスは60420ウォンで絶対値になります.
参加者に所定の演算式を持つ文字列式をパラメータとして与える場合は、solution関数を完了して、優勝時に得られる最大ボーナス金額を返します.
せいげんじょうけん
  • 式は、3または100より長い文字列です.
  • 式は、スペース、カッコを使用せずに、数値と3つの演算子(+、-、*)のみを使用する演算式です.入力として無効な式は指定されません.
  • (「402+-561*」)は、正しい中位数ではないため、無効な式を提供しません.
  • 式の被演算子(オペランド)は999以下である.
  • (すなわち、「100-2455*458+12」)は、999より大きい被演算子を含む式を入力として提供しない.
  • "-56+100"のように、入力された式も演算子によって負数ではありません.
  • 式には、少なくとも1つの演算子が含まれます.
  • 演算子の優先度をどのように適用しても、式の中間計算値と最終結アップル値は263-1を下回るように入力されます.
  • たとえば、
  • では、前の演算子の優先度が高くなります.
  • 問題を解く


    問題を要約すると,演算子の優先度を6つのケースとし,それぞれのケースで最大の演算結果を求めることができる.

    インプリメンテーションコード

    const solution = expression => {
        const answer = [];
        //우선순위대로 나열한 경우의 수이다.
        const orders = ['+-*','+*-','-+*','-*+','*-+','*+-'];
        //문자열 연산자로 계산한다.
        const calc = (a,b,operator) => {
            if(operator === '+'){
                return Number(a)+Number(b);
            }
            else if(operator === '-'){
                return Number(a)-Number(b);
            }
            else{
                return Number(a)*Number(b);
            }
        }
        //모든 경우의 수에 대하여
        for(const order of orders){
            //숫자와 연산자를 각각 배열로 관리
            let numbers = expression.split(/[-*+]/g);
            let operators = expression.match(/[^0-9]/g);
            const ord = order.split('');
            //경우의 수 중 하나에서 우선순위에 따라 반복한다.
            for(const o of ord){
                let i = 0;
                //첫 우선순위가 연산자를 담고 있는 배열에서 없어질 때까지 반복
                while(operators.includes(o)){
                     if(operators[i] === o){
                         let result = calc(numbers[i],numbers[i+1],operators[i]);
                         numbers.splice(i,2,result);
                         operators.splice(i,1);
                         i=0;
                    }
                    else{
                        i+=1;
                    }
                }
            }
            //계산이 끝난 절댓값을 정답 배열에 넣어준다.
            answer.push(Math.abs(numbers[0]));
        }
        //정답들 중 가장 큰 값 반환.
        return Math.max(...answer);
    }