21W26-Tree

[murry2018]

SWEA 1231. 중위 순회

#include <cstdio>
#include <cstring>
#include <cctype>

template <typename T>
struct storage {
  T item;
};

template <typename T>
struct optional {
  storage<T> *store = nullptr;
  optional() {
    store = nullptr;
  }
  optional(T item) {
    if (store != nullptr)
      delete store;
    store = new storage<T>;
    store->item = item;
  }
  T value() {
    return store->item;
  }
  bool has_value() {
    return store != nullptr;
  }
  T operator*() {
    return store->item;
  }
};

using namespace std;

namespace io {
  char* skip_space(char *s) {
    if (s == nullptr)
      return s;
    while (isspace(*s))
      s++;
    return s;
  }

  optional<int> read_int(char *s, char **next) {
    if (s == nullptr) {
      if (next)
        *next = nullptr;
      return {};
    }
    s = skip_space(s);
    int res = 0;
    if (!isdigit(s[0])) {
      return {};
    }
    char *p = s;
    res = *p - '0';
    while (isdigit(*(++p))) {
      res = res*10 + *p - '0';
    }
    if (next)
      *next = p;
    return {res};
  }

  optional<char> read_alpha(char *s, char **next) {
    if (s == nullptr) {
      if (next)
        *next = nullptr;
      return {};
    }
    s = skip_space(s);
    if (!isalpha(*s) && *s != '_') {
      return {};
    } else {
      if (next)
        *next = s+1;
      return {*s};
    }
  }
}

struct Node {
  char value;
  optional<int> left, right;
  Node() {
  }
  Node(char value, optional<int> left, optional<int> right)
    :value(value), left(left), right(right) {
  }
  static optional<Node> read(char *s) {
    optional<char> value;
    optional<int> left, right;
    value = io::read_alpha(s, &s);
    if (!value.has_value()) {
      return {};
    }
    left = io::read_int(s, &s);
    right = io::read_int(s, &s);
    return optional<Node>(Node(*value, left, right));
  }
};

void speak_tree(Node tree[], int curr) {
  if (tree[curr].left.has_value()) {
    speak_tree(tree, tree[curr].left.value());
  }
  putchar(tree[curr].value);
  if (tree[curr].right.has_value()) {
    speak_tree(tree, tree[curr].right.value());
  }
}

int main() {
  int N;
  Node tree[101];
  char buff[100];
  for (int T = 1; T <= 10; T++) {
    memset(tree, 0, sizeof tree);
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
      int idx;
      scanf("%d", &idx);
      fgets(buff, 100, stdin);
      optional<Node> node = Node::read(buff);
      if (node.has_value()) {
        tree[idx] = *node;
      } else {
        fprintf(stderr, "FATAL! node format error(%s)", buff);
      }
    }
    printf("#%d ", T);
    speak_tree(tree, 1);
    putchar('\n');
  }
}

[murry2018]

SWEA 1233. 사칙연산 유효성 검사

풀고 나서 알게 된 사실이지만 iterator을 지역 변수 이상의 스코프에 저장해 두는 것은 권장할 만한 방식이 아니라고 합니다. node_validator::fields[] 배열이 그런 경우인데, 이 코드는 왜 잘 되는지 저도 잘 모르겠습니다... SWEA에서 제공하는 테스트케이스만 아슬아슬하게 통과가 되는걸지도

#include <cstdio>
#include <cctype>
#include <functional>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

// using Predicate = function<int(int)>;

typedef int (*Predicate)(int);

// static Predicate isnotspace = complement(isspace);
int isnotspace(int c) {
    return !isspace(c);
}

struct node_validator {
    const string node_info;
    string::const_iterator fields[4];
    int nfields = 0;
    node_validator() {}
    node_validator(string _node_info)
        : node_info(_node_info) {
    }
    void split() {
        string::const_iterator iter, next;
        iter = next = node_info.begin();
        auto end = node_info.end();
        while (next != end) {
            iter = skip(isspace, next);
            if (iter == end)
                break;
            fields[nfields++] = iter;
            next = skip(isnotspace, iter);
        }
    }
    string::const_iterator skip(Predicate pred, string::const_iterator s) {
        auto end = node_info.end();
        while (s != end && pred(*s))
            ++s;
        return s;
    }

    bool is_operator() {
        static const char ops[] = {'+', '-', '*', '/'};
        static const int nop = 4;
        const char *op_ed = ops + nop;
        return find(ops, op_ed, fields[1][0]) != op_ed;
    }
    bool is_valid() {
        split();
        return is_operator()?
            nfields == 4:
            nfields == 2;
    }
};

bool every_valid(vector<node_validator>& validators) {
    for (node_validator& validator: validators) {
        if (!validator.is_valid()) {
            return false;
        }
    }
    return true;
}

int main() {
    char buf[1024];
    for (int t = 1; t <= 10; t++) {
        int vertices = 0;
        scanf("%d", &vertices);
        while(getchar()!='\n');

        vector<node_validator> validators;
        for (int i = 0; i < vertices; i++) {
            fgets(buf, 1024, stdin);
            validators.emplace_back(buf);
        }

        bool valid = every_valid(validators);
        printf("#%d %d\n", t, valid);
    }
}

[murry2018]

SWEA 1232. 사칙연산

#include <cstdio>
#include <algorithm>
#include <cctype>
#include <string>
#include <vector>

namespace string {
  using iter_t = std::string::iterator;
  bool isspace(char c) {
    return static_cast<bool>(std::isspace(c));
  }
  bool isnotspace(char c) {
    return !isspace(c);
  }
  template <typename _CharPredicate>
  iter_t skip(iter_t begin, iter_t end, _CharPredicate predicate) {
    while (begin != end && predicate(*begin))
      ++begin;
    return begin;
  }

  int parse_int(std::string s) {
    int res = 0;
    for (char c : s) {
      res *= 10;
      res += c-'0';
    }
    return res;
  }

  std::vector<std::string> split(std::string s) {
    std::vector<std::string> result;
    iter_t end = s.end();
    iter_t begin = skip(s.begin(), s.end(), isspace);
    iter_t next = begin;
    while (next != end) {
      begin = skip(next, end, isspace);
      next = skip(begin, end, isnotspace);
      if (begin != end)
        result.emplace_back(begin, next);

    }
    return result;
  }
}

struct oper {
  virtual double
  call(double lhs, double rhs) const = 0;
};

struct add_oper : oper {
  double call(double lhs, double rhs) const {
    return lhs + rhs;
  }
};

struct sub_oper : oper {
  double call(double lhs, double rhs) const {
    return lhs - rhs;
  }
};

struct mul_oper : oper {
  double call(double lhs, double rhs) const {
    return lhs * rhs;
  }
};

struct div_oper : oper {
  // does not consider divide-by-zero
  double call(double lhs, double rhs) const {
    return lhs / rhs;
  }
};

oper *oper_from(char op_char) {
  static oper *ops[] = {
    new add_oper(),new sub_oper(),
    new mul_oper(),
    new div_oper()
  };
  static char op_chars[] = "+-*/";
  static char *op_ed = op_chars + 4;
  char *pop = std::find(op_chars, op_ed, op_char);
  if (pop == op_ed) {
    return nullptr;
  } else {
    return ops[pop-op_chars];
  }
}

struct node {
  virtual double reduce() = 0;
  virtual ~node() {}
};

struct number_node : node {
  double value;
  number_node(double value)
    : value(value) { }
  double reduce() {
    return value;
  }
};

struct operator_node : node {
  node *lhs, *rhs;
  const oper *op;
  bool lazy = false;
  int lhn, rhn;
  node **node_tree;
  operator_node(char op_char) {
    op = oper_from(op_char);
  }
  operator_node(char op_char, node *lhs, node *rhs): lhs(lhs), rhs(rhs) {
    op = oper_from(op_char);
  }
  operator_node(oper* op, node **node_tree, int lhn, int rhn)
    : op(op), node_tree(node_tree), lazy(true), lhn(lhn), rhn(rhn) {
  }
  double reduce() {
    if (lazy) {
      rhs = node_tree[rhn];
      lhs = node_tree[lhn];
    }
    double left = lhs->reduce();
    double right = rhs->reduce();
    return op->call(left, right);
  }
};

int nmemb;
node *tree[1000] = {0};

node *read_node(std::string node_info) {
  auto fields = string::split(node_info);
  int node_id = string::parse_int(fields[0]) - 1;
  oper* op = oper_from(fields[1][0]);
  if (op == nullptr) {
    int value = string::parse_int(fields[1]);
    tree[node_id] = new number_node(value);
  } else {
    int lhn = string::parse_int(fields[2]) - 1;
    int rhn = string::parse_int(fields[3]) - 1;
    tree[node_id] = new operator_node(op, tree, lhn, rhn);
  }
  return tree[node_id];
}

void destroy_tree() {
  for (int i = 0; i < nmemb; i++) {
    delete tree[i];
  }
}

char buff[1024];
int main() {
  for (int t = 1; t <= 10; t++) {
    std::scanf("%d", &nmemb);
    while(std::getchar() != '\n');
    for (int i = 0; i < nmemb; i++) {
      std::fgets(buff, 1024, stdin);
      read_node(buff);
    }
    int result = static_cast<int>(tree[0]->reduce());
    printf("#%d %d\n", t, result);
    destroy_tree();
  }
}

[moodmine]

SWEA 1231. 중위 순회

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

using namespace std;

#define MAX_NODE 100

char tree[MAX_NODE + 1]; // 1번부터 100번 까지의 트리 배열

void ClearBuffer()
{
    while (getchar() != '\n');
}

void ReadTreeinorder(int root)
{
    int left_child = root * 2;
    int right_child = root * 2 + 1;

    if (left_child <= MAX_NODE && tree[left_child] != NULL)
        ReadTreeinorder(left_child);

    printf("%c", tree[root]);

    if (right_child <= MAX_NODE && tree[right_child] != NULL)
        ReadTreeinorder(right_child);
}

int main(int argc, char** argv)
{
    int test_case;
    int T;

    //freopen("input.txt", "r", stdin);
    //cin >> T;
    T = 10;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        for (int i = 0; i <= MAX_NODE; i++)
        {
            tree[i] = NULL;
        }

        int Num_Node;
        scanf("%d", &Num_Node);

        int point;
        char data;
        for (int i = 0; i < Num_Node; i++)
        {
            ClearBuffer();
            scanf("%d %c", &point, &data);
            tree[point] = data;
            // 자식 노드의 위치를 활용해서 더 빨라지게 하는 방법은 없을까?
        }

        printf("#%d ", test_case);
        ReadTreeinorder(1);
        printf("\n");
    }
    return 0;
}

SWEA 1233. 사칙연산 유효성 검사

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

using namespace std;

#define MAX_NODE 200

char tree[MAX_NODE + 1]; // 1번부터 100번 까지의 트리 배열
int tree_result[MAX_NODE + 1]; // 계산 결과 저장

void ClearBuffer()
{
    while (getchar() != '\n');
}

void TreeOperator(int root, int* check)
{
    int left_child = root * 2;
    int right_child = root * 2 + 1;

    switch (tree[root])
    {
    case '+':
        tree_result[root] = (tree_result[left_child] - 48) + (tree_result[right_child] - 48);
        break;
    case '-':
        tree_result[root] = (tree_result[left_child] - 48) - (tree_result[right_child] - 48);
        break;
    case '*':
        tree_result[root] = (tree_result[left_child] - 48) * (tree_result[right_child] - 48);
        break;
    case '/':
        tree_result[root] = (tree_result[left_child] - 48) / (tree_result[right_child] - 48);
        break;
    default:
        *check = 0;
    }
}

void ReadTreeinorder(int root, int* check)
{
    int left_child = root * 2;
    int right_child = root * 2 + 1;

    if (left_child <= MAX_NODE && tree[left_child] != NULL)
        ReadTreeinorder(left_child, check);
    else
        return;

    if (right_child <= MAX_NODE && tree[right_child] != NULL)
        ReadTreeinorder(right_child, check);
    else
        return;

    if (tree_result[left_child] != NULL && tree_result[right_child] != NULL)
        TreeOperator(root, check);
    else
        check = 0;

}

int main(int argc, char** argv)
{
    int test_case;
    int T;

    //freopen("input.txt", "r", stdin);
    //cin >> T;
    T = 10;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        for (int i = 0; i <= MAX_NODE; i++)
        {
            tree[i] = NULL;
            tree_result[i] = NULL;
        }

        int Num_Node;
        scanf("%d", &Num_Node);

        int point;
        char data;
        for (int i = 0; i < Num_Node; i++)
        {
            ClearBuffer();
            scanf("%d %c", &point, &data);
            tree[point] = data;
            if (data >= 48)
                tree_result[point] = data - 48;
            // 자식 노드의 위치를 활용해서 더 빨라지게 하는 방법은 없을까?
        }

        int check = 1;
        ReadTreeinorder(1, &check);
        printf("#%d %d\n", test_case, check);
    }
    return 0;
}

SWEA 1232. 사칙연산

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

using namespace std;

typedef struct TreeNode
{
    char type = NULL; 
    // 이게 연산자인지 정수인지 구분하는 변수 0일 시 연산자 1일 시 정수
    int data_int = NULL;
    char data_op = NULL;
    int left = 0;
    int right = 0;
}TreeNode;

void ClearBuffer()
{
    while (getchar() != '\n');
}

void TreeOperator(TreeNode Tree[], int root)
{
    switch (Tree[root].data_op)
    {
    case '+':
        Tree[root].data_int = (Tree[Tree[root].left].data_int) + (Tree[Tree[root].right].data_int);
        break;
    case '-':
        Tree[root].data_int = (Tree[Tree[root].left].data_int) - (Tree[Tree[root].right].data_int);
        break;
    case '*':
        Tree[root].data_int = (Tree[Tree[root].left].data_int) * (Tree[Tree[root].right].data_int);
        break;
    case '/':
        Tree[root].data_int = (Tree[Tree[root].left].data_int) / (Tree[Tree[root].right].data_int);
        break;
    }
}

void ReadTreeinorder(TreeNode Tree[], int root)
{
    if (Tree[root].left != 0)
        ReadTreeinorder(Tree, Tree[root].left);
    else
        return;

    if (Tree[root].right != 0)
        ReadTreeinorder(Tree, Tree[root].right);
    else
        return;

    TreeOperator(Tree, root);

}

int main(int argc, char** argv)
{
    int test_case;
    int T;
    int test;

    //freopen("input.txt", "r", stdin);
    //cin >> T;
    T = 10;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        int Num_Node;
        scanf("%d", &Num_Node);
        TreeNode Tree[1001];

        int point;
        char data[10];
        for (int i = 1; i <= Num_Node; i++)
        {
            scanf("%d", &point);
            test = point;
            getchar();
            scanf("%s", &data);
            if (data[0] >= 48)
            {
                Tree[point].type = 1;
                Tree[point].data_int = atoi(data);
            }
            else
            {
                Tree[point].type = 0;
                Tree[point].data_op = data[0];
            }

            data[0] = getchar();
            if (data[0] != '\n')
            {
                scanf("%d", &Tree[point].left);

                data[0] = getchar();
                if (data[0] != '\n')
                    scanf("%d", &Tree[point].right);

            }
        }

        ReadTreeinorder(Tree, 1);
        printf("#%d %d\n", test_case, Tree[1].data_int);
    }
    return 0;
}

[happy-oh]

SWEA 1231 중위 순회

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<iostream>

using namespace std;
#define MAX_NODE_NUM 200
#define MAX_CHILD_NUM 2

typedef struct
{
    int parent;
    int child[MAX_CHILD_NUM];
    char data;
} TreeNode;
TreeNode tree[MAX_NODE_NUM];
int nodeNum;
int edgeNum;
int root;

void initTree(void)
{
    int i;
    int j;
    for (i = 0; i <= nodeNum; i++)
    {
        tree[i].parent = -1;
        for (j = 0; j < MAX_CHILD_NUM; j++)
        {
            tree[i].child[j] = -1;
        }
    }
}

void addChild(int parent, int child, char data)
{
    int i;
    for (i = 0; i < MAX_CHILD_NUM; i++)
    {
        if (tree[parent].child[i] == -1)
        {

            break;
        }
    }
    tree[parent].child[i] = child;
    tree[child].parent = parent;
    tree[parent].data = data;

}

int getRoot(void)
{
    int i;
    int j;
    for (i = 1; i <= nodeNum; i++)
    {
        if (tree[i].parent == -1)
        {
            return i;
        }
    }
    return -1;
}

void preOrder(int root)
{
    int i;
    int child;
    printf("%d ", root);

    for (i = 0; i < MAX_CHILD_NUM; i++)
    {
        child = tree[root].child[i];
        if (child != -1)
        {
            preOrder(child);
        }
    }
}
void midOrder(int root)
{
    int i;
    int child00, child11;
    //printf("%d ", root);
    child00 = tree[root].child[0];
    child11 = tree[root].child[1];
    if (child00 != -1)
    {
        midOrder(child00);
    }
    printf("%c", tree[root].data);
    if (child11 != -1)
    {
        midOrder(child11);
    }

}

int main(void)
{
    int test_case;
    int T;
    int node_num;
    int idx;

    freopen("input.txt", "r", stdin);
    T = 10;
    int parent, child1, child2;
    char data;

    for (test_case = 1; test_case <= T; ++test_case)
    {

        scanf("%d", &nodeNum);
        initTree();
        for (idx = 1; idx <= nodeNum; idx++)
        {
            scanf("%d %c ", &parent, &data);
            if (2 * parent <= nodeNum)
                scanf("%d", &child1);
            else
                child1 = -1;
            if (2 * parent + 1 <= nodeNum)
                scanf(" %d", &child2);
            else
                child2 = -1;
            addChild(parent, child1, data);
            addChild(parent, child2, data);
        }
        printf("#%d ", test_case);
        midOrder(1);
        printf("\n");

    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

1233 아리스메틱 유효성

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<iostream>

using namespace std;
#define MAX_NODE_NUM 200
#define MAX_CHILD_NUM 2

typedef struct
{
    int parent;
    int child[MAX_CHILD_NUM];
    char data;
} TreeNode;
TreeNode tree[MAX_NODE_NUM];
int nodeNum;
int edgeNum;
int root;

void initTree(void)
{
    int i;
    int j;
    for (i = 0; i <= nodeNum; i++)
    {
        tree[i].parent = -1;
        for (j = 0; j < MAX_CHILD_NUM; j++)
        {
            tree[i].child[j] = -1;
        }
    }
}

void addChild(int parent, int child, char data)
{
    int i;
    for (i = 0; i < MAX_CHILD_NUM; i++)
    {
        if (tree[parent].child[i] == -1)
        {

            break;
        }
    }
    tree[parent].child[i] = child;
    tree[child].parent = parent;
    tree[parent].data = data;

}

int getRoot(void)
{
    int i;
    int j;
    for (i = 1; i <= nodeNum; i++)
    {
        if (tree[i].parent == -1)
        {
            return i;
        }
    }
    return -1;
}

void preOrder(int root)
{
    int i;
    int child;
    printf("%d ", root);

    for (i = 0; i < MAX_CHILD_NUM; i++)
    {
        child = tree[root].child[i];
        if (child != -1)
        {
            preOrder(child);
        }
    }
}
void midOrder(int root)
{
    int i;
    int child00, child11;
    //printf("%d ", root);
    child00 = tree[root].child[0];
    child11 = tree[root].child[1];
    if (child00 != -1)
    {
        midOrder(child00);
    }
    printf("%c", tree[root].data);
    if (child11 != -1)
    {
        midOrder(child11);
    }

}

int main(void)
{
    int test_case;
    int T;
    int node_num;
    int idx;

    freopen("input.txt", "r", stdin);
    T = 10;
    int parent, child1, child2;
    char data;
    int flag;

    for (test_case = 1; test_case <= T; ++test_case)
    {
        flag = 1;
        scanf("%d", &nodeNum);
        initTree();
        for (idx = 1; idx <= nodeNum; idx++)
        {
            scanf("%d %c ", &parent, &data);
            if (2 * parent <= nodeNum) {
                scanf("%d", &child1);
                if (data >= 48)
                    flag = 0;
            }
            else {
                child1 = -1;
                if (data < 48)
                    flag = 0;
            }
            if (2 * parent + 1 <= nodeNum) {
                scanf(" %d", &child2);
                if (data >= 48)
                    flag = 0;
            }
            else
                child2 = -1;
            addChild(parent, child1, data);
            addChild(parent, child2, data);

        }
        printf("#%d %d\n", test_case, flag);

    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}