[자료구조] 후위표기식 변환 postfix / 스택

후기표기식 변환

• 중위표기 수식을 후위표기 수식으로 변환
• 알고리즘 개요
  • 수식의 각 연산자에 대해 우선순위에 따라 괄호를 적용
  • 각 연산자를 그에 대응하는 오른쪽 괄호 뒤로 이동
  • 괄호를 제거
• 예) A*B-C/D 수식의 후위표기 수식 변환
  
  1. ((A*B)-(C/D))
  2. ((A B)* - (C D)/) 
  3. ((A B)* (C D)/)-
  4. A B * C D / -

 

스택을 이용한 후위표기식 변환

1. 왼쪽 괄호를 만나면, 무시하고 다음 문자를 읽는다.
2. 피연산자를 만나면 출력한다.
3. 연산자를 만나면 스택에 넣는다.
4. 오른쪽 괄호를 만나면 스택을 pop하여 출력한다.
5. 수식이 끝나면 스택이 공백이 될 때까지 pop 하여 출력한다.

 

• 연산자만 스택에 넣고, 피연산자는 그대로 출력
• 오른쪽 괄호가 나오면 스택에 있던 연산자를 pop하여 출력

 

#include <iostream>
using namespace std;

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

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;
    }
};

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 main(){ 
    char infix[100];
    char postfix[100];
    
    cout << "중위 수식을 입력하세요: ";
    //cin >> infix;
    cin.getline(infix, 100);
    
    convert_postfix(infix, postfix);
    cout << "변환된 후위 표기식은: " << postfix <<endl;
    
}

 

 

중위 수식을 입력하세요: ((A*B)-(C/D))
변환된 후위 표기식은: AB*CD/-