C++ 스택(Stack)을 활용한 후위 표기식(Postfix) 평가 프로그램

수학적 표현식을 컴퓨터로 계산하려면 일반적인 중위 표기법(infix) 대신 전위 표기법(prefix) 또는 후위 표기법(postfix) 형태로 변환해야 합니다. 중위 표기식을 후위 표기식으로 변환한 뒤에는 후위 표기식 평가 알고리즘을 적용하여 정확한 답을 구할 수 있습니다.

이때 핵심적으로 사용되는 자료구조가 바로 스택(Stack)입니다.

동작 원리

후위 표기식을 왼쪽부터 한 문자씩 차례로 읽어 나가며 다음과 같이 처리합니다.

• 피연산자(숫자)를 만나면: 해당 값을 스택에 push합니다.
• 연산자를 만나면: 스택에서 두 개의 값을 pop하고, 올바른 순서(피연산자 순서)에 맞게 연산을 수행합니다.
• 연산 결과는 이후 연산에 다시 사용되므로 스택에 push합니다.

전체 표현식의 처리가 끝나면 최종 결과값이 스택의 top에 남게 됩니다.

입력: 후위 표기식: 53+62/*35*+
출력: 결과: 39

알고리즘

postfixEvaluation(postfix)

입력: 평가할 후위 표기식

출력: 후위 표기식을 평가한 결과값

Begin
    for each character ch in the postfix expression, do
        if ch is an operator, then
            a := pop first element from stack
            b := pop second element from the stack
            res := b a
            push res into the stack
        else if ch is an operand, then
            add ch into the stack
    done
    return element of stack top
End

예제 코드 (C++)

#include<iostream>
#include<cmath>
#include<stack>
using namespace std;
float scanNum(char ch) {
    int value;
    value = ch;
    return float(value-'0');   // 문자를 실수형 숫자로 변환하여 반환
}
int isOperator(char ch) {
    if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
        return 1;              // 연산자인 경우
    return -1;                 // 연산자가 아닌 경우
}
int isOperand(char ch) {
    if(ch >= '0' && ch <= '9')
        return 1;              // 피연산자(숫자)인 경우
    return -1;                 // 피연산자가 아닌 경우
}
float operation(int a, int b, char op) {
    // 실제 연산 수행
    if(op == '+')
        return b+a;
    else if(op == '-')
        return b-a;
    else if(op == '*')
        return b*a;
    else if(op == '/')
        return b/a;
    else if(op == '^')
        return pow(b,a);       // b^a 거듭제곱 계산
    else
        return INT_MIN;        // 유효하지 않은 연산자 처리
}
float postfixEval(string postfix) {
    int a, b;
    stack<float> stk;
    string::iterator it;
    for(it=postfix.begin(); it!=postfix.end(); it++) {
        // 각 문자를 읽으며 후위 표기식 평가 진행
        if(isOperator(*it) != -1) {
            a = stk.top();
            stk.pop();
            b = stk.top();
            stk.pop();
            stk.push(operation(a, b, *it));
        }else if(isOperand(*it) > 0) {
            stk.push(scanNum(*it));
        }
    }
    return stk.top();
}
main() {
    string post = "53+62/*35*+";
    cout << "결과: "<<postfixEval(post);
}

실행 결과

결과: 39

정리

이 프로그램은 스택의 LIFO(Last-In, First-Out) 특성을 활용하여 후위 표기식을 한 번의 순회만으로 평가합니다. 시간 복잡도는 O(n)으로 매우 효율적이며, 괄호나 연산자 우선순위를 고려할 필요 없이 단순한 규칙만으로 계산이 가능하다는 점이 후위 표기법의 가장 큰 장점입니다.