[백준] 1918. 후위 표기식

문제 링크

[백준] 1918. 후위 표기식

풀이 과정

스택 문제입니다. 괄호로 인해 우선순위와, 연산자 우선순위가 있으므로, 이를 구분해서 작성해줘야 했습니다.

const infix = input().split("");
let postfix = "";
let stack = [];

사용된 변수는 위와 같습니다.

• infix 는 입력으로 들어온 중위 표기식을 split 메서드 로 변경된 문자 배열을 담고 있습니다.
• postfix 는 후위표기식 표현 문자열을 의미합니다.
• stack 은 연산자 및 괄호 기호를 담는 데에 사용되는 스택입니다.

for (let i = 0; i < infix.length; i++) {
    let ch = infix[i];

    if (ch >= "A" && ch <= "Z") postfix += ch;
    else if (ch === "(") stack.push(ch);
    else if (ch === ")") {
        while (stack.length && stack[stack.length - 1] !== "(") postfix += stack.pop();
        stack.pop();
    } else if (ch === "+" || ch === "-") {
        while (stack.length && stack[stack.length - 1] !== "(") postfix += stack.pop();
        stack.push(ch);
    } else if (ch === "*" || ch === "/") {
        while (stack.length && (stack[stack.length - 1] === "*" || stack[stack.length - 1] === "/")) postfix += stack.pop();
        stack.push(ch);
    }
}

infix 를 순회하며, 문자가 알파벳 대문자인지, 열린 괄호인지, 닫힌 괄호인지, + 혹은 - 인지, * 혹은 / 인지에 따라 다른 처리를 하도록 합니다. 연산자 +와 -는 같은 우선순위를, *와 /는 같은 우선순위를 가지므로, 둘로 구분지어 코드를 작성합니다.

• 알파벳 대문자인 경우, 문자열 postfix 뒤에 붙여줍니다.
• 열린 괄호인 경우, 해당 문자를 스택에 넣어줍니다.
• 닫힌 괄호인 경우, 열린 괄호를 만날 때까지 stack 에 담겨있는 연산자들을 하나씩 빼 postfix 뒤에 붙여줍니다. 마지막으로 열린 괄호도 제거합니다.
• + 또는 - 인 경우, 같은 depth 내에 있는 다른 연산자들을 차례대로 빼 postfix 뒤에 붙입니다. 열린 괄호를 만나기 전까지는 같은 depth 입니다.
• * 또는 / 인 경우, 같은 우선순위인 * 와 / 이면 빼서 postfix 뒤에 붙입니다. + 와 - 는 우선순위가 낮으므로 빼지 않습니다.

코드

const fs = require("fs");
const stdin = (process.platform === "linux" ? fs.readFileSync("/dev/stdin") : `A+B*C*((D-E)*G)`).toString().trim().split("\n");
const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

const infix = input().split("");
let postfix = "";
let stack = [];

for (let i = 0; i < infix.length; i++) {
    let ch = infix[i];

    if (ch >= "A" && ch <= "Z") postfix += ch;
    else if (ch === "(") stack.push(ch);
    else if (ch === ")") {
        while (stack.length && stack[stack.length - 1] !== "(") postfix += stack.pop();
        stack.pop();
    } else if (ch === "+" || ch === "-") {
        while (stack.length && stack[stack.length - 1] !== "(") postfix += stack.pop();
        stack.push(ch);
    } else if (ch === "*" || ch === "/") {
        while (stack.length && (stack[stack.length - 1] === "*" || stack[stack.length - 1] === "/")) postfix += stack.pop();
        stack.push(ch);
    }
}

while (stack.length) postfix += stack.pop();

console.log(postfix);