[BOJ] 1918 - 후위 표기식

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

BOJ - 후위 표기식

문제 유형: 스택, 문자열 처리, 트리

문제 난이도: Gold II

시간 제한: 2초

메모리 제한: 128MB

 

문제

수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

 

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

 

 

입력

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다. 

 

출력

첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

 

풀이

두 가지 풀이가 있다.

공통점은, 연산자의 우선순위이다.

연산자의 우선순위 번호가 더 높은 연산자가 더 먼저 계산되도록 해야 한다.

또한, 괄호는 하나의 서브수식이므로, 그 역시 고려해야 한다.

 

우선, 스택을 이용한 풀이가 있다.

순차적으로 문자열을 읽으며, 다음을 수행한다:

피연산자이면 새로운 수식 문자열에 그대로 추가한다.

여는 괄호라면, 스택에 넣는다.

닫는 괄호라면, 스택의 여는 괄호까지 연산자들을 꺼내서 뒤에 붙인다.

이외의 연산자라면, 스택의 톱 연산자가 현재 읽고있는 연산자의 우선순위보다 크거나 같은동안 계속 빼서 수식 문자열의 뒤에 붙인다.

더 우선순위가 높거나 앞에 와서 같은 우선순위이더라도 먼저 계산되어야 함을 의미한다.

그 뒤, 스택의 톱에 자신을 추가한다.

최종적으로 스택에 남은 연산자들을 모두 꺼내서 뒤에 붙인다.

 

트리를 이용한 풀이는, 우선 파싱을 해줘야 한다.

부분수식을 순차적으로 한 번 읽으면서 분리 기점이 되는 연산자를 골라야 한다. 최초의 부분수식은 전체인 닫힌구간 [0, n-1]이 되겠다.

연산자 우선순위가 낮은 최대한 오른쪽의 연산자 인덱스를 구한다. 그 인덱스의 연산자가 서브트리의 루트가 된다.

그 연산자를 기점으로 왼쪽, 오른쪽을 나눠서 또 부분수식을 파싱한다. 각각 루트의 왼쪽 자식, 오른쪽 자식이다.

주의할 점은, 기점은 괄호에 종속되면 안된다는 점이다. 그에 유의해야 한다.

부분수식이 괄호로 감싸져 있으면, 잘못 볼수가 있다. 그에 유의해서, 부분수식이 괄호로 감싸져 있는 경우도 고려해야 한다.

 

최종적으로 파싱된 이진트리를 후위순회한 결과가 후위표기식이 된다.

 

코드

C++

스택을 이용한 풀이

#include <bits/stdc++.h>

using namespace std;

int getPrecedence(char op) {
  if (op == '+' || op == '-')
    return 1;
  if (op == '*' || op == '/')
    return 2;
  return 0;
}

string toPostfix(const string &exp) {
  stack<char> stk;
  string newExp = "";

  for (char ch : exp) {
    if (isalpha(ch)) {
      newExp += ch;
    } else if (ch == '(') {
      stk.push(ch);
    } else if (ch == ')') {
      while (stk.top() != '(') {
        newExp += stk.top();
        stk.pop();
      }
      stk.pop();
    } else {
      while (!stk.empty() && getPrecedence(stk.top()) >= getPrecedence(ch)) {
        newExp += stk.top();
        stk.pop();
      }
      stk.push(ch);
    }
  }

  while (!stk.empty()) {
    newExp += stk.top();
    stk.pop();
  }

  return newExp;
}

int main(int argc, char *argv[]) {
  string exp;
  cin >> exp;

  string newExp = toPostfix(exp);
  cout << newExp << "\n";
  return 0;
}

 

 

트리를 이용한 풀이

#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
  char key;
  TreeNode *left;
  TreeNode *right;
  TreeNode(char ch) {
    this->key = ch;
    this->left = NULL;
    this->right = NULL;
  }
};

int getPrecedence(char op) {
  if (op == '+' || op == '-')
    return 1;
  if (op == '*' || op == '/')
    return 2;
  return 0;
}

TreeNode *parseExp(const string &exp, int l, int r) {
  if (l == r) {
    return new TreeNode(exp[l]);
  }

  int minPrecedence = INT_MAX;
  int operatorIndex = -1;
  int balance = 0;

  for (int i = l; i <= r; ++i) {
    if (exp[i] == '(') {
      balance++;
    } else if (exp[i] == ')') {
      balance--;
    } else if (balance == 0) {
      int precedence = getPrecedence(exp[i]);
      if (precedence > 0 && precedence <= minPrecedence) {
        minPrecedence = precedence;
        operatorIndex = i;
      }
    }
  }

  if (operatorIndex == -1) {
    if (exp[l] == '(' && exp[r] == ')') {
      return parseExp(exp, l + 1, r - 1);
    }
    return nullptr;
  }

  auto root = new TreeNode(exp[operatorIndex]);
  root->left = parseExp(exp, l, operatorIndex - 1);
  root->right = parseExp(exp, operatorIndex + 1, r);

  return root;
}

string postorder(TreeNode *root) {
  if (!root)
    return "";
  string res = "";
  res += postorder(root->left);
  res += postorder(root->right);
  res += root->key;

  return res;
}

int main() {
  string exp;
  cin >> exp;

  int n = exp.size();

  auto root = parseExp(exp, 0, n - 1);

  string newExp = postorder(root);

  cout << newExp << "\n";
  return 0;
}