[Baekjoon] 1918 후위 표기식(파이썬/자바스크립트/NodeJS)

이번 문제는 아래 링크에서 풀어볼 수 있습니다.

1918번: 후위 표기식

---

문제

수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

결과: ABC*+DE/-

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

입력

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다. 

출력

첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

예제 입력 1

A*(B+C)

예제 출력 1

ABC+*

예제 입력 2

A+B

예제 출력 2

AB+

예제 입력 3

A+B*C

예제 출력 3

ABC*+

예제 입력 4

A+B*C-D/E

예제 출력 4

ABC*+DE/-

---

정답 코드

답안 1
파이썬 Ver.

import sys

data = sys.stdin.readline().rstrip()


def answer1(data):
    stack = []
    result = ""

    for c in data:
        if c.isalpha():
            result += c
        else:
            if c == "(":
                stack.append(c)
            elif c == ")":
                while stack and stack[-1] != "(":
                    result += stack.pop()
                stack.pop()
            elif c == "+" or c == "-":
                while stack and stack[-1] != "(":
                    result += stack.pop()
                stack.append(c)
            elif c == "*" or c == "/":
                while stack and (stack[-1] == "*" or stack[-1] == "/"):
                    result += stack.pop()
                stack.append(c)

    while stack:
        result += stack.pop()

    return result


print("answer1", answer1(data))

자바스크립트/NodeJS Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim();

const answer1 = (data) => {
    const stack = [];
    let result = '';

    for (let c of data) {
        if (c >= 'A' && c <= 'Z') {
            result += c;
        } else {
            if (c === '(') {
                stack.push(c);
            } else if (c === ')') {
                while (stack.length && stack[stack.length - 1] !== '(') {
                    result += stack.pop();
                }
                stack.pop();
            } else if (c === '+' || c === '-') {
                while (stack.length && stack[stack.length - 1] !== '(') {
                    result += stack.pop();
                }
                stack.push(c);
            } else if (c === '*' || c === '/') {
                while (
                    stack.length &&
                    (stack[stack.length - 1] === '*' ||
                        stack[stack.length - 1] === '/')
                ) {
                    result += stack.pop();
                }
                stack.push(c);
            }
        }
    }

    while (stack.length) {
        result += stack.pop();
    }

    return result;
};

console.log('answer1', answer1(input));

 

답안 2
파이썬 Ver.

import sys

data = sys.stdin.readline().rstrip()


def answer2(data):
    def priority(operator):
        if operator == "+" or operator == "-":
            return 1
        elif operator == "*" or operator == "/":
            return 2
        else:
            return 0

    stack = []
    result = ""

    for c in data:
        if c.isalpha():
            result += c
        else:
            if c == "(":
                stack.append(c)
            elif c == ")":
                while stack and stack[-1] != "(":
                    result += stack.pop()
                stack.pop()
            else:
                while stack and priority(stack[-1]) >= priority(c):
                    result += stack.pop()
                stack.append(c)

    while stack:
        result += stack.pop()

    return result


print("answer2", answer2(data))

 

자바스크립트/NodeJS Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim();

const answer2 = (data) => {
    const priority = (operator) => {
        if (operator === '+' || operator === '-') return 1;
        else if (operator === '*' || operator === '/') return 2;
        else return 0;
    };

    const stack = [];
    let result = '';

    for (let c of data) {
        if (c >= 'A' && c <= 'Z') result += c;
        else {
            if (c === '(') stack.push(c);
            else if (c === ')') {
                while (stack.length && stack[stack.length - 1] !== '(')
                    result += stack.pop();

                stack.pop();
            } else {
                while (
                    stack.length &&
                    priority(stack[stack.length - 1]) >= priority(c)
                )
                    result += stack.pop();
                stack.push(c);
            }
        }
    }

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

    return result;
};

console.log('answer2', answer2(input));

---

문제 풀이

 입력값으로 주어진 문자열을 for 반복문으로 탐색하면서 연산자와 괄호 간의 우선 순위에 따라 스택에다 쌓고, 문자열과 합하여 출력하면 되는 문제이다.

 답안 2를 기준으로 설명하자면 우선 연산자와 괄호의 우선 순위를 판별할 함수 priority를 선언한다. 그런 다음 입력 받은 문자열을 for 반복문으로 순회하는데 isalpha 메서드로 탐색하는 문자가 알파벳인지 판별하여 알파벳이라면 바로 result에 붙인다.

 알파벳이 아니라면 조건문을 거쳐 문자의 종류에 따라 다른 작업을 한다. 열린 괄호라면 그대로 스택에 붙여 넣는다. 닫힌 괄호라면 조건에 따라 while 반복문을 실행하는데, 스택에 값이 들어 있으면서 스택의 맨 위에 쌓인 값이 열린 괄호가 아니라면 결괏값에 스택에 쌓여 있는 값을 반복해서 붙여넣는다. 이를 반복하다 스택이 비거나 열린 괄호에 도달하면 while 반복문을 빠져나와 스택 안의 열린 괄호를 pop 메서드로 제거하고 다음 for 반복문을 실행한다.

 탐색하는 문자가 사칙 연산자라면 priority 함수를 통해 각각의 우선 순위를 반환한다. 스택의 맨 위에 쌓인 연산자의 우선 순위가 현재 탐색 중인 연산자의 우선 순위보다 높다면 스택의 맨 위 값을 result에 붙여넣는다. 즉 스택의 맨 위 값이 '*'이고 탐색 중인 값이 '+'라면 '*'의 우선 순위가 2로 더 크므로 '*'를 '+'보다 먼저 result에 붙여넣는 것이다.

 마지막으로 while 반복문을 통해 스택 안에 남은 값을 마저 result에 붙여넣은 후 result를 반환한다.

---

함께 보기

https://pannchat.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%B0%B1%EC%A4%80-%ED%9B%84%EC%9C%84%ED%91%9C%EA%B8%B0%EC%8B%9D-python

[파이썬] 백준1918 후위표기식 python

https://o-sae.tistory.com/79

[백준][파이썬] 1918. 후위 표기식