[C++] 중위 표기식을 후위 표기식으로 변환 후 계산

중위 표기식은 연산자가 중간에 위치하는 표기식으로 우리가 늘 쓰는 표기식이다. 후위 표기식은 연산자가 뒤에 있는 표기식으로 컴퓨터의 연산 방식이다. 컴퓨터는 사람이 입력한 중위 표기식을 후위 표기식으로 변환해서 연산을 진행한다고 한다.

중위 표기식 : A * (B + C)
후위 표기식: ABC+*

 

이번 글에서는 중위 표기식을 후위 표기식으로 변환하는 알고리즘과 후위 표기식을 계산하는 알고리즘을 다룬다. 두 가지 경우 모두 stack 자료구조가 필요하다.

 

 

1. 중위 표기식을 후위 표기식으로 변환

알고리즘은 아래와 같다.

1) 피연산자는 무조건 출력
2) 연산자인 경우
---- top보다 우선순위 크면 push
---- top보다 우선순위 작거나 같으면 pop 후 2) 반복
3) '('는 push
4) ')'가 나타나면 '(' 만날때까지 pop 후 출력
5) 피연산자가 더이상 없으면 stack에 있는거 전주 pop 후 출력

 

이를 그대로 코드로 구현하면 된다. 코드를 보기 전에 먼저 수동으로 직접 해보자. 아래의 식을 위 알고리즘에 따라 후위 표기식으로 변환해본다.

 

식 = (A+(B*C-D)+E)-(F+G)/H

코드는 아래와 같다

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int priority(char ch){
    if(ch == '+' || ch == '-') return 1;
    if(ch == '*' || ch == '/') return 2;
    return 0;
    // '('는 원래 우선순위가 가장 높지만 top에 '('가 있는 경우를 고려해줘야 하기 때문에 0으로 설정
}

int main(){
    string input, ans;
    stack<char> s;
    char c;
    
    cin >> input;
    
    for(int i = 0; i < input.length(); i++){
        c = input[i];
        
        // 1. 피연산자는 출력
        if(c >= 'A' && c <= 'Z'){
            ans += c;
            continue;
        }
        
        // 2. 스택이 비어있는 경우 또는 '('인 경우 push
        if(s.empty() || c == '('){
            s.push(c);
            continue;
        }
        
        // 3. ')'인 경우 '(' 만날때까지 출력
        if(c == ')'){
            while(s.top() != '('){
                ans += s.top();
                s.pop();
            }
            s.pop(); // '('는 삭제
            continue;
        }
        
        // 4. top보다 우선순위 크면 push
        if(priority(s.top()) < priority(c)){
            s.push(c);
        }
        
        // 5. top보다 우선순위 작거나 같으면 pop 후 반복
        else{
            while(!s.empty() && priority(s.top()) >= priority(c)){
                ans += s.top();
                s.pop();
            }
            s.push(c);
        }
    }
    
    // 6. 스택이 안 비었으면 전부 출력
    while(!s.empty()){
        ans += s.top();
        s.pop();
    }
    
    cout << ans << endl;
    
    return 0;
}

우선순위에서 '(' 가 0으로 가장 낮은 이유는 스택이 ['+', '(' ] 인 경우 새로운 연산자와 비교할 때 스택의 top이 소괄호이므로 항상 push해줘야 하기 때문이다. 엄밀히 말해서 소괄호는 항상 push기 때문에 우선순위가 가장 높지만, 스택의 top이 소괄호인 경우를 고려해줘야 하기 때문에 우선순위를 가장 낮게 설정해주는 것이다.

 

 

2. 후위 표기식의 계산

후위 표기식도 스택을 통해 구현할 수 있다. 코드는 따로 보지 않고 원리만 보겠다. 굉장히 간단하다. 딱 두 가지 규칙만 따르면 된다.

1. 피연산자면 스택에 push
2. 연산자면 스택에서 두 개 pop해서 연산 후 결과값 push

​

123*+45/-를 계산하는 예시를 살펴보자. 단, 스택에서 꺼낼 때 계산 순서가 (아래쪽) 연산자 (위쪽)임을 주의히자.