---
# System prepended metadata

title: 13845 - Syntax forest
tags: [binary tree]

---

# 13845 - Syntax forest
>author: Utin
###### tags: `binary tree`
---

## Brief
See the code below

## Solution 0

```c=
#include <stdio.h>
#include <stdlib.h>

#define NUMSYM 9

typedef enum _id {
    X, A, B, C, D, PLUS, TIMES, MINUS, CALL
} ID;

typedef struct _node {
    ID id;
    struct _node* left, * right;
} Node;

Node* func[26];
int data[5];
char sym[10] = "XABCD+*-@";

Node* make_node(char c);
Node* create_tree();
long long count(Node* func_root, long long x);
long long mod(long long num);

int main() {
    int n, m;
    char func_name;
    scanf("%d %d", &n, &m);
    while (n--) {
        scanf(" %c", &func_name);
        func[func_name - 'a'] = create_tree();
    }
    while (m--) {
        scanf(" %c", &func_name);
        for (int i = 0; i < 5; i++) scanf("%d", &data[i]);
        printf("%lld\n", count(func[func_name - 'a'], data[X]));
    }
}

Node* make_node(char c) {
    Node* new_node = (Node*) malloc(sizeof(Node));
    int flag = 0;
    for (int i = 0; i < NUMSYM; i++) {
        if (c == sym[i]) {
            new_node->id = i;
            flag = 1;
            break;
        }
    }
    if (!flag) new_node->id = c - 'a' + NUMSYM;
    new_node->left = new_node->right = NULL;
    return new_node;
}

Node* create_tree() {
    char c;
    scanf(" %c", &c);
    Node* new_node = make_node(c);
    if (new_node->id > D && new_node->id < NUMSYM) {
        new_node->left = create_tree();
        new_node->right = create_tree();
    }
    return new_node;
}

long long count(Node* func_root, long long x) {
    if (func_root->id == PLUS)
        return mod(count(func_root->left, x) + count(func_root->right, x));
        
    if (func_root->id == TIMES)
        return mod(count(func_root->left, x) * count(func_root->right, x));
    
    if (func_root->id == MINUS)
        return mod(count(func_root->left, x) - count(func_root->right, x));

    if (func_root->id == CALL)
        return mod(count(func[func_root->left->id - NUMSYM], count(func_root->right, x)));


    if (func_root->id == X) return mod(x);
    else return mod(data[func_root->id]);
}

long long mod(long long num) {
    num %= 998244353;
    if (num < 0) num += 998244353;
    return num;
}

// Utin
```

## Reference