Untitled

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

typedef struct node {
    int data;
    struct node *left, *right;
} BTNode;

#define MAXLEN 3010

int valmax;
int values[MAXLEN];

// Print the syntax tree in preorder to debug
void printPrefix(BTNode* node) 
{  
    if (node == NULL) 
        return;
    printf("%d ", node->data);
    printPrefix(node->left);
    printPrefix(node->right);
}


// Calculate ternary expression
void calc(BTNode* node)
{

    if (values[node->data]) {
        if (node->left == NULL) {
            printf("%d\n", values[node->data]);
            return ;
        }
        return calc(node->left);
        
    }
    else {
        if (node->left == NULL) {
            printf("%d\n", values[node->data]);
            return ;
        }
        return calc(node->right);
        
    }
}


BTNode* makeNode(int val)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    valmax = val > valmax ? val : valmax;
    node->data = val;
    node->left = node->right = NULL;
    return node;
}

// Build the syntax tree by the grammar of ternary expression
BTNode* EXPR()
{
    char c;
    int now;
    c = getchar();
    BTNode* node;
    if (isdigit(c)) {
        ungetc(c, stdin);
        scanf("%d", &now);
        node = makeNode(now);
    }
    c = getchar();
    if (c == '?') {
        node->left = EXPR();
        node->right = EXPR();
    }
    return node;
}

int main()
{
    BTNode* root = EXPR();

    // printPrefix(root);
    // putchar('\n');

    int T;
    scanf("%d", &T);
    while (T--) {
        for (int i = 1; i <= valmax; i++) {
            scanf("%1d", &values[i]);
        }   
        calc(root);
    }

    return 0;
}