[Algorithm] infix를 postfix로 변환하기

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

오늘은 괄호를 포함한 수식을 계산하는 계산기를 만들기 위해, infix수식을 postfix로 변환하는 알고리즘을 알아보겠습니다.

infix to postfix

const open = "(";
const close = ")";

const priority = new Map();
priority.set("+", 1);
priority.set("-", 1);
priority.set("*", 2);
priority.set("/", 2);

const infix = [...];
const postfix = [];
const operators = [];

//translate to postfix
for(let e of infix){
    //if e is number
    const parsedNumber = parseInt(e, 10);
    if(!isNaN(parsedNumber)) postfix.push(parsedNumber);

    //if e is "("
    else if(e === open) operators.push(e);
        
    //if e is ")"
    else if(e === close){
        while(operators[operators.length - 1] != open){
            postfix.push(operators.pop()); 
        }
        operators.pop();
    }
        
    //if e is operator
    else{
        if(operators.length == 0) operators.push(e);
        else{
            while(operators[operators.length - 1] !== open && (priority.get(operators[operators.length - 1]) >= priority.get(e))){
                postfix.push(operators.pop()); 
            }
            operators.push(e);
        }
    }
}

while(operators.length !== 0){
    postfix.push(operators.pop()); 
}

console.log(postfix);

우선, infix로 되어있는 배열 infix가 주어졌을 때, 각 요소에 대해서

1. 여는 괄호인 경우
2. 닫는 괄호인 경우
3. 숫자인 경우
4. 연산자인 경우

로 나눠서 생각해야 합니다.

여는 괄호인 경우

우선 여는 괄호인 경우, 무조건 operators스택에 push합니다. operators스택에 push된 여는괄호는 닫는괄호의 경우에서 제거가 됩니다.

닫는 괄호인 경우

닫는 괄호인 경우, operators스택에서 여는괄호를 만날 때까지 pop해서 postfix배열에 push합니다.

숫자인 경우

숫자인 경우, 무조건 postfix배열에 push합니다. 단, push하기전에, string에서 int형으로 캐스팅을 해줘야 나중에 계산하기 편합니다.

연산자인 경우

연산자인 경우가 제일 복잡합니다.

산술연산에서 곱하기와 나누기는 더하기와 빼기보다 우선적으로 연산되어야 하므로, 각 연산별로 priority가 존재합니다. 따라서 +와 -는 1의 우선도를, *와 /는 2의 우선도를 부여했습니다. (즉, operators스택에서 우선도가 낮은 연산자가 높은 연사자 위에 쌓일 수 없습니다.)

일단 operators스택이 비어있는 경우 무조건 push하며, 비어있지 않는 경우에는 읽은 연산자와 operators의 top의 연산자의 우선순위를 비교해야 합니다.

• scan > top인 경우, operators스택에 차곡차곡 쌓입니다.
• scan <= top인경우, operators스택의 top연산자를 pop해서 postfix에 push해야 합니다. pop하고 push하는 과정을 여는괄호를 만나거나 operators스택이 빌 때까지 반복해야 합니다.

 

결과

짜잔! 잘 작동합니다. (int형으로 캐스팅하기 전이라 문자열 배열입니다.) 이를 이용해 실제로 계산하는 방법은 다음 포스트에서 다루겠습니다.