Problem:


小学生のイクタ君は、ある日おじいさんから数式が書かれた紙をもらった。
どうやらおじいさんは数式の答えの金額だけお小遣いをくれるらしい。
イクタ君はまだ足し算、引き算、掛け算しか習ってなかったので、数式にも足し算と引き算と掛け算しか使われていない。
通常の計算では足し算と引き算より掛け算を先に計算しなければならないのだが、イクタ君は演算子の優先順位についての理解があやふやだったので、とりあえず数式の計算結果が最大になるような都合の良い優先順位を考えることにした。

+&minus;&times;の3つの二項演算子と括弧を含む数式が与えられる。
3つの演算子の優先順位を任意に変更して、数式を最大化したときの計算結果を答えよ。

ただし、以下の点に注意せよ。

 演算子は必ず左結合である。
(同じ優先順位の演算子は必ず数式の左側から計算する。)

 異なる演算子が同じ優先順位であってもよい。

 一つの数式を計算している途中で優先順位を変更してはならない。

Input

入力は以下の形式で与えられる。

0〜9の数字と演算子'+','-','*'、括弧'(',')'で構成された数式

 正確に記述すると入力は以下のBNFで示される形式になっている

<expr> ::= ( <expr> ) | <number> | <expr> <op> <expr> 
 <op> ::= + | - | *

 <number>は非負整数を表す。

Constraints

入力は以下の制約を満たす。

 数式は200文字以下である。

 どのような優先順位を設定しても、計算の結果やその途中で64bit整数型でoverflowするようなことはない。

Output

数式から得られる最大値を1行で出力せよ。

Sample Input 1

3-2*3

Output for the Sample Input 1

3

 *の優先順位を-より低くすることでこのようになる。

Sample Input 2

(5-3*4)*(0-2+1)

Output for the Sample Input 2

21

 優先順位は+>*>-

Sample Input 3

1-2+3-4+5-6*0

Output for the Sample Input 3

3

 優先順位が一般的な場合

Sample Input 4

(1989967-3*1-211+4487)

Output for the Sample Input 4

8511076028



Sample input:
3-2*3


Sample output:
3

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

def func(S, pr):
    lst = []
    op_lst = ['+', '-', '*', '(', ')']
    ss = ''
    for c in S:
        if c in op_lst:
            if ss != '':
                lst.append(int(ss))
            lst.append(c)
            ss = ''
        else:
            ss += c
    if ss != '':
        lst.append(int(ss))
    while True:
        if not '(' in lst:
            break
        pos1 = lst.index('(')
        pos2 = lst.index(')')
        lst = lst[:pos1] + [calc(lst[pos1 + 1:pos2], pr)] + lst[pos2 + 1:]
    return calc(lst, pr)

def calc(lst, pr):
    for p in pr:
        for c in p:
            while True:
                if not c in lst:
                    break
                pos = lst.index(c)
                lst = lst[:pos - 1] + [eval(str(lst[pos - 1]) + c + str(lst[pos + 1]))] + lst[pos + 2:]
    return lst[0]

S = raw_input()
ans = -(10 ** 30)
for i, j, k in it.product([0, 1, 2], repeat = 3):
    pr = [[], [], []]
    pr[i].append('+')
    pr[j].append('-')
    pr[k].append('*')
    ans = max(ans, func(S, pr))

print ans

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

def calc(lst, pos, pr):
    ret = []
    while True:
        if pos >= len(lst):
            break
        if lst[pos] == '(':
            val, pos = calc(lst, pos + 1, pr)
            ret.append(val)
        elif lst[pos] == ')':
            pos += 1
            break
        else:
            ret.append(lst[pos])
            pos += 1
    lst = ret
    for p in pr:
        i = 0
        ret = []
        while i < len(lst):
            if lst[i] in p:
                ret[-1] = eval(str(ret[-1]) + lst[i] + str(lst[i + 1]))
                i += 2
            else:
                ret.append(lst[i])
                i += 1
    return ret[0], pos

S = raw_input()

lst = []
ss = ''
for c in S:
    if c in ['+', '-', '*', '(', ')']:
        if ss != '':
            lst.append(int(ss))
        lst.append(c)
        ss = ''
    else:
        ss += c
if ss != '':
    lst.append(int(ss))

ans = -(10 ** 30)
for i, j, k in it.product([0, 1, 2], repeat = 3):
    pr = [[], [], []]
    pr[i].append('+')
    pr[j].append('-')
    pr[k].append('*')
    ans = max(ans, calc(lst, 0, pr)[0])

print ans

Submission status: Wrong Answer

Solution code:
from string import digits
from itertools import product
S = input() + "$"

def parse(pri):
    code = "+-*"

    cur = 0
    def number():
        nonlocal cur
        c = S[cur]
        if c == '(':
            cur += 1 # '('
            v = expr(0)
            cur += 1 # ')'
            return v
        num = 0
        while S[cur] in digits:
            num = 10*num + int(S[cur])
            cur += 1
        return num
    def expr(level):
        nonlocal cur
        op = '+'
        result = 0
        while 1:
            if level == 2:
                v = number()
            else:
                v = expr(level+1)
            if op == '+':
                result += v
            elif op == '-':
                result -= v
            else:
                result *= v
            c = S[cur]
            if code.find(c) == -1 or pri[code.index(c)] != level:
                break
            op = c
            cur += 1
        return result
    return expr(0)
ans = 0
for pri in product(range(3), repeat=3):
    ans = max(ans, parse(pri))
print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 20
ops = ["+", "-", "*"]
nums = [str(i) for i in range(0, 10)]
priorities = []
for op1 in ops:
  for op2 in ops:
    for op3 in ops:
      if op1 != op2 and op1 != op3 and op2 != op3:
        priorities += [[op1], [op2], [op3]]
        priorities += [[op1], [op2, op3]]
        priorities += [[op1, op2], [op3]]
        priorities += [[op1, op2, op3]]

def calc(num_lst, op_lst, priority):
  for x in range(len(priority)):
    while op_lst:
      for i, op in enumerate(op_lst):
        if op in priority[x]:
          if op == "+":
            num_lst = num_lst[:i] + [num_lst[i] + num_lst[i + 1]] + num_lst[i + 2:]
          elif op == "-":
            num_lst = num_lst[:i] + [num_lst[i] - num_lst[i + 1]] + num_lst[i + 2:]
          else:
            num_lst = num_lst[:i] + [num_lst[i] * num_lst[i + 1]] + num_lst[i + 2:]
          op_lst.pop(i)
          break
      else:
        break
  return num_lst[0]

def parse(s, priority):
  num_lst = []
  op_lst = []
  p = 0
  if s[p] == "(":
    p += 1
    num, addp = parse(s[p:], priority)
    num_lst.append(num)
    p += addp

  elif s[p] in nums:
    acc = ""
    while s[p] in nums:
      acc += s[p]
      p += 1
    num_lst.append(int(acc))
  
  while p < len(s) and s[p] != ")":
    op_lst.append(s[p])
    p += 1
    acc = ""
    if s[p] == "(":
      p += 1
      num, addp = parse(s[p:], priority)
      num_lst.append(num)
      p += addp
    else:
      #print(s[p])
      while s[p] in nums:
        acc += s[p]
        p += 1
      num_lst.append(int(acc))
  p += 1

  return (calc(num_lst, op_lst, priority), p)

def main():
  s = "(" + input() + ")"
  ans = -INF
  for priority in priorities:
    a, _ = parse(s, priority)
    ans = max(ans, a)
  print(ans)
main()

Submission status: Wrong Answer

Solution code:
INF = 10 ** 20
ops = ["+", "-", "*"]
nums = [str(i) for i in range(0, 10)]
priorities = []
for op1 in ops:
  for op2 in ops:
    for op3 in ops:
      if op1 != op2 and op1 != op3 and op2 != op3:
        priorities.append([[op1], [op2], [op3]])
        priorities.append([[op1], [op2, op3]])
        priorities.append([[op1, op2], [op3]])
        priorities.append([[op1, op2, op3]])

def calc(num_lst, op_lst, priority):
  for x in range(len(priority)):
    while op_lst:
      for i, op in enumerate(op_lst):
        if op in priority[x]:
          if op == "+":
            num_lst = num_lst[:i] + [num_lst[i] + num_lst[i + 1]] + num_lst[i + 2:]
          elif op == "-":
            num_lst = num_lst[:i] + [num_lst[i] - num_lst[i + 1]] + num_lst[i + 2:]
          else:
            num_lst = num_lst[:i] + [num_lst[i] * num_lst[i + 1]] + num_lst[i + 2:]
          op_lst.pop(i)
          break
      else:
        break
  return num_lst[0]

def parse(s, priority):
  num_lst = []
  op_lst = []
  p = 0
  if s[p] == "(":
    p += 1
    num, addp = parse(s[p:], priority)
    num_lst.append(num)
    p += addp

  elif s[p] in nums:
    acc = ""
    while s[p] in nums:
      acc += s[p]
      p += 1
    num_lst.append(int(acc))
  
  while p < len(s) and s[p] != ")":
    op_lst.append(s[p])
    p += 1
    acc = ""
    if s[p] == "(":
      p += 1
      num, addp = parse(s[p:], priority)
      num_lst.append(num)
      p += addp
    else:
      #print(s[p])
      while s[p] in nums:
        acc += s[p]
        p += 1
      num_lst.append(int(acc))
  p += 1

  return (calc(num_lst, op_lst, priority), p)

def main():
  s = "(" + input() + ")"
  ans = -INF
  for priority in priorities:
    a, _ = parse(s, priority)
    print(priority, a)
    ans = max(ans, a)
  print(ans)
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

def calc(lst, pos, pr):
    ret = []
    while pos < len(lst):
        if lst[pos] == '(':
            val, pos = calc(lst, pos + 1, pr)
            ret.append(val)
        elif lst[pos] == ')':
            pos += 1
            break
        else:
            ret.append(lst[pos])
            pos += 1
    lst = ret
    for p in pr:
        i = 0
        ret = []
        while i < len(lst):
            if lst[i] in p:
                ret[-1] = eval(str(ret[-1]) + lst[i] + str(lst[i + 1]))
                i += 2
            else:
                ret.append(lst[i])
                i += 1
        lst = ret
    return lst[0], pos

S = raw_input()

lst = []
ss = ''
for c in S:
    if c in ['+', '-', '*', '(', ')']:
        if ss != '':
            lst.append(int(ss))
        lst.append(c)
        ss = ''
    else:
        ss += c
if ss != '':
    lst.append(int(ss))

ans = -(10 ** 30)
for i, j, k in it.product([0, 1, 2], repeat = 3):
    pr = [[], [], []]
    pr[i].append('+')
    pr[j].append('-')
    pr[k].append('*')
    ans = max(ans, calc(lst, 0, pr)[0])

print ans

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = S()

    t = []
    k = 0
    kf = False
    for c in s:
        if '0' <= c <= '9':
            k *= 10
            k += int(c)
            kf = True
        else:
            if kf:
                t.append(k)
            k = 0
            t.append(c)
            kf = False
    if kf:
        t.append(k)

    def calc(a,b,o):
        if o == '+':
            return a + b
        if o == '-':
            return a - b
        return a * b

    def f(s, ops):
        t = s[:]
        ff = True
        while ff:
            ff = False
            ti = -1
            for i in range(len(t)-1,-1,-1):
                if t[i] == '(':
                    ti = i
                    break
            if ti < 0:
                break
            tj = -1
            for i in range(ti+1,len(t)):
                if t[i] == ')':
                    tj = i + 1
                    break
            t[ti:tj] = [f(t[ti+1:tj-1], ops)]
            ff = True

        for i in range(3):
            nt = []
            for c in t:
                if isinstance(c, int):
                    if len(nt) > 1 and ops[nt[-1]] == i:
                        kt = calc(nt[-2],c,nt[-1])
                        nt[-2] = kt
                        del nt[-1]
                    else:
                        nt.append(c)
                else:
                    nt.append(c)
            t = nt
        return t[0]

    r = -inf
    for a in itertools.product(range(3), repeat=3):
        tr = f(t, {'+': a[0], '-': a[1], '*': a[2]})
        if r < tr:
            r = tr

    return r




print(main())

Submission status: Accepted

Solution code:
from string import digits
from itertools import product
S = input() + "$"

def parse(pri):
    code = "+-*"

    cur = 0
    def number():
        nonlocal cur
        c = S[cur]
        if c == '(':
            cur += 1 # '('
            v = expr(0)
            cur += 1 # ')'
            return v
        num = 0
        while S[cur] in digits:
            num = 10*num + int(S[cur])
            cur += 1
        return num
    def expr(level):
        nonlocal cur
        op = '+'
        result = 0
        while 1:
            if level == 2:
                v = number()
            else:
                v = expr(level+1)
            if op == '+':
                result += v
            elif op == '-':
                result -= v
            else:
                result *= v
            c = S[cur]
            if code.find(c) == -1 or pri[code.index(c)] != level:
                break
            op = c
            cur += 1
        return result
    return expr(0)
ans = -10**30
for pri in product(range(3), repeat=3):
    ans = max(ans, parse(pri))
print(ans)

Submission status: Accepted

Solution code:
INF = 10 ** 20
ops = ["+", "-", "*"]
nums = [str(i) for i in range(0, 10)]
priorities = []
for op1 in ops:
  for op2 in ops:
    for op3 in ops:
      if op1 != op2 and op1 != op3 and op2 != op3:
        priorities.append([[op1], [op2], [op3]])
        priorities.append([[op1], [op2, op3]])
        priorities.append([[op1, op2], [op3]])
        priorities.append([[op1, op2, op3]])

def calc(num_lst, op_lst, priority):
  for x in range(len(priority)):
    while op_lst:
      for i, op in enumerate(op_lst):
        if op in priority[x]:
          if op == "+":
            num_lst = num_lst[:i] + [num_lst[i] + num_lst[i + 1]] + num_lst[i + 2:]
          elif op == "-":
            num_lst = num_lst[:i] + [num_lst[i] - num_lst[i + 1]] + num_lst[i + 2:]
          else:
            num_lst = num_lst[:i] + [num_lst[i] * num_lst[i + 1]] + num_lst[i + 2:]
          op_lst.pop(i)
          break
      else:
        break
  return num_lst[0]

def parse(s, priority):
  num_lst = []
  op_lst = []
  p = 0
  if s[p] == "(":
    p += 1
    num, addp = parse(s[p:], priority)
    num_lst.append(num)
    p += addp

  elif s[p] in nums:
    acc = ""
    while s[p] in nums:
      acc += s[p]
      p += 1
    num_lst.append(int(acc))
  
  while p < len(s) and s[p] != ")":
    op_lst.append(s[p])
    p += 1
    acc = ""
    if s[p] == "(":
      p += 1
      num, addp = parse(s[p:], priority)
      num_lst.append(num)
      p += addp
    else:
      #print(s[p])
      while s[p] in nums:
        acc += s[p]
        p += 1
      num_lst.append(int(acc))
  p += 1

  return (calc(num_lst, op_lst, priority), p)

def main():
  s = "(" + input() + ")"
  ans = -INF
  for priority in priorities:
    a, _ = parse(s, priority)
    ans = max(ans, a)
  print(ans)
main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import product

def parse(S, op):
    """
    構文木を返す
    Sは普通の記法の式
    opは優先順序　通常は(*/: 1, +-: 2)
    """
    S = "0+({})".format(S)
    V = []
    for x in list("()+-*"):
        S = S.replace(x, " {} ".format(x))
    i = 0
    rank = 0
    O = []
    for s in S.split():
        if s == "(":
            rank += 1
        elif s == ")":
            rank -= 1
        elif s.isdigit():
            V.append(s)
            i += 1
        else:
            V.append(s)
            O.append([-rank, op[s], i])
            i += 1

    G = [[] for _ in range(len(V))]
    P = [-1]*len(V)
    O = sorted(O)
    
    def get_pair(i):
        while P[i] != -1:
            i = P[i]
        return i
    
    for _, _, i in O:
        l, r = get_pair(i-1), get_pair(i+1)
        G[i].extend([l, r])
        P[l], P[r] = i, i
    p = O[-1][2]
    return G, V, p

def make(G, V, p):
    def call(i):
        if V[i].isdigit():
            return V[i]
        else:
            assert len(G[i]) == 2
            left = call(G[i][0])
            right = call(G[i][1])
            return "({}{}{})".format(left, V[i], right)
    return call(p)

S = input()
ans = -float("inf")

for a, b, c in product(range(3), repeat=3):
    op = {}
    op["+"] = a
    op["-"] = b
    op["*"] = c
    ans = max(ans, eval(make(*parse(S, op))))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
S = input()
for x in "()+*-":
    S = S.replace(x, " {} ".format(x))
S = S.split()

def parse(pri, cur):

    def number():
        nonlocal cur
        if S[cur].isdigit():
            val = int(S[cur])
            cur += 1
            return val
        cur += 1
        val = expr(0)
        cur += 1
        return val
    
    def expr(level):
        nonlocal cur
        if level == 3:
            this = number()
        else:
            this = expr(level+1)
        while cur < len(S) and S[cur] in "+-*" and pri[S[cur]] == level:
            op = S[cur]
            cur += 1
            that = expr(level+1)
            if op == "+":
                this += that
            elif op == "-":
                this -= that
            else:
                this *= that
        return this
    return expr(0)

pri = {}
ans = -float("inf")
for P in product(range(3), repeat=3):
    pri["+"], pri["-"], pri["*"] = P
    ans = max(ans, parse(pri, 0))
print(ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

O = {'+': lambda l, r: l + r,
     '-': lambda l, r: l - r,
     '*': lambda l, r: l * r}

P = {'+': 0,
     '-': 0,
     '*': 0}

class Source():
    def __init__(self, S, i=0):
        self.S = S
        self.pos = i

def peek(S):
    return S.S[S.pos] if S.pos < len(S.S) else 'a'

def next(S):
    S.pos += 1

def expr(S, i):
    # print(S.pos)
    if i == 0:
        left = factor(S)
    else:
        left = expr(S, i - 1)

    while peek(S) in O and P[peek(S)] == i:
        ope = peek(S)
        next(S)
        if i == 0:
            right = factor(S)
        else:
            right = expr(S, i - 1)
            
        left = O[ope](left, right)
        
    # print(left, i)
    return left


def factor(S):
    if peek(S) == '(':
        next(S)
        res = expr(S, 2)
        next(S)
    else:
        res = num(S)
    return res

def num(S):
    sign = 1
    if peek(S) == '-':
        sign = -1
        next(S)
    res = 0
    while '0' <= peek(S) <= '9':
        res = res * 10 + int(peek(S))
        next(S)

    return sign * res

S = input()
ans = -int(1e19)

for plus in range(3):
    P['+'] = plus
    for minus in range(3):
        P['-'] = minus
        for times in range(3):
            P['*'] = times
            ans = max(ans, expr(Source(S), 2))
            
print(ans)

Submission status: Accepted

Solution code:

S = input()
y = [0,0,0]
ans = -1e64

def calc(s):
    #print(s)
    A = []
    i = 0
    cntr = 0
    s2 = ""
    for j,c in enumerate(s):
        if cntr > 0:
            if c == ')':
                cntr -= 1
                if cntr == 0:
                    A.append(calc(s2))
                    continue
            if c == '(':
                cntr += 1
            s2 = s2 + c
        else:
            if c.isdigit():
                i *= 10
                i += int(c)
            else:
                if c == '(':
                    cntr += 1
                    if cntr == 1:
                        s2 = ""
                    continue
                if s[j - 1] != ')':
                    A.append(i)
                i = 0
                A.append(c)
    A.append(i)
    #print(A)
    for i in range(3):
        j = 0
        while j < len(A):
            a = A[j]
            if a == "+" and y[0] == i:
                A[j - 1] += A[j + 1]
                del A[j : j + 2]
            elif a == "-" and y[1] == i:
                A[j - 1] -= A[j + 1]
                del A[j : j + 2]
            elif a == "*" and y[2] == i:
                A[j - 1] *= A[j + 1]
                del A[j : j + 2]
            else:
                j += 1
    return A[0]


for i in range(27):
    y[0] = i // 9
    y[1] = (i % 9) // 3
    y[2] = i % 3
    ans = max(ans, calc(S))

print(ans)