Bài tập | NEU OJ

Một số trình biên dịch/thông dịch cho ngôn ngữ tính toán khoa học cần tính đạo hàm của biểu thức tại một điểm cụ thể bằng cách duyệt AST và áp dụng quy tắc đạo hàm tương ứng với từng loại nút — đây là nguyên lý cơ bản của kỹ thuật automatic differentiation.

Cho một biểu thức tiền tố chỉ chứa một biến duy nhất x, hằng số nguyên không âm, và các toán tử hai ngôi $+, -, \times, \div, {}^{\wedge}$ (viết là + - * / ^), trong đó toán hạng bên phải của ^ luôn là một hằng số nguyên không âm (số mũ). Cho giá trị $x_0$ cụ thể, hãy tính $f(x_0)$ và $f'(x_0)$ bằng cách đánh giá đệ quy trên cây theo các quy tắc:

(u+v)' &= u'+v' & (u-v)' &= u'-v' \\ (u \times v)' &= u'v+uv' & (u \div v)' &= \frac{u'v-uv'}{v^2} \\ (u^{n})' &= n\,u^{n-1}u' & & \end{aligned}$$ với $u' = $ đạo hàm của biến `x` là $1$, đạo hàm của hằng số là $0$. Đề bảo đảm không xảy ra chia cho 0 khi đánh giá $f$ và $f'$ tại $x_0$ đã cho.

Định dạng đầu vào:
Dòng 1: biểu thức tiền tố, các token cách nhau bởi khoảng trắng. Dòng 2: một số thực $x_0$ (có thể âm, có thể có phần thập phân).
Định dạng đầu ra:
In ra trên một dòng hai số thực $f(x_0)$ và $f'(x_0)$ , cách nhau bởi một khoảng trắng, mỗi số làm tròn và hiển thị đúng 6 chữ số thập phân.

Ví dụ: với biểu thức + ^ x 2 * 3 x (tức $f(x)=x^2+3x$ ) và $x_0=2$ : $f(2)=4+6=10$ , $f'(x)=2x+3 \Rightarrow f'(2)=7$ . Output: 10.000000 7.000000.

solution

Đề bài: [Trình biên dịch] Đạo hàm số trên cây cú pháp bằng quy tắc đệ quy