[자료구조] 후기표기식 계산하기 postfix / 스택

 

스택을 이용하여 후위표기식 계산하기 

 

- 피연산자를 만나면 스택에 push 한다.
- 연산자를 만나면 필요한 개수 만큼의 피연산자를 스택에서 pop 한다.
- 연산결과를 다시 스택에 push 한다.
- 수식이 끝나면, 마지막으로 스택을 pop하여 출력한다.

 

#include <iostream>
using namespace std;

const int MAX_NUM = 100; //define MAX_NUM 100
typedef int element;
typedef int element2;

class Stack{
public:
    element data[MAX_NUM];
    int top; //마지막 원소를 가리키는 인덱스
    
    Stack(){
        top=-1; //초기화
    }
    bool is_empty(){
        //if(top == -1) return true;
        //else return false;
        return(top == -1);
    }
    
    bool is_full(){
        //if (top == MAX_NUM-1) return true; //인덱스는 0~99까지니까 -1 해주어야 한다.
        //else return false;
        return (top == MAX_NUM-1);
    }
    
    void push(element value){
        if(is_full()){
            cout << "STACK OVERFLOW!!!" << endl;
            exit(-1);
        }
        else{
            //top++;
            //data[top] = value;
            data[++top] = value;
        }
    }
    element pop(){
        if (is_empty()){
            cout<<"STACK UNDERFLOW!!!"<<endl;
            exit(-1);
        }
        else{
            //element x = data[top];
            //top--;
            //return(x);
            return(data[top--]);
        }
    }
    element peek(){
        if(is_empty()){
            cout<< "STACK UNDERFLOW!!!" <<endl;
            exit(-1);
        }
        else{
            return(data[top]);
        }
    }
    void printStack(){
        cout << "## STACK 상태 ###" <<endl;
        for(int i = top; i >= 0; i--)
            cout << data[i] <<endl;
    }
};


class IntStack{
public:
    element2 data[MAX_NUM];
    int top; //마지막 원소를 가리키는 인덱스
    
    IntStack(){
        top=-1; //초기화
    }
    bool is_empty(){
        return(top == -1);
    }
    
    bool is_full(){
        return (top == MAX_NUM-1);
    }
    
    void push(element2 value){
        if(is_full()){
            cout << "STACK OVERFLOW!!!" << endl;
            exit(-1);
        }
        else{
            data[++top] = value;
        }
    }
    element2 pop(){
        if (is_empty()){
            cout<<"STACK UNDERFLOW!!!"<<endl;
            exit(-1);
        }
        else{
            return(data[top--]);
        }
    }
    element2 peek(){
        if(is_empty()){
            cout<< "STACK UNDERFLOW!!!" <<endl;
            exit(-1);
        }
        else{
            return(data[top]);
        }
    }
    void printIntStack(){
        cout << "## STACK 상태 ###" <<endl;
        for(int i = top; i >= 0; i--)
            cout << data[i] <<endl;
    }
};


void convert_postfix(char *infix, char *postfix)
{
    Stack PStack;
    int j = 0;
    
    for(int i = 0; i < strlen(infix); i++){
        char ch = infix[i];
        if(ch == '(') continue;
        else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') //연산자면
            PStack.push(ch);
        else if (ch == ')'){
            //char op = PStack.pop();
            //postfix[j++] = op;
            //j++
            postfix[j++] = PStack.pop();
        }
        else //일반 문자 내지 피연산자
            postfix[j++] = ch;
    }
    while (!PStack.is_empty()){
        postfix[j++] = PStack.pop();
    }
    postfix[j] = '\0';
}

int calculate_postfix(char *postfix){
    IntStack CStack;
    
    for(int i = 0; i < strlen(postfix); i++){
        char ch = postfix[i];
        int opr1, opr2;
        
        if(ch == '+'){
            opr2 = CStack.pop(); //opr2를 opr1보다 먼저 pop하는 것이 중요하다.
            opr1 = CStack.pop();
            CStack.push(opr1 + opr2);
        }else if(ch == '*'){
            opr2 = CStack.pop();
            opr1 = CStack.pop();
            CStack.push(opr1 * opr2);
        }else if(ch == '-'){
            opr2 = CStack.pop();
            opr1 = CStack.pop();
            CStack.push(opr1 - opr2);
            
        }else if(ch == '/'){
            opr2 = CStack.pop();
            opr1 = CStack.pop();
            CStack.push(opr1 / opr2);
            
        }else {
            CStack.push(ch - '0');
        }
    }
    return CStack.pop();
    
}

int main(){
    char infix[100];
    char postfix[100];
    
    cout << "중위 수식을 입력하세요: ";
    cin.getline(infix, 100);
    
    convert_postfix(infix, postfix);
    cout << "변환된 후위 표기식은: " << postfix <<endl;
    
    int result = calculate_postfix(postfix);
    cout << infix << " = " << result << endl;
}

 

입력 & 출력

중위 수식을 입력하세요: 1+2*7
변환된 후위 표기식은: 127*+
1+2*7 = 15