Phân tích: Decision Tree

Phần khó nhất ở đây là việc phân tích (parsing) cây. Một cách dễ dàng để thực hiện việc này là sử dụng kỹ thuật gọi là đệ quy đi xuống (recursive descent). Ngữ pháp của cây được định nghĩa đệ quy, vì vậy việc phân tích nó một cách đệ quy cũng là điều hợp lý. Dưới đây là một giải pháp bằng Python.

import re
import sys
inp = sys.stdin

tokens = None
ti = -1

def ReadInts():
  """Reads several space-separated integers on a line.
  """
  return tuple(map(int, inp.readline().strip().split(" ")))

def NextToken():
  """Consumes the next token from 'tokens'.
  """
  global ti
  assert 0 <= ti < len(tokens)
  ti += 1
  return tokens[ti - 1]

def ParseNode():
  """Parses from 'tokens' and returns a tree node.
  """
  global ti
  assert NextToken() == "("
  node = {"weight": float(NextToken())}
  tok = NextToken()
  if tok == ")":
    return node
  node["feature"] = tok
  node[True] = ParseNode()
  node[False] = ParseNode()
  assert NextToken() == ")"
  return node

def ParseTree(s):
  """Initializes 'tokens' and 'ti' and parses a tree.
  """
  global tokens
  global ti
  s = re.compile(r"\(").sub(" ( ", s)
  s = re.compile(r"\)").sub(" ) ", s)
  s = re.compile(r"[ \n]+").sub(" ", " %s " % s)
  tokens = s[1:-1].split(" ")
  ti = 0
  return ParseNode()

def Evaluate(tree, features):
  ans = tree["weight"]
  if "feature" in tree:
    ans *= Evaluate(tree[tree["feature"] in features], features)
  return ans

if __name__ == "__main__":
  N = ReadInts()[0]
  for prob in xrange(1, N + 1):
    n_lines = ReadInts()[0]
    lines = [inp.readline() for _ in xrange(n_lines)]
    tree = ParseTree(" ".join(lines))
    n_queries = ReadInts()[0]
    print "Case #%d:" % prob
    for _ in xrange(n_queries):
      features = set(inp.readline().strip().split(" ")[2:])
      print "%.7f" % Evaluate(tree, features)

Đối với mỗi bộ thử nghiệm, chúng ta đọc n_lines dòng chứa định nghĩa cây, chúng ta ghép chúng lại với nhau bằng các khoảng trắng và truyền chuỗi kết quả vào hàm ParseTree().

Trong ParseTree(), chúng ta thực hiện một số bước "tiền xử lý" để làm cho chuỗi dễ phân tích hơn. Đầu tiên, chúng ta đặt các khoảng trắng xung quanh mỗi dấu ngoặc đơn bằng cách sử dụng hai biểu thức chính quy (regular expressions) đơn giản. Tiếp theo, chúng ta thay thế mỗi chuỗi các ký tự khoảng trắng bằng một khoảng trắng duy nhất và đảm bảo luôn có chính xác một ký tự khoảng trắng ở đầu và cuối đầu vào. Cuối cùng, chúng ta loại bỏ các khoảng trắng ở đầu và cuối và chia phần còn lại thành các token.

Hàm ParseNode() thực hiện phần còn lại. Nó sử dụng hàm NextToken() để đọc từng token một từ danh sách tokens và trả về một cấu trúc từ điển (dictionary) đơn giản đại diện cho một nút cây.

Khi đã có cây dưới dạng từ điển, sau đó chúng ta sử dụng Evaluate() để thực hiện duyệt cây từ gốc đến lá và tính toán câu trả lời cho mỗi con vật đầu vào.

Sử dụng các trình phân tích cú pháp có sẵn trong các ngôn ngữ động

Một số thí sinh đã nhận thấy rằng có một cách thậm chí còn dễ dàng hơn để phân tích cây. Hầu hết các ngôn ngữ thông dịch, động đều cho phép bạn truy cập vào trình phân tích cú pháp tích hợp của chúng, và bằng cách thao tác một chút với đầu vào, bạn có thể làm cho trình thông dịch của ngôn ngữ đó thực hiện việc phân tích cho bạn! Điều này có nghĩa là sử dụng eval trong JavaScript hoặc Python, hoặc read trong Lisp. Hãy xem một số lời giải ngắn nhất tại 1b-a.pastebin.com/d4631e678.

Dựa trên phân tích chính thức của Google Code Jam.