[プログラマ]式と最大化/Python/シーケンスの組合せ

式の最大化

質問する

参加者に所定の演算式を持つ文字列式をパラメータとして与える場合は、solution関数を完了して、優勝時に得られる最大ボーナス金額を返します.演算子の優先度(+>->xまたは->x>+)は定義できますが、2つ以上の演算子が同じ優先度を持つように、演算子の優先度(+、x>-またはx>+、-)は定義できません.

I/O例

expressionresult"100-200*300-500+20"60420
x>+>-演算子の優先順位をソートすると、最大の終端値が得られます.
演算順序は次のとおりです.
100-200x300-500+20
= 100-(200x300)-500+20
= 100-60000-(500+20)
= (100-60000)-520
= (-59900-520)
= -60420
したがって,優勝時に獲得できる賞金は|−60420|=60420である.

制限
式は、長さが3または100未満の文字列です.
-expressionの被演算子(オペランド)は999以下である.入力された式も演算子が負ではありません.
式には少なくとも1つの演算子が含まれます.
-同じ演算子の優先度が高い.

私の答え

現在の計算優先度の演算子が式にある場合、更新式の計算と作成には想像以上に時間がかかります.

from itertools import permutations

# 수식에서 연산자와 피연산자 분리
def split_expression(expression):
    operand = ''
    result = []
    for i, x in enumerate(expression):
        # 숫자일 경우
        if x.isdigit():
            operand += x
            if i == len(expression) - 1:
                result.append(operand)
        # 연산자일 경우
        else:
            result.append(operand)
            result.append(x)
            operand = ''
    return result
    
    
def solution(expression):
    ops = ["+", "-", "*"]
    # 연산자 3개의 우선순위 조합
    pm = list(permutations(ops))
    max_value = 0
    for i in range(6):
        exp = split_expression(expression)
        for j in range(3):
            # 현재 우선순위인 연산자가 수식에 있을 때 
            while pm[i][j] in exp:
            	# 연산자의 인덱스를 가져옴
                idx = exp.index(pm[i][j])
                exp = exp[:idx - 1] + [str(eval(''.join(exp[idx - 1:idx + 2])))] + exp[idx + 2:]
        max_value = max(max_value, abs(int(exp[0])))        
    return max_value

親の解析

こんなに簡単に解ける!!

import itertools

def solution(expression):
    symbols = ["-", "+", "*"]
    answer = []
    for i in itertools.permutations(symbols):
        first, second = i[0], i[1]
        lst = []
        for e in expression.split(first):
            temp = [f"({i})" for i in e.split(second)]
            lst.append(f'({second.join(temp)})')
        answer.append(abs(eval(first.join(lst))))
    return max(answer)