스택 응용 2. 후위 표현의 연산

중위표현 

: 5+7처럼 연산자(Operator)가 피연산자(Operand)의 가운데에들어가는 표현이다.

 

후위표현

: 5 7 +처럼 연산자가 뒤로 가는 표현이다.

 

 우리가 수식을 프로그램 할 때에는 중위표현을 사용하지만 이 표현은 나중에 컴파일러에 의해 후위표현으로 변환되어 실행된다. 

 

(2+5)*3-1 의 후위표현은 2 5 + 3 * 1 - 가 된다. 이 후위표현을 가지고 연산을 실행하면 다음과 같다. 

언제라도 피 연산자가 들어오면 스택에 push한다. 

연산자가 들어오면 스택에 쌓인 피연산자 두 개에 대해 해당 연산을 가하고 그 결과를 다시 스택에 푸시한다. 단, 그림처럼 먼저 팝 된 피연산자가 연산자의 오른쪽으로 가게 해서 연산을 가한다. 

 

2 5 + 3 * 1 -

 

후위 연산의 연산과정을 코드로 나타내면 다음과 같다. 

 

#include <iostream>
using namespace std;

class Stack
{
public:
    Stack();
    ~Stack();

    void Push(int element);
    int Pop();
    bool is_Empty();

    void operate(char oper);
    void printStack();

private: 
    int Top;
    int stack[10];
};

int main(void)
{
    Stack s1;
    s1.Push(2);
    s1.Push(5);
    s1.operate('+');
    s1.Push(3);
    s1.operate('*');
    s1.Push(1);
    s1.operate('-');
    s1.printStack();	// 20
}						// Top: 0 값: 20

Stack::Stack(): Top(-1){}

Stack::~Stack() {}

void Stack::Push(int element)
{
    ++Top;
    stack[Top] = element;
}

int Stack::Pop()
{
    if(is_Empty())
        return -1;

    int temp = Top;
    
    --Top;
    return stack[temp];
}

bool Stack::is_Empty()
{
    return bool(Top == -1);
}

void Stack::operate(char oper)
{
    int val1 = Pop();
    int val2 = Pop();

    int result;
    switch (oper)
    {
    case '+':
        result = val2+val1;
        break;
    case '-':
        result = val2-val1;
        break;
        
    case '*':
        result = val2*val1;
        break;
    
    case '/':
        result = val2/val1;
        break;
    
    default:
        break;
    }

    Push(result);

}

void Stack::printStack()
{
    for(int i = 0; i<=Top; i++)
        cout<<stack[i]<<" ";
        
    cout<<endl;
    cout<<"Top: "<<Top<<endl;


    if(Top > 1)
        cout<<"스택이 비어있지 않습니다." <<endl;
    else  if(Top == -1)
        cout<<"값: "<<0<<endl;
    else   
        cout<<"값: "<<stack[Top]<<endl;
}