Blog

// ast.hpp — 노드 계층(Element)과 방문자 인터페이스
#pragma once
#include <memory>

struct Num; struct Add; struct Mul;

struct Visitor {
	virtual ~Visitor() = default;
	virtual void visit(const Num &) = 0;
	virtual void visit(const Add &) = 0;
	virtual void visit(const Mul &) = 0;
#ifdef WITH_NEG
	virtual void visit(const struct Neg &) = 0;     // 새 노드 종류를 추가하면
#endif
};

struct Node {
	virtual ~Node() = default;
	virtual void accept(Visitor &v) const = 0;     // 첫 번째 디스패치: 노드 타입
};

struct Num : Node {
	double value;
	explicit Num(double v) : value(v) {}
	void accept(Visitor &v) const override { v.visit(*this); }   // 두 번째: 방문자 타입
};
struct Add : Node {
	std::unique_ptr<Node> l, r;
	Add(std::unique_ptr<Node> a, std::unique_ptr<Node> b) : l(std::move(a)), r(std::move(b)) {}
	void accept(Visitor &v) const override { v.visit(*this); }
};
struct Mul : Node {
	std::unique_ptr<Node> l, r;
	Mul(std::unique_ptr<Node> a, std::unique_ptr<Node> b) : l(std::move(a)), r(std::move(b)) {}
	void accept(Visitor &v) const override { v.visit(*this); }
};

// visitors.cpp — 노드 클래스를 건드리지 않고 연산(방문자)을 세 개 추가한다
#include <algorithm>
#include <iostream>
#include <string>
#include "ast.hpp"

struct Evaluator : Visitor {
	double result = 0;
	double eval(const Node &n) { n.accept(*this); return result; }
	void visit(const Num &n) override { result = n.value; }
	void visit(const Add &n) override { result = eval(*n.l) + eval(*n.r); }
	void visit(const Mul &n) override { result = eval(*n.l) * eval(*n.r); }
};

struct Printer : Visitor {
	std::string out;
	void visit(const Num &n) override { out += std::to_string(int(n.value)); }
	void visit(const Add &n) override { out += "("; n.l->accept(*this); out += " + "; n.r->accept(*this); out += ")"; }
	void visit(const Mul &n) override { n.l->accept(*this); out += " * "; n.r->accept(*this); }
};

struct Depth : Visitor {
	int d = 0, best = 0;
	void enter(const Node &a, const Node &b) { ++d; best = std::max(best, d); a.accept(*this); b.accept(*this); --d; }
	void visit(const Num &) override { best = std::max(best, d); }
	void visit(const Add &n) override { enter(*n.l, *n.r); }
	void visit(const Mul &n) override { enter(*n.l, *n.r); }
};

int main()
{
	// (2 + 3) * (4 + 1)
	auto expr = std::make_unique<Mul>(
		std::make_unique<Add>(std::make_unique<Num>(2), std::make_unique<Num>(3)),
		std::make_unique<Add>(std::make_unique<Num>(4), std::make_unique<Num>(1)));

	Printer p; expr->accept(p);
	Evaluator e;
	Depth d; expr->accept(d);
	std::cout << p.out << " = " << e.eval(*expr) << "  (depth " << d.best << ")\n";
}

// variant_ast.cpp — 닫힌 노드 집합이라면 std::variant + std::visit가 accept/visit 보일러플레이트를 대신한다
#include <iostream>
#include <memory>
#include <string>
#include <variant>

struct Num; struct Add; struct Mul; struct Neg;
using Expr = std::variant<Num, Add, Mul, Neg>;
using P = std::unique_ptr<Expr>;

struct Num { double v; };
struct Add { P l, r; };
struct Mul { P l, r; };
struct Neg { P e; };                                   // 새 노드: accept()를 쓸 필요 없다

template <class... F> struct overloaded : F... { using F::operator()...; };

double eval(const Expr &e)
{
	return std::visit(overloaded{
		[](const Num &n) { return n.v; },
		[](const Add &n) { return eval(*n.l) + eval(*n.r); },
		[](const Mul &n) { return eval(*n.l) * eval(*n.r); },
		[](const Neg &n) { return -eval(*n.e); },
	}, e);
}

std::string show(const Expr &e)
{
	return std::visit(overloaded{
		[](const Num &n) { return std::to_string(int(n.v)); },
		[](const Add &n) { return "(" + show(*n.l) + " + " + show(*n.r) + ")"; },
		[](const Mul &n) { return show(*n.l) + " * " + show(*n.r); },
		[](const Neg &n) { return "-" + show(*n.e); },
	}, e);
}

template <class T, class... A> P mk(A &&...a) { return std::make_unique<Expr>(T{std::forward<A>(a)...}); }

int main()
{
	// -(2 + 3) * 4
	P expr = mk<Mul>(mk<Neg>(mk<Add>(mk<Num>(2.0), mk<Num>(3.0))), mk<Num>(4.0));
	std::cout << show(*expr) << " = " << eval(*expr) << '\n';
}

/* visit.c — C 방문자: 노드는 태그를 갖고, 연산마다 "노드 종류 → 처리 함수" 표를 만든다 */
#include <stdio.h>

enum kind { NUM, ADD, MUL, NKIND };

struct node {
	enum kind kind;
	double value;                 /* NUM */
	const struct node *l, *r;     /* ADD, MUL */
};

struct visitor {                  /* 연산 하나 = 노드 종류별 함수 표 */
	double (*on[NKIND])(const struct visitor *v, const struct node *n);
};

static double accept(const struct visitor *v, const struct node *n) { return v->on[n->kind](v, n); }

/* 평가 연산 */
static double ev_num(const struct visitor *v, const struct node *n) { (void)v; return n->value; }
static double ev_add(const struct visitor *v, const struct node *n) { return accept(v, n->l) + accept(v, n->r); }
static double ev_mul(const struct visitor *v, const struct node *n) { return accept(v, n->l) * accept(v, n->r); }
static const struct visitor evaluator = { { [NUM] = ev_num, [ADD] = ev_add, [MUL] = ev_mul } };

/* 노드 수 세기 연산: 노드 정의는 그대로 두고 추가 */
static double cnt_leaf(const struct visitor *v, const struct node *n) { (void)v; (void)n; return 1; }
static double cnt_bin(const struct visitor *v, const struct node *n) { return 1 + accept(v, n->l) + accept(v, n->r); }
static const struct visitor counter = { { [NUM] = cnt_leaf, [ADD] = cnt_bin, [MUL] = cnt_bin } };

int main(void)
{
	/* (2 + 3) * (4 + 1) */
	struct node n2 = { NUM, 2, 0, 0 }, n3 = { NUM, 3, 0, 0 }, n4 = { NUM, 4, 0, 0 }, n1 = { NUM, 1, 0, 0 };
	struct node a1 = { ADD, 0, &n2, &n3 }, a2 = { ADD, 0, &n4, &n1 };
	struct node m = { MUL, 0, &a1, &a2 };

	printf("value = %g, nodes = %g\n", accept(&evaluator, &m), accept(&counter, &m));
	return 0;
}