차량기지 알고리즘: 중위 표기법을 후위 표기법으로 바꾸기

중위 표기법과 후위 표기법은 수식을 표기하기 위한 방법이다. 중위 표기법(Infix Notation)은 연산자를 두 피연산자 사이에 적는 방법이고, 후위 표기법(Postfix Notation)은 연산자를 두 피연산자 뒤에 적는 방법이다. 예를 들어, 1과 2를 더하는 수식을 중위 표기법으로 작성하면 "1+2"가 되고 후위 표기법으로 작성하면 "12+"가 된다. 다른 예로, 1과 2를 더하고 그 결과에 3을 곱하는 수식을 중위 표기법으로 작성하면 "(1+2)*3"이 되고 후위 표기법으로 작성하면 "12+3*"가 된다.

 

인간은 역사적으로 중위 표기법을 써왔기 때문에 중위 표기법이 편하지만, 컴퓨터에게는 예외없이 왼쪽부터 차례로 문자를 읽어가기만 해도 수식을 정확히 이해할 수 있는 후위 표기법이 편하다. 따라서 컴파일러는 중위 표기법을 후위 표기법으로 바꾸어주어야한다. 이 문제는 에츠허르 다익스트라가 1961년에 해답을 제시하였는데, 그 알고리즘의 동작 방식이 기차의 차량기지 관리 방식과 비슷하게 생겼기 때문에 차량기지 알고리즘이라고 불린다.

 

차량기지 알고리즘

입력 중위 표기법으로 작성된 수식

출력 후위 표기법으로 작성된 수식
1. 입력값으로 주어진 수식을 좌에서 우로 한 글자씩 읽어간다.
2. 해당 글자가 피연산자라면 그 글자를 그대로 출력한다.
3. 만약 해당 글자가 연산자라면, i) 스택이 빌 때까지 ii) 스택의 탑에 여는 괄호가 있을 때까지 iii) 스택의 탑에 해당 글자보다 더 낮은 우선순위의 연산자가 있을 때까지 스택을 팝하여 출력한다. 그 후 해당 글자를 스택에 푸시한다.
4. 해당 글자가 여는 괄호면 스택에 푸시한다.
5. 해당 글자가 닫는 괄호면 여는 괄호를 만날 때까지 계속 스택을 팝하고 그 원소를 출력한다. 이때, 두 괄호 문자는 출력하지 않고 모두 버린다.
6. 2단계부터 5단계까지를 입력 수식을 다 읽을 때까지 반복한다.
7.스택에 남은 모든 원소들을 팝하고 출력한다.

 

아래는 c++로 차량기지 알고리즘을 구현한 코드이다. 하나의 중위 표기법 수식을 입력으로 받아 후위 표기법으로 바꾼 다음 출력하는 코드이다. 이때, 피연산자는 알파벳 대문자 A-Z로 간주했다.

 

 

#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool isLetterHigherThanTop(char top, char letter);

int main() {
  stack<char> st;
  string infix;

  cin >> infix;
  int infix_lenght = infix.length();
  int i;
  char letter, poped;
  
  // main loop: scan infix notation input from left to right
  for(i = 0; i < infix_lenght; i++){
    letter = infix.at(i);
    
    // If scanned letter is an operand (A-Z),
    if((letter >= 'A') && (letter <= 'Z')) {
    	// just print it.
    	cout << letter;
    }
    // If scanned letter is a left parenthesis,
    else if (letter == '(') {
    	// push it to the stack.
    	st.push(letter);
    }
    // If scanned letter is a right parenthesis,
    else if (letter == ')') {
    	// pop and print operators in stack
    	// until meeting a left parenthesis.
    	// DO NOT print any parenthesis.
    	while(true){
	    	poped = st.top();
    		st.pop();
    		if(poped == '('){
    			break;
    		}
    		else{
    			cout << poped;
    		}
    	}
    }
    // If scanned letter is an operator,
    else {
    	// pop and print operators until one of these cases meets:
    	// 1. stack is empty
    	// 2. top of the stack is a left parenthesis
    	// 3. top of the stack is an operator which has
    	//    higher priority than the scanned operater.
    	while(!st.empty() && (st.top() != '(') && !isLetterHigherThanTop(st.top(), letter)){
    		poped = st.top();
    		st.pop();
    		cout << poped;
    	}
    	// then push the operator on the stack.
    	st.push(letter);
    }
  }

  // pop and print all operators on stack
  while(!st.empty()){
  	cout << st.top();
  	st.pop();
  }

  cout << endl;

  return 0;
}

// return true if scanned operator has higher priority
// than the operator in top of the stack.
// In particular, the former is either + or -, and
// the latter is either * or /.
bool isLetterHigherThanTop(char top, char letter){
	bool isTopSmall = (top == '+') || (top == '-');
	bool isLetterBig = (letter == '*') || (letter == '/');
	return isTopSmall && isLetterBig;
}