Even Idiots Can Make Game

수식 표기법

Date/Lastmod
2025-05-07
Section
DEV
Categories
알고리즘

#1 정의

#1 수식 표기법의 종류

#2 중위 표기법(Infix, Polish Notation)

#2 전위 표기법(Prefix)

#2 후위 표기법(Postfix, Reverse Polish Notation)

스택 기반 머신에서 연산을 구현할때 논리의 흐름이 후위 표기식과 유사하다. JVM(Java Virtual Machine)은 연산에 스택 머신을 활용하는 대표적인 아키텍처이다. 다음의 Java 코드를 가정하자:

public class Example
{
  public static void main(String[] args)
  {
    int x = (2 + 3) * 4;
  }
}

javap -c Example로 바이트코드를 확인하면 아래와 같다.

0: iconst_2 ; push 2
1: iconst_3 ; push 3
2: iadd     ; add
3: iconst_4 ; push 4
4: imul     ; mul
5: istore_1 ; store to x

피연산자는 스택에 계속 푸시하고, 이항 연산자를 만나면 그만큼 스택에서 팝 한후 연산한다. 그리고 그 연산의 결과를 다시 스택에 넣는다.

Java 코드였던 (2 + 3) * 4는 스택 머신에서 (2 3 add) 4 mul라는 후위 표기식으로 변경되었다.

#1 수식 표기법 전환

덧셈, 뺄셈, 곱셈, 나눗셈의 네 가지 이항 연산에 대해서 수식 표기법 전환을 생각해본다.
이항 연산자의 우선 순위는 곱셉과 나눗셈이 같고, 덧셈과 뺄셈이 같다. 그리고 곱셈과 나눗셈이 덧셈과 뺄셈보다 우선 순위가 높다.

#2 중위 표기법 → 후위 표기법

#3 언제 필요한가?

컴퓨터는 후위 표기법을 가장 선호하는데, 스택 기반으로 처리하기가 쉽기 때문이다. 하지만 사람은 중위 표기가 제일 익숙하기 때문에, 사람이 작성한 중위 표기법을 컴퓨터가 이해할 수 있도록 후위 표기법으로 바꾸는 알고리즘은 자주 사용된다.

컴파일러, 계산기, 수식 해석기 등에서 중위 표기법을 후위 표기법으로 변환하는 로직은 필수적으로 구현된다.

#3 차량 기지(Shunting Yard) 알고리즘

중위 표기법 후위 표기법으로 전환하는 여러 방법 중에서 스택이 가장 간편하고, 1 다익스트라가 만든 차량 기지(Shunting Yard) 알고리즘이 유명하다.

차량기지 알고리즘은, 스택을 이용하여 연산자를 저장하는데, 이것이 마치 차량기지에 차를 주차하는 것과 비슷하다고 하여 차량기지 알고리즘이라는 이름이 붙었다.

알고리즘을 기술하면 다음과 같다.

글로 읽으면 왜 차량 기지인지 잘 감이 안오는데, 그림으로 보면 쉽게 이해할 수 있다.

예를 들어 A * (B + C) 라는 중위 표현식을 차량기지 알고리즘을 통해 후위 표현식으로 나타내는 과정은 아래와 같다.

C++ 코드로 표현하면 아래와 같다. 피연산자는 'A' 부터 'Z'까지의 문자라고 가정한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

// 전환할 중위 표현식
string infix; cin >> infix;

// 연산자인지 여부를 반환
auto is_operator = [](char ch) {
  return ch == '+' || ch == '-' || ch == '*' || ch == '/';
};

// 이항 연산자의 우선순위를 반환
auto precedence = [](char ch) {
  switch (ch) {
    case '+': case '-': return 0; 
    case '*': case '/': return 1;
  }
};

// 연산자를 저장할 스택
stack<char> op_stack;

// 중위 표기식 문자열의 문자 ch를 하나 하나 읽는다:
for (char ch: infix) {
  // 피연산자라면, 
  if (isalpha(ch)) {
    cout << ch;
  
  // 연산자라면
  } else if (is_operator(ch)) {

    // 탑에 연산자가 존재하고, 우선순위가 ch 이상인 경우 계속해서 탑을 출력하고 팝한다.
    while (!op_stack.empty() && op_stack.top() != '(' && precedence(op_stack.top()) >= precedence(ch)) {
      cout << op_stack.top();
      op_stack.pop();
    }
    // 현재 연산자를 푸시한다.
    op_stack.push(ch);
  
  // 여는 괄호라면
  } else if (ch == '(') {
    op_stack.push(ch);

  // 닫는 괄호라면
  } else if (ch == ')') {
    // 여는 괄호 나올때 까지 연산자를 모두 출력
    while (op_stack.top() != '(') {
      cout << op_stack.top();
      op_stack.pop();
    }
    // 여는 괄호는 삭제해 줌
    op_stack.pop();
  }
}

// 스택에 남은 연산자가 있다면 출력
while (!op_stack.empty()) {
  cout << op_stack.top();
  op_stack.pop();
}

위 알고리즘을 이용하여 [백준] 1918 G2 후위 표기식 문제를 날먹할 수 있다.

#2 후위 표기법 → 중위 표기법


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

string postfix; cin >> postfix;
auto precedence = [](char ch) {
  switch (ch) {
    case '+': case '-': return 0; 
    case '*': case '/': return 1;
  }
};

auto is_operator = [](char ch) {
  return ch == '+' || ch == '-' || ch == '*' || ch == '/';
};

stack<string> op_stack;

for (char ch: postfix) {
  // 피연산자 일 때
  if (isalpha(ch)) {
    op_stack.push(string{ch});

  // 연산자일 때
  } else if (is_operator(ch)) {
    string r_op = op_stack.top(); op_stack.pop();
    string l_op = op_stack.top(); op_stack.pop();

    // 연산자로 결합
    string exp = "(" + l_op + ch + r_op + ")";
    op_stack.push(exp);
  }
}

while (!op_stack.empty()) {
  cout << op_stack.top();
  op_stack.pop();
}

[백준] 1935 S3 후위 표기식2 문제에서 위 알고리즘을 응용해 후위 표기식의 값을 직접 계산해 볼 수 있다.

#3 언제 필요한가?

보통 디버깅 / 리버싱을 통해 내부적으로 (JVM처럼) 후위 구조로 된 수식을 인간이 읽기 편한 중위 수식으로 변경할 때 사용한다.

#2 중위 표기법 → 전위 표기법

차량기지 알고리즘을 재활용한다. 중위 표기법 문자열을 거꾸로 뒤집어서, 차량기지 알고리즘을 적용하여 후위 표기법으로 만든다.

그리고, 그 후위 표기식을 다시 뒤집으면 전위 표기식이 나온다.

#1 참고 문헌

  1. 이진 트리를 이용하는 방법도 있으나 구현이 복잡하다. ↩︎

comments powered by Disqus