트리 평가하기
결과를 계산해 보세요.
트리 평가하기은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
AST 순회하기
평가는 후위 순회입니다. 먼저 자식들을 계산한 다음 노드의 연산자로 결합합니다. 숫자 리프는 자신의 값을 그대로 반환합니다.
이 트리 순회 인터프리터는 인터프리터가 가질 수 있는 가장 단순한 백엔드입니다.
eval 시그니처
평가 함수는 노드 포인터를 받아 정수를 반환합니다. 트리가 재귀적이므로 함수 역시 재귀적입니다.
부동 소수점 언어라면 대신 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;
}0으로 나누기 방지하기
정수를 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와 같은 언어는 바이트코드 가상 머신으로 이동하기 전에 이 모델을 사용했습니다.
다음으로 변수를 추가하여 인터프리터가 값을 기억하도록 하겠습니다.
빠른 확인
eval이 노드를 방문하는 순서를 생각해 보세요.
복습
재귀 평가기를 구현했습니다. 리프 기본 사례, 이항 연산 재귀, 0으로 나누기 방지, 트리 해제와 상수 접기를 포함합니다.
이제 인터프리터는 모든 산술 AST를 계산할 수 있습니다. 다음은 변수를 추가하는 일입니다.
자주 묻는 질문
“트리 평가하기” 강의는 무료인가요?
네 — “트리 평가하기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“트리 평가하기”에서 뭘 배우나요?
결과를 계산해 보세요. 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
C Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“트리 평가하기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.