APCS實作解題： 先加後乘與函數（112年1月）

2023 年 7 月 1 日
| 尚無留言

https://zerojudge.tw/ShowProblem?problemid=j607

題目說明

給一個運算式，運算式的內容由數字、＋、＊ 和 某個函式f() 所組成，除了函式f()以外不會有額外的括號。請將此運算式依照 先加後乘 的方式運算。

函式 f(x1, x2, …, xn)定義： x1, x2, …, xn的最大值減去最小值。

解題思路

  • 可以用max( [x1, x2, …, xn] ) – min([x1, x2, …, xn] )實現函數
  • 使用stack, 紀錄f(, ) 出現時間，概念類似（112年六月考題：磁軌移動序列）
    • 只要看到”f(” 一定會再看見 “)”
    • f 可能是巢狀結構, 最內層的先計算，使用遞迴function recursion找出最內層數值
    • 計算出f( )答案
  • 先加減後乘除：
    • 將字串以”*”字元切割成許多子字串
    • 每個子字串相加
    • 子字串相乘得到答案

Python 解題

import sys


def scan_f(codes, idx):

  s = ''
  while idx < len(codes):

    if codes[idx]=='f' and codes[idx+1]=='(':
      idx += 2
      max_v, idx = scan_f(codes, idx)
      s += str(max_v)

    elif codes[idx]==')':

      # decode s
      arr = []
      for x in s.split(','):
        mul = 1
        for a in x.split('*'):
          psum = 0
          for b in a.split('+'):
            psum += int(b)

          mul *= psum

        arr.append(mul)

      idx += 1
       
      return max(arr)-min(arr), idx

    else:
      s += codes[idx]
      idx += 1


codes = input() #sys.stdin.readlines()[0]

s1 = ''
idx = 0
while idx < len(codes):

  if codes[idx]=='f' and codes[idx+1]=='(':
    idx +=2
    v, idx = scan_f(codes, idx)
    s1 += str(v)
  else:
    s1 += codes[idx]
    idx += 1

# +- before *

mul = 1
for a in s1.split('*'):
  psum = 0
  for b in a.split('+'):
    psum += int(b)

  mul *= psum

print(mul)
APCS