IT회사원 신동갓

BOJ 1918 후위표기식

https://www.acmicpc.net/problem/1918

구조체로 스택을 만들고 다시 해보았습니다.(.cpp에서 돌려야합니다.)

설명은 이전의 글을 참조해주세요.

  #include <stdio.h>
  #include <string.h>
  #include <stdlib.h>
  #define MAX_SIZE 10000
  ​
  typedef struct stack {
      char s[MAX_SIZE];
      int size;
  ​
      stack() {
          size = 0;
      }
  ​
      int empty() {
          if (size) return 0;
          else return 1;
      }
  ​
      void push(char c) {
          s[size] = c;
          size++;
      }
  ​
      void pop() {
          if (!empty()) {
              size--;
          }
      }
  ​
      char top() {
          return s[size - 1];
      }
  }stack;
  ​
  ​
  char* getPostOrder(char* str) {
      int len = strlen(str);
      char* ret = (char*)malloc(sizeof(char) * (len + 1));
      int retIdx = 0;
          
      stack s;
  ​
      for (int i = 0; i < len; i++) {
          if (str[i] == '+' || str[i] == '-') {
              while (!s.empty() && s.top() != '(') {
                  ret[retIdx++] = s.top();
                  s.pop();
              }
              s.push(str[i]);
          }
          else if (str[i] == '*' || str[i] == '/') {
              while (!s.empty() && (s.top() == '*' || s.top() == '/')) {
                  ret[retIdx++] = s.top();
                  s.pop();
              }
              s.push(str[i]);
          }
          else if (str[i] == '(') {
              s.push(str[i]);
          }
          else if (str[i] == ')') {
              while (s.top() != '(') {
                  ret[retIdx++] = s.top();
                  s.pop();
              }
              s.pop();
          }
          else if (str[i] >= 'A' && str[i] <= 'Z') {
              ret[retIdx++] = str[i];
          }
      }
  ​
      while (!s.empty()) {
          ret[retIdx++] = s.top();
          s.pop();
      }
  ​
      ret[retIdx] = '\0';
  ​
      return ret;
  }
  ​
  int main() {
      char str[MAX_SIZE];
      scanf("%s", str);
  ​
      char *ret = getPostOrder(str);
      printf("%s", ret);
  ​
      free(ret);
  ​
      return 0;
  }

https://www.acmicpc.net/problem/2263

헉헉..

엄청 어렵네요!!..

pre, in, post 각각의 순회는 이해했지만,

완벽히 이해한 것은 아니였나봅니다.

이 문제는

in과 post를 이용하여 pre를 유추하는 문제입니다.

post와 in의 특징을 제대로 이해하고 있다면

O(N)의 시간으로 해결할 수 있습니다.

우선 post에 특징에 대해서 말씀드리겠습니다.

post는 Left - Right - Root 순으로 순회를 합니다.

그렇다면 우리가 받는 post input에서 가장 끝이 트리의 root라는 것을 알 수 있습니다.

예제를 예로 들면 1 3 2 로 들어오니 2가 root라는 것을 알 수 있죠.

두번째로 in의 특징입니다.

in은 Left - Root - Right 순으로 순회를 합니다.

여기서 중요한 점!은 바로 in의 input을 그대로 받는 것이 아닌 그의 위치를 저장하는 것입니다.

예제를 예로 들면

1 2 3 이라는 input이 들어오니, pos[1] = 0, pos[2] = 1, pos[3] = 2

이런 식으로 위치를 저장합니다.

그 이유는

in을 사용해서 우리는 left, right 서브트리와 root로 구분을 지을 수 있기 때문입니다.

post를 이용하여 root를 찾았고, root가 무엇인지 안다면 in에서 그 root를 기준으로 left와 right 서브트리로 나눌 수 있습니다.

이러한 과정을 분할하면서 계속 반복한다면 원래의 트리 모양을 유추할 수 있겠지요.

pre는 Root - Left - Right 이므로 위의 특징들을 이용하여 root를 찾아낸 후 출력하고 in의 root를 기준으로

left서브트리의 노드 수와 right 서브트리의 노드 수를 체크하여 post트리에 적용한 후 그 노드 수를 기준으로 나눠주면 됩니다.

코드입니다.

pos배열을 선언할 때 배열의 개수가 MAX_SIZE + 1인 이유는 input이 1~N까지 들어오기 때문입니다.(이것 떄문에 엄청 틀렸습니다.)