[DS] Stack 응용 (infix, prefix, postfix)

수식을 표현하는데 3가지 표현이 있습니다.

 

 

수식(expression)의 표현

---

수식의 표현은 2진수 연산자(binary operator)를 표함하는

수식에서 연산자(operator)와 피연산자(operand)의 위치에 따라 결정됩니다.

 

infix    →    a+b

prefix    →    +ab

postfix    →    ab+

 

infix - 두 피연산자(operand) 사이에 연산자(operator)가 위치한 수식

prefix - 두 피연산자(operand) 앞에 연산자(operator)가 위치한 수식

postfix - 두 피연산자(operand) 뒤에 연산자(operator)가 위치한 수식

 

 

 

 

prefix와 postfix를 알아야 하는 이유

---

우리에게는 infix가 익숙하지만 컴퓨터는 prefix와 postfix가 유리합니다.

 

 

 

수식(Expression) 표현 변환 (a+b*c)

---

① infix에서 postfix로 바꾸는 방법

 

1 -수식에 필요한 괄호를 채워줍니다.

(a+(b*c))

 

2 - 여는 괄호 위치에 그 괄호에 할당된 연산자(operator)를 가져옵니다.

(a+(b*c))

↓

+a*bc

 

 

② infix에서 postfix로 바꾸는 방법

 

1 - 수식에 필요한 괄호를 채워줍니다.

(a+(b*c))

 

2 - 닫는 괄호 위치에 그 괄호에 할당된 연산자(operator)를 가져옵니다.

(a+(b*c))

↓

abc*+

 

 

 

infix를 postfix로 변환하는 알고리즘(algorithm)

---

 

입력(input) - infix 표현의 수식(string)    ex) a+b*c

출력(output) - 입력에 표현된 수식의 postfix(string)    ex) abc*+

 

< 가정 >

1. 5가지의 산술 연산자(arithmetic operator)만 고려(+, -, *, / %)

2. 피연산자(operand)는 영문자 단일 문자만을 사용함

3. EOS(End of String)문자는 '$' 사용

4. Stack 코드는 아래 링크에 있습니다.

5. 괄호 사용가능

 

 

a + b * c 에서 연산자(operator)이든 피연산자(operand)이든 하나하나를 token이라고 합니다.

 

< 알고리즘>

1. stack 생성 후, EOS('$') stack에 넣고 시작합니다.

 

2. 입력 수식으로부터 token 한 개씩 확인하면서 다음을 반복합니다.

→  '( '이면 stack에 넣는다.

→  ' )' 이면, stack에서 '( '이 나올때까지 pop하여 출력하고, '( '은 stack에서 삭제합니다.

→  피연산자(operand)면 stack top 원소의 우선순위가 자신(해당 token)의 우선순위보다 낮아질 때까지 pop하여 출력하고,

해당 token은 stack에 넣는다.

→  Operand면 그대도 출력한다.

 

3. Stack에 남아 있는 모든 원소를 순서대로 pop하여 출력합니다.

 

 

Class 정의를 위한 함수 정의

---

class Infix_to_Postfix {
    char list[SIZE];
    int top;
public:
    Infix_to_Postfix();
    void push(char s);
    char pop();
    bool stack_full();
    bool stack_empty();
    char top_element();         // ← added method 1
};
bool is_operand(char s);        // ← added method 2
int get_precedence(char s);     // ← added method 3

 

top_element - 현재 stack에 있는 top 원소 return

is_operand - 피연산자(operand)이면 true return

get_precedence - 연산자(operand)의 우선순위 return 

 

 

코드 구현

---

기본 stack 구현은 아래 링크에서 확인해 주세요

https://yyyeji.tistory.com/360

 

char stack::top_element() {
    return list[top-1];
}

top_element는 현재 stack의 top 원소이 뭔지 알려주는 함수입니다.

top은 stack에서 원소가 추가될 위치를 의미하기 때문에 top의 위치인 top-1번써 list 값을 return합니다.

 

 

bool is_operand(char s){
    if((s == '(') || (s == ')')||
       (s == '+') || (s == '-')||
       (s == '*') || (s == '/')||
       (s == '%') || (s == '$'))
       return false;
    else return true;
}

is_operand는 함수 파라미터(parameter)로 들어온 문자가 피연산자(operand)인지 아닌지 알려주는 함수입니다.

파라미터(parameter)로 들어온 문자가 피연산자(operand)이면 true을 반환합니다.

 

 

int get_precedence(char s){
    if((s == '$')||(s=='(')) return 0;
    else if ((s=='+')||(s=='-')) return 1;
    else if ((s=='*')||(s=='/')||(s=='%')) return 2;
    return 3;
}

get_precedence는 함수의 파라미터(parameter)로 들어온 연산자(operator)의 우선순위를 반환하는 함수입니다.

'$'(EOS), '(' (여는 괄호)는 우선순위가 가장 낮고 나머지는 우리가 아는 우선순위 입니다.

 

 

 

 

main 함수 구현

---

int main(){
    stack s;
    string input, output;
    char t;                    // pop해서 character 저장할 공간
    cout << "Enter an infix expression to convert : ";
    cin >> input;
    input += '$';              // EOS(End of String)
    s.push('$');               // EOS(End of String)


    for(int i = 0; i<input.size(); i++){
        if(is_operand(input[i])) output+=input[i];
        else if(input[i] == '(') s.push(input[i]);
        else if(input[i] == ')') {
            for(int j = 0; j<input.size(); j++){
                if(s.top_element() == '(') {
                    t = s.pop();
                    break;
                }
                else output += s.pop();
            }
        }
        else if(!is_operand(input[i])){
            for(int j = 0; j<input.size(); j++){
                if(get_precedence(input[i]) > get_precedence(s.top_element())){
                    s.push(input[i]);
                    break;                    
                }
                else {
                    output += s.pop();    
                }
            }
        }
        else{
            for(int j = 0; j<input.size(); j++){
                if(s.top_element() == '$') break;
                else output += s.pop();
            }
        }
    }
    cout << output;
    return 0;
}

 

 

stack s;
string input, output;
char t;                    // pop해서 character 저장할 공간
cout << "Enter an infix expression to convert : ";
cin >> input;
input += '$';              // EOS(End of String)
s.push('$');               // EOS(End of String)

input 문자열을 받고 EOS(End of String) '$'문자열을 붙여주고, 스택(stack)에도 하나 넣어줍니다.

 

 

for문의 코드를 살펴보겠습니다.

if(is_operand(input[i])) output+=input[i];

is_operand 함수를 통해 현재의 token이 연산자(operator)인지 피연산자(operand)인지 구분하고,

피연산자(operand)라면 output 변수에 넣습니다.

 

 

else if(input[i] == '(') s.push(input[i]);

현재의 token이 여는 괄호('(')라면 stack에 넣어줍니다.

 

 

else if(input[i] == ')') {
    for(int j = 0; j<input.size(); j++){
        if(s.top_element() == '(') {
            t = s.pop();
            break;
        }
        else output += s.pop();
    }
}

현재 token이 닫는 괄호(')')라면 for문을 사용해서 다음을 확인합니다.

 

stack의 top 문자가 여는괄호('(')가 나오면 여는 괄호('(')를 pop하고 for문을 종료시킵니다.

여는 괄호('(')가 아니면 output 변수에 stack의 원소를 하나씩 pop해서 이어 붙입니다.

 

 

else if(!is_operand(input[i])){
    for(int j = 0; j<input.size(); j++){
        if(get_precedence(input[i]) > get_precedence(s.top_element())){
            s.push(input[i]);
            break;                    
        }
        else {
            output += s.pop();    
        }
    }
}

현재 token이 피연산자(operand)이면 for문을 사용해서 다음을 확인합니다.

 

stack의 top 원소와 현재 token의 우선순위를 비교하게 됩니다.

현재 token이 stack의 top 원소보다 우선순위가 높으면 stack에 push하고 for문을 멈추고,

우선순위가 낮으면 output 변수에 stack의 top 원소를 pop해서 이어붙입니다.

 

 

else{
    for(int j = 0; j<input.size(); j++){
        if(s.top_element() == '$') break;
        else output += s.pop();
    }
}

연산자(operator), 피연산자(operand), 여는 괄호('('), 닫는 괄호(')')가 아니면 for문을 사용해서 다음을 확인합니다.

 

stack의 top 원소가 EOS('$')이면 for문을 종료하고,

그게 아니라면 stack의 원소를 pop해서 output 변수에 이어 붙입니다.

 

 

cout << output;

처음 for문이 종료되면 output 변수의 문자열을 터미널에 출력합니다.

 

 

 

◡̈