Tip - 후위 표기식 연산

후위 표기식

우리가 흔히 연산식을 읽기 쉽도록 나타낸 것을 중위 표기식이라 부르고

$$ 1+2-(3-5)\div 2 $$

처럼 쓰곤 한다.

하지만 이를 다음과 같이 연산의 대상이 되는 숫자들을 앞으로, 연산자들을 뒤로 보내 표현한 것을 후위 표기식이라 한다.

$$ 12+35-2\div - $$

괄호는 변환 과정에 처리되어 사라진다.

후위 표기식으로 표현했을 때 좋은 점은, 앞에서 읽는 것으로 연산을 그대로 해줄 수 있다는 것이다.

$$ \begin{aligned} &12+35-2\div -\\ &(3)35-2\div -\\ &(3)(-2)2\div-\\ &(3)\left(-1\right)-\\ &&=4 \end{aligned} $$

이는 인간이 계산하기엔 모르겠지만 컴퓨터가 앞에서 그저 읽으면서 결과값을 계산하는 코드를 짜기에 굉장히 최적화가 되어있는 구조이다.

후위 표기식 변환법

중위 표기식을 후위 표기식으로 변환하는 방법은 스택을 이용해 풀 수 있는 대표적인 문제 중 하나이다.

연산자의 우선순위

우선, 연산자마다 다른 우선순위를 매긴다. 곱하기와 나머지는 더하기와 빼기보다 먼저 수행되어야 하고, 괄호도 따로 처리해주어야 하기 때문이다.

$$ \begin{aligned} * \Rightarrow 3\\ \div \Rightarrow 3\\ + \Rightarrow 2\\ - \Rightarrow 2\\ ( \Rightarrow 1 \end{aligned} $$

$1,2,3$ 이 중요한건 아니다. 상대적인 크기를 나타냈을 뿐이다.

구현

동적 배열 두 개를 사용한다.

한 개는 후위 표기식으로 바뀌는 결과를 담고, 하나는 연산자들에 대한 스택이다.

우선, 중위 표기식의 문자들을 순회하며 연산자가 아닌 숫자라면 결과 배열에 push한다.

사칙 연산자라면 다음과 같이 한다.

1. 연산자 스택의 top 부터 보면서 현재 만난 연산자 이상의 우선순위를 가진 원소가 나오면 일 때 까지 계속해서 pop 한 다음에 결과 배열에 push 한다.
2. 현재 만난 연산자를 연산자 스택에 넣는다.
3. 중위 표기식 순회를 마친 후에, 연산자 스택에 남아있는 연산자들을 모두 결과 배열에 push 한다.

괄호 연산자라면 다음과 같이 한다.

1. ( 를 만났다면 스택에 넣는다.
2. ) 를 만났다면 ( 가 나오기 전까지 연산자 스택에 있는 연산자들을 모두 결과 배열에 push 하고 연산자 스택에서 ( 도 pop 한다.

예시

설명을 위해 그림을 그리고 예시 중위 표기식을 바꾸어 보도록 하겠다.

$$ a+b*(c-d\div e)+f $$

$a$ 는 숫자이므로 그냥 결과에 push 해준다.

$+$ 는 연산자이므로 스택에 넣는다.

$b$ 도 그냥 결과에 push 한다.

$*$ 는 $+$ 보다 우선순위가 크므로, $+$ 를 꺼내지 않고 스택에 쌓인다.

이제 괄호니까 그냥 스택에 넣는다.

$c$ 는 숫자니까 결과에 넣는다.

$-$ 는 $($ 보다 우선순위가 높으므로 $($ 를 빼지않고 $-$ 도 스택에 넣는다.

$e$ 가 나오는 부분까지 빨리 해보자.

이제 ) 가 나왔으므로 스택에서 ( 가 나올 때 까지 모두 결과에 추가해준 뒤에 ( 는 제거한다.

이제 $+$ 가 나왔으므로 스택에서 자신 이상의 우선순위를 가진 $*$ 와 $+$를 모두 빼준후 자신을 스택에 넣는다.

그 후에 $f$ 까지 결과에 넣어준다.

이제 중위 표기식을 모두 순회했으므로 스택에 있는것을 모두 빼서 그대로 결과에 붙여준다.

후위 표기식이 완성되었다.

$$ \begin{aligned} a+b*(c-d&\div e)+f\\ \Downarrow&\\ abcde\div -\,&*+f+ \end{aligned} $$

왜 이것이 후위 표기식을 만드는 방법일까?

이 과정이 동작하는 이유는 다음과 같다.

우선 연산자끼리의 우선 순위가 다른 경우를 본다.

• 후위 표기식에서는 우선순위가 높은 연산자가 앞에 와야한다.

$$ 1+5*4 $$

를 보면, 후위 표기식으로 바꾸면

$$ 154*+ $$

가 되야 하기 때문에, 자신 초과의 우선순위를 가진 연산자가 스택에 있다면 다 꺼내서 결과에 push 해줘야 옳다.

연산자끼리의 우선 순위가 같은 경우를 본다.

$1+5-4$ 를 보자.

후위 표기식은

$$ 15+4- $$

이다.

연산자끼리의 우선순위가 같으면 먼저 온 연산자가 먼저 연산되는게 맡기 때문에 연산자 스택에서 자신과 우선순위가 같더라도 빼서 결과에 push 해주는게 옳다.

괄호를 보자

다음과 같은 중위 표기식을 보자.

$$ 1+(5-4*7)-2 $$

괄호란건 내부의 값이 먼저 처리가 되어야 하기 때문에 대략 다음과 같이 뭉텅이로 생각해줄 수 있다.

$$ \begin{aligned} 1+X-2\\ \Downarrow \text{후위 표기식 변환}\\ 1X+2- \end{aligned} $$

괄호 내부엔 또 위에서 본대로 먼저 후위표기식 변환이 되어서 다음과 같이 나오게된다.

$$ \begin{aligned} 1X+2-\\ 1547*-+2- \end{aligned} $$

괄호가 중첩되어 있어도 귀납적(재귀적)으로 올바르게 처리가 될 것이므로 위와 같은 구현이 결국 후위 표기식을 만드는데 있어 논리적을 맞다는 것이 보여진다.

연습 문제

후위 표기식을 줬을 때 그거에 대한 연산을 하는것은 굉장히 쉽다.

BOJ 1935 - 후위 표기식2

하지만 중위 표기식을 후위 표기식으로 바꾸는 것은 위와 같은 과정을 구현해야 하기 때문에 어렵다.

BOJ 1918 - 후위 표기식

난이도가 무려 골드 2가 되었다.

이걸 사전지식 없이 스스로 스택을 써서 구현해야지! 하는 사람이 있다면 상당히 비범한 사람이다. 대개 후위 표기식을 만드는 것은 컴퓨터 전공 학생이라면 학부 자료구조 시간에 배우곤 한다.

템플릿

Python엔 eval 이 있는데 c++ 엔 왜 없는가 하면서 직접 만든 후위 표기식을 이용한 eval 구현체이다.

이제 여기에 bigint 같은 것을 끼얹으면 큰 수 연산도 손쉽게 할 수 있다.

template<class T>
struct _eval {
   string ops = "+-*/%()";
   bool is_op(char c) { return ops.find(c) != string::npos; }
   bool is_op(string c) { return sz(c) == 1 && is_op(c[0]); }
   T run_op(T a, T b, char op) {
      if (op == '+') return a + b;
      else if (op == '-') return a - b;
      else if (op == '*') return a * b;
      else if (op == '/') return a / b;
      else return a % b;
   }
   T run_op(T a, T b, string op) { return run_op(a, b, op[0]); }
   int op_priority(string op) {
      if (op == "*" || op == "/" || op == "%") return 3;
      else if (op == "+" || op == "-") return 2;
      else return 1;
   }
   T calc_infix(const string &s) { return calc_postfix(to_postfix(s)); }
   T calc_postfix(const vector<string> &s) {
      vector<T> t;
      for (auto &c: s) {
         if (is_op(c)) {
            T val = run_op(t[sz(t) - 2], t[sz(t) - 1], c[0]);
            t.pop_back(), t.pop_back(), t.push_back(val);
         } else {
            // Warning: long long conversion will cause crash on bigint usage
            t.push_back(stoll(c));
         }
      }
      return t[0];
   }
   vector<string> to_postfix(const vector<string> &s) {
      vector<string> ret, op;
      for (auto &c: s) {
         if (is_op(c)) {
            if (c == "(") op.push_back("(");
            else if (c == ")") {
               while (sz(op) && op.back() != "(") ret.pb(op.back()), op.pop_back();
               op.pop_back();
            } else {
               while (sz(op) && op_priority(op.back()) >= op_priority(c)) ret.pb(op.back()), op.pop_back();
               op.push_back(c);
            }
         } else {
            ret.pb(c);
         }
      }
      while (sz(op)) ret.pb(op.back()), op.pop_back();
      return ret;
   }
   vector<string> to_postfix(const string &s) { return to_postfix(parse(s)); }
   vector<string> parse(const string &s) {
      vector<string> ret;
      string tmp;
      for (int i = 0; i < sz(s); i++) {
         if (is_op(s[i])) ret.pb(string(1, s[i]));
         else if (i == sz(s) - 1 || is_op(s[i + 1])) ret.pb(tmp + s[i]), tmp = "";
         else tmp += s[i];
      }
      if (sz(ret) && ret[0] == "-") { // leading negative operator
         ret[1] = "-" + ret[1];
         ret.erase(ret.begin());
      }
      return ret;
   }
   string to_raw(const vector<string> &s) {
      string ret;
      for (auto &c: s) ret += c;
      return ret;
   }
};
_eval<ll> eval;

string infix =  
   "1124781624781264781268481724687+212412846287647814687*(312412478612784612784617284678126478-4124124221421412/2)+6214241241";  
  
auto postfix = eval.to_postfix(infix);  
  
cout << eval.calc_postfix(postfix); // 66360423797920478340067154229211331864487945623433009292