C Academy · บทเรียน

ประเมินค่าต้นไม้

คำนวณผลลัพธ์

ประเมินค่าต้นไม้ เป็นบทเรียน C Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน C Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส C Academy มีบทเรียนทั้งหมด 4 บทเรียน

การเดินผ่าน AST

การประเมินผลคือการเดินต้นไม้แบบหลังไปก่อน โดยคำนวณโหนดย่อยก่อน แล้วจึงรวมผลด้วยตัวดำเนินการของโหนด ใบไม้ที่เป็นตัวเลขจะคืนค่าของตัวเองโดยตรง

ตัวแปลผลที่เดินผ่านต้นไม้นี้เป็นแบ็กเอนด์ที่ง่ายที่สุดเท่าที่ตัวแปลผลจะมีได้

ลายเซ็นของฟังก์ชันประเมินผล

ตัวประเมินผลของเรารับตัวชี้ไปยังโหนดและคืนค่าจำนวนเต็ม เนื่องจากต้นไม้มีการเรียกซ้ำ ฟังก์ชันนี้จึงเป็นฟังก์ชันเรียกซ้ำด้วย

สำหรับภาษาที่ใช้เลขทศนิยม คุณอาจคืนค่า double หรือค่าที่มีป้ายกำกับแทน

int eval(Node *n);  /* returns the integer value of the subtree */

การประเมินผลใบไม้

กรณีพื้นฐานจะหยุดการเรียกซ้ำ เมื่อโหนดเป็นตัวเลข ค่าของโหนดนั้นก็คือคำตอบของต้นไม้ย่อยดังกล่าว

การเรียกซ้ำทุกครั้งต้องไปถึงกรณีพื้นฐาน มิฉะนั้นจะไม่มีวันสิ้นสุด

int eval(Node *n) {
  if (n->kind == N_NUM) {
    return n->value;
  }
  /* ... handle N_BINOP below ... */
  return 0;
}

การประเมินผล BinOp

สำหรับโหนดตัวดำเนินการ เราจะเรียกซ้ำเข้าไปยังโหนดย่อยทั้งสอง จากนั้นจึงใช้ตัวดำเนินการ การประเมินด้านซ้ายก่อนด้านขวาทำให้ได้ลำดับจากซ้ายไปขวาตามปกติ

การใช้ switch กับอักขระตัวดำเนินการช่วยให้ตรรกะอ่านได้ง่าย

int eval(Node *n) {
  if (n->kind == N_NUM) return n->value;
  int l = eval(n->bin.left);
  int r = eval(n->bin.right);
  switch (n->bin.op) {
    case '+': return l + r;
    case '-': return l - r;
    case '*': return l * r;
    case '/': return l / r;
  }
  return 0;
}

การป้องกันการหารด้วยศูนย์

การหารจำนวนเต็มด้วยศูนย์เป็นพฤติกรรมที่ไม่ได้กำหนดในภาษา C และโดยทั่วไปจะทำให้กระบวนการทำงานล้มเหลว ตัวแปลผลที่ปลอดภัยจะตรวจตัวหารก่อน

การรายงานข้อผิดพลาดขณะทำงานอย่างชัดเจนย่อมดีกว่าการเกิด SIGFPE ที่ควบคุมไม่ได้

#include <stdio.h>
#include <stdlib.h>

static int safe_div(int a, int b) {
  if (b == 0) {
    fprintf(stderr, "runtime error: division by zero\n");
    exit(1);
  }
  return a / b;
}

การประเมินผลตั้งแต่ต้นจนจบ

ที่นี่ ต้นไม้ที่สร้างขึ้นด้วยตนเองสำหรับ (2 + 3) * 4 จะถูกประเมินผลเป็น 20 ฟังก์ชัน eval เดียวกันนี้สามารถทำงานกับต้นไม้ใด ๆ ที่ตัวแยกวิเคราะห์สร้างขึ้นได้

เรียกใช้เพื่อยืนยันว่าการเดินต้นไม้แบบหลังไปก่อนคำนวณคำตอบได้ถูกต้อง

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
  int is_num; int value;
  char op; struct Node *l, *r;
} Node;

static Node *N(int v){ Node*n=calloc(1,sizeof*n); n->is_num=1; n->value=v; return n; }
static Node *B(char o,Node*a,Node*b){ Node*n=calloc(1,sizeof*n); n->op=o; n->l=a; n->r=b; return n; }

static int eval(Node *n){
  if (n->is_num) return n->value;
  int l = eval(n->l), r = eval(n->r);
  switch (n->op){
    case '+': return l + r;
    case '-': return l - r;
    case '*': return l * r;
    case '/': return l / r;
  }
  return 0;
}

int main(void){
  Node *ast = B('*', B('+', N(2), N(3)), N(4));
  printf("%d\n", eval(ast));
  return 0;
}

ความลึกของสแตก

ตัวดำเนินการที่ซ้อนกันแต่ละตัวจะเพิ่มเฟรมในสแตกการเรียกของ C นิพจน์ที่ซ้อนกันลึกมาก เช่น มีวงเล็บหนึ่งพันคู่ อาจทำให้สแตกเต็มได้

นิพจน์จริงส่วนใหญ่ไม่ซับซ้อนถึงระดับนั้น แต่ตัวแปลผลที่แข็งแกร่งอาจเปลี่ยนไปใช้สแตกที่จัดการเองเพื่อความปลอดภัย

การพับค่าคงที่

เนื่องจากการประเมินผลและการแยกวิเคราะห์ใช้ต้นไม้เดียวกัน คุณจึงสามารถปรับให้เหมาะสมได้ หากโหนดย่อยทั้งสองของการดำเนินการแบบไบนารีเป็นตัวเลข คุณอาจคำนวณผลลัพธ์เพียงครั้งเดียว แล้วแทนที่โหนดนั้นด้วยใบไม้

การพับค่าคงที่ นี้เป็นการปรับปรุงตัวแปลผลแบบคลาสสิก

/* fold: collapse a binop of two literals into one literal */
Node *fold(Node *n) {
  if (n->kind == N_BINOP) {
    n->bin.left  = fold(n->bin.left);
    n->bin.right = fold(n->bin.right);
    if (n->bin.left->kind == N_NUM &&
        n->bin.right->kind == N_NUM)
      return num(eval(n));
  }
  return n;
}

การคืนหน่วยความจำของต้นไม้

ต้องคืนหน่วยความจำของโหนดที่จัดสรรบนฮีป การคืนหน่วยความจำแบบหลังไปก่อนจะเยี่ยมชมโหนดย่อยก่อนโหนดแม่ ซึ่งสอดคล้องกับการประเมินผล

หากลืมทำเช่นนี้ จะเกิดหน่วยความจำรั่วกับทุกนิพจน์ที่ตัวแปลผลทำงาน

void free_tree(Node *n) {
  if (n->kind == N_BINOP) {
    free_tree(n->bin.left);
    free_tree(n->bin.right);
  }
  free(n);
}

เครื่องหมายลบเอกภาค

จำเป็นต้องจัดการการปฏิเสธค่า เช่น -5 ทางเลือกหนึ่งคือใช้โหนดเอกภาค อีกทางเลือกคือแปลง -x เป็น 0 - x ขณะทำการแยกวิเคราะห์

ไม่ว่าจะใช้วิธีใด การประเมินผลก็ยังคงเป็นการเดินต้นไม้แบบเรียกซ้ำที่เรียบง่าย

/* desugar approach: parse_factor returns binop('-', num(0), operand) */
if (cur().kind == TOK_MINUS) {
  bump();
  return binop('-', num(0), parse_factor());
}

เหตุใดจึงเดินผ่านต้นไม้

ตัวแปลผลที่เดินผ่านต้นไม้นั้นเขียนและแก้ไขข้อผิดพลาดได้ง่าย แต่ต้องแลกกับความเร็ว ภาษาต่าง ๆ เช่น Ruby รุ่นแรกใช้รูปแบบนี้ก่อนเปลี่ยนไปใช้เครื่องเสมือนแบบไบต์โค้ด

ถัดไปเราจะเพิ่มตัวแปร เพื่อให้ตัวแปลผลจดจำค่าได้

ตรวจสอบความเข้าใจ

ลองวิเคราะห์ลำดับที่ฟังก์ชันประเมินผลเยี่ยมชมโหนดต่าง ๆ

สรุปทบทวน

คุณได้สร้างตัวประเมินผลแบบเรียกซ้ำ ซึ่งประกอบด้วยกรณีพื้นฐานสำหรับใบไม้ การเรียกซ้ำสำหรับการดำเนินการแบบไบนารี การป้องกันการหารด้วยศูนย์ รวมถึงการคืนหน่วยความจำของต้นไม้และการพับค่าคงที่

ตอนนี้ตัวแปลผลสามารถคำนวณ AST ทางคณิตศาสตร์ใด ๆ ได้แล้ว ขั้นต่อไปคือการเพิ่มตัวแปร

คำถามที่พบบ่อย

บทเรียน “ประเมินค่าต้นไม้” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “ประเมินค่าต้นไม้” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส C Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส C Academy มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “ประเมินค่าต้นไม้”

คำนวณผลลัพธ์ คุณปฏิบัติ C Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน C Academy หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน C Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน

บทเรียน “ประเมินค่าต้นไม้” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน C Academy นี้ได้ไหม

ได้ บทเรียน C Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

← กลับไปที่ C Academy